آموزش مسئله 8 وزیر هوش مصنوعی به صورت جامع و گام به گام

در این مقاله قصد داریم در مورد مسئله 8 وزیر هوش مصنوعی صحبت کنیم. همانطورکه می دانید 8 وزیر یکی از مسائل مربوط در زمینه هوش مصنوعی هست و چندین روش کاربردی برای حل آن وجود دارد. در این مقاله به تعدادی از این روش‌ها خواهیم پرداخت. با ما همراه باشید.

مقدمه و تاریخچه مسئله 8 وزیر هوش مصنوعی

کسایی که شطرنج بازی می‌کنند و با آن آشنایی دارند می‌دانند که در بازی شطرنج هر مهره قانونی برای حرکت دارد و مهره وزیر هم از این امر مستثنی نیست. وزیر می‌تواند به‌صورت افقی یا عمودی یا ضربدری برای بقیه مهره‌ها تهدید باشد. مسئله 8 وزیر هم در همین رابطه هست. سوالی که در این مسئله مطرح است این است که به چند روش می‌توان هشت وزیر را روی یک صفحه شطرنج قرار داد تا هیچ دو وزیربه یکدیگر حمله نکنند و برای هم تهدید محسوب نباشند. قبل از هر چیزی در ابتدا ببینیم مسئله 8 وزیر کی و چطور مطرح شد. در ادامه نگاهی به تاریخچه این مسئله می اندازیم.

مسئله 8 وزیر ظاهراً اولین بار توسط ماکس بزل (Max Bezzel) در روزنامه شطرنج برلین در سال (1848) مطرح شد و اولین بار توسط فرانتس ناوک (Franz Nauck) در روزنامه مصور لایپزیگ (1850) به طور کامل حل شد و بعداً توسط Nauck پازل به مسئله n وزیر روی یک صفحه شطرنج n×n گسترش داده شد. پس از آن (Gunther) راه حلی با استفاده از دترمینان ارائه داد که J.W.L. Glaisher آنرا کامل کرد و درنهایت در سال 1979، Edsger Dijkstra با استفاده از الگوریتم عقب گرد اول عمق این مسئله را حل کرد. اگر علاقمند به دانستن اطلاعات بیشتر در مورد ادسخر دیکسترا هستید می‌توانید از اینجا (+) در مورد ایشان بیشتر بخوانید.

مسئله 8 وزیر هوش مصنوعی 92 راه حل دارد که 12 راه حل آن منحصر به فرد است و بقیه از تقارن این 12 تا بدست می آیند. هر یک از دوازده راه‌حل نشان‌داده‌شده در این صفحه، یک کلاس معادل از راه‌حل‌ها را نشان می‌دهد که با چرخاندن صفحه شطرنج و/یا چرخاندن آن در امتداد یکی از محورهای تقارن آن از یکدیگر حاصل می‌شوند. هر یک از کلاس های هم ارزی نشان داده شده توسط راه حل های 1و 2 و.. 11 شامل هشت راه حل است. از آنجایی که راه حل 12 با چرخش 180 درجه صفحه شطرنج ثابت است، کلاس هم ارزی آن تنها از چهار راه حل تشکیل شده است.

مسئله n وزیر هوش مصنوعی از جمله مسائل NP-Hard در هوش مصنوعی است که روش‌های جستجوی معمولی قادر به حل آن‌ها نخواهد بود. راستی حواسمان باشد که این مسئله در صورتی که n=2 و n=3 باشد، راه حلی ندارد. فهمیدن این موضوع کار سختی نیست. جدولی با 4 عنصر تصور کنید و دو وزیر هر طوری بچینید همدیگر را تهدید می‌کنند و 3 وزیر و صفحه شطرنج 3 در 3 هم به همین صورت هست. 12 حالت اصلی را در شکل زیر مشاهده می‌کنیم.

مشکل یافتن همه راه‌حل‌ها برای مسئله 8 وزیر هوش مصنوعی می‌تواند از نظر محاسباتی بسیار گران باشد، زیرا 4،426،165،368 ترتیب ممکن از هشت وزیر که در یک سطح 8×8 وجود دارد، اما تنها دارای 92 راه حل متمایز است پس این مسئله فضای جستجوی وسیعی دارد. می‌توان از میانبرهایی استفاده کرد که الزامات محاسباتی را کاهش می‌دهد یا قوانین کلی که از تکنیک‌های محاسباتی brute-force اجتناب می‌کند.

به عنوان مثال، با اعمال یک قانون ساده که هر وزیر را به یک ستون (یا ردیف) محدود می‌کند، اگرچه همچنان نیروی brute در نظر گرفته می‌شود، می‌توان تعداد احتمالات را به 16777216 (یعنی 8 به توان 8) ترکیب ممکن کاهش داد.

روش های حل مسئله 8 وزیر هوش مصنوعی

در این مطلب مسئله 8 وزیر با 4 روش زیر حل شده‌اند:

• استفاده از روش مکاشفه ای (heuristic) در حل مسئله 8 وزیر هوش مصنوعی برای N>=4 یا n=1
• روش های جستجوی محلی در مسئله 8 وزیر هوش مصنوعی
• حل مسئله 8 وزیر هوش مصنوعی با الگوریتم ژنتیک
• حل مسئله 8 وزیر هوش مصنوعی با روش عقبگرد یا Back tracking

در ادامه به توضیح هرکدام از این روش‌ها می‌پردازیم.

استفاده از روش مکاشفه ای (heuristic) در حل مسئله 8 وزیر هوش مصنوعی برای N>=4 یا n=1

برای حل این مسئله که دارای ۹۲ جواب است، باید روش هایی جهت کاهش حالات، روش Brute Force یا امتحان تک تک جواب‌ها را انجام داد.

1- عدد n را بر عدد 12 تقسیم کن و باقی مانده را یادداشت کن.

2- به ترتیب اعداد زوج 2 تا n را در یک لیست بنویس.

3- اگر باقی مانده 3 یا 9 بود، عدد 2 را به انتهای لیست انتقال بده.

4- به لیست اعداد فرد 1 تا N را به ترتیب اضافه کن. اما اگر باقی مانده 8 بود جای اعداد را دو به دو باهم عوض کن. ( 1-3-5-7-9 می شه 3-1-7-5-9)

5- اگر باقی مانده 2 بود جای 1 و 3 را باهم عوض کن و 5 را به انتهای لیست ببر.

6- اگر باقی مانده 3 یا 9 بود، اعداد 1 و 3 را به انتهای لیست ببر.

7- حال با استفاده از لیست بدست آمده وزیرها در صفحه شطرنج چیده می شوند، بطوریکه جای وزیر ستون اول، اولین عدد لیست، جای وزیر ستون دوم، دومین عدد لیست و….

برای به‌دست آوردن حالات دیگر از روش‌های دیگر باید استفاده شود. روش حل مسئله 12 راه حل یکتا دارد با در نظر گرفتن تقارن و چرخش به 92 حالت قابل تبدیل است.

روش های جستجوی محلی در مسئله 8 وزیر هوش مصنوعی

در این نوع از روش‌ها هدف یافتن مسیری با کم‌ترین هزینه از حالت شروع به حالت هدف در گراف فضای حالت است. در بسیاری از مسائل بهینه سازی مسیر راه حل اهمیت ندارد. بلکه خود حالت هدف مهم است که نسبت به حالت‌های دیگر در فضای حالت‌ها بهتر باشد. به مسئله 8 وزیر هوش مصنوعی می‌توان به عنوان یک مسئله بهینه سازی هم نگاه کرد که هدف بهینه کردن تعداد تهدیدهای جفت وزیرها است.

یعنی وزیرها را می‌چینیم ولی در نهایت اونی جواب می شه که کمترین تعداد برخوردها را داشته باشد.

روش کار به این شکل است که:

• استفاده از یک حالت به عنوان حالت فعلی
• بهبود حالت فعلی از طریق حرکت به یکی از حالت های همسایه

همسایه‌های اطراف وزیر را نگاه می‌کنیم که با حرکت وزیر به روی آن همسایه یا خانه شطرنج، تهدیدها کمتر می‌شود یا نه و دوباره باز چک کردن همسایه ها را ادامه می دهیم و بالاخره می‌رسیم به چیدمانی که حالت بهینه است. مزایای این روش این است که مصرف حافظه بسیار کمتر است و می‌توان به راه حل‌های معقول در فضاهای بسیار بزرگ یا نامحدود دست یافت.

حل مسئله 8 وزیر با الگوریتم جستجوی ممنوعه TS در متلب

در این بخش سورس کد حل مسئله 8 وزیر با الگوریتم جستجوی ممنوعه TS در متلب قرار داده شده است. در این سورس کد دو نمونه از حل مسئله، مسئله 8 وزیر هوش مصنوعی و n وزیر با الگوریتم TS در متلب ارائه شده است.

همین الان کلیک کنید

مسئله 8 وزیر هوش مصنوعی را با این روش حل می‌کنیم. البته مثالمان را برای 4 وزیر می‌زنیم که حجم مسئله کوچکتر باشد. در ابتدا جدولی داریم با 4 خانه و 4 وزیر. حالت اولی را اتفاقی انتخاب می‌کنیم. چیدمان آن اتفاقی است. این مسئله را بدین صورت فرموله سازی می‌شود. که در هر ستون می دانیم که فقط یک وزیر می‌تواند وجود داشته باشد و عملیات را طوری تعریف می‌کنیم که هر وزیر فقط در ستون خودش حرکت کند. اندازه فضای حالت 4 به توان 4 می‌شود. که در حالت‌های بزرگ N به توان N است. نرخ رشد N به توان N بسیار سریع است و فضای حالت بسیار بزرگی دارد.

در این مسئله در حالت 4 دیگه متوقف می شویم و به جواب بهینه رسیدیم.

حل مسئله 8 وزیر هوش مصنوعی با الگوریتم ژنتیک

در مورد مسئله 8 وزیر می دانیم که دو وزیر نباید در یک ستون قرار بگیرند. برای نمایش مسئله در مورد کروموزوم‌ها بدین ترتیب عمل می‌کنیم: ابتدا یک آرایه تک بعدی ایجادمی کنیم که به تعداد ستون‌های شطرنج ما عنصر دارد. هر عنصر از این آرایه نشان می‌دهد که وزیر در آن ستون در کدام سطر قرار دارد. اگر مسئله 8 وزیر را در این قالب تصور کنیم آرایه ما 8 عنصر خواهد داشت و فرضاً آرایه دارای مقادیر زیر است.

8,7,6,5,4,3,2,1

برای توضیح بیشتر، مقدار 8 در اولین عنصر نشان دهنده این است که در ستون اول صفحه شطرنج، وزیر در سطر هشتم قرار دارد در ستون دوم وزیر در سطر 7 قرار دارد و… . ابتدا باید طبق الگوریتم ژنتیک تولید جمعیت اولیه کنیم.

مسئله هشت وزیر با الگوریتم ژنتیک GA در متلب

سورس کد مسئله هشت وزیر با الگوریتم ژنتیک GA در متلب عنوان محصولی است که در این بخش به آن پرداخته شده است. در این سورس کد دو نمونه از حل مسئله 8 وزیر و n وزیر با الگوریتم ژنتیک در متلب ارائه شده است.

همین الان کلیک کنید

تولید جمعیت اولیه

الگوریتم ژنتیک در ابتدای کار تولید جمعیت اولیه می‌کند بعداً سعی می‌کند این جمعیت اولیه را بهبود ببخشد. برای این مسئله تولید جمعیت اولیه به‌صورت تصادفی خواهد بود.

نحوه انتخاب والدین

نحوه انتخاب والدین به این صورت است که 5 کروموزوم به‌طور تصادفی انتخاب می‌شوند. بعد از بین این 5 کروموزوم دوتایی که تابع سازگاری آنها بیشینه‌تر هست انتخاب می‌شوند. نحوه محاسبه این تابع بدین شکل است که برای هر ژن که در مسئله 8 وزیر هوش مصنوعی ژن همان وزیرهای ما هست. برای هر وزیر تعداد تهدیدها حساب می‌شوند و از معکوس جمع آنها مقدار تابع سازگاری برای هر وزیر به‌دست می‌آید. هدف داشتن حداکثر تابع سازگاری است.

برای تولید فرزندان یک نقطه رندوم در کروموزوم‌ها انتخاب می‌شود. فرزند اول ژن‌های سمت چپ این نقطه در والد اول و فرزند دوم ژن‌های سمت چپ این نقطه در والد دوم را به ارث می‌برند. سپس برای پر کردن باقی ژن‌ها در سمت راست این نقطه در فرزند اول، والد دوم را از سمت چپ به راست پیمایش کرده و هر مقداری که در فرزند اول وجود نداشت را به همان ترتیب پیمایش در این فرزند درج می‌کنیم. برای پر کردن سمت راست فرزند دوم نیز همین کار را با والد اول تکرار می‌کنیم.

برای هر یک از فرزندان به احتمال 80% جهش ایجاد می‌شود. دو اندیس از آرایه به صورت تصادفی انتخاب می‌شود و مقدار موجود در آنها باهم جابه جا می‌شود. سپس کل جمعیت براساس تابع سازگاری مرتب می‌شوند و دو کروموزوم یا وزیر آخر که جز بدترین‌ها هستند را با فرزندان جابه جا می‌کنیم.

نتیجه: الگوریتم با توجه به جمعیت انتخاب شده بعد از یک تا بیشتر از 20 بار تکرار می تواند به جواب برسد.

حل مسئله 8 وزیر با الگوریتم ژنتیک در سی شارپ #C

در این بخش سورس کد حل مسئله 8 وزیر با الگوریتم ژنتیک در سی شارپ #C همراه با گزارش کار قرار داده شده است. در این سورس کد مسئله 8 وزیر با استفاده از الگوریتم ژنتیک پیاده سازی شده است.

همین الان کلیک کنید

برای مطالعه تکمیلی در مورد الگوریتم ژنتیک مقاله جامع و کاملی را در همین سایت آماده کرده ایم که می توانید این مقاله را با عنوان آموزش الگوریتم ژنتیک – آموزش رایگان و جامع از 0 تا 100 الگوریتم ژنتیک مطالعه فرمایید.

حل مسئله 8 وزیر هوش مصنوعی با روش عقبگرد یا Back tracking

عقبگرد یا همان backtracking روشی است که در آن تمام حالت‌های ممکن ساخته می‌شود و هر حالتی که ساخته می‌شود چک می‌شود تا درست یا غلط بودن آن بررسی شود و اگر غلط بود حالتی دیگر را تولید می‌کند و همین طور ادامه می‌دهد.

شکل بالا درخت تمام حالاتی است که 4 وزیر را می‌توان در صفحه شطرنج 4 در 4 قرار داد. وزیر اول می‌تواند در ستون‌های 1 تا 4 قرار گیرد. وزیر دوم هم می‌تواند در سطر دوم در ستون‌های 1 تا 4 قرار بگیرد و همین طور الی آخر ادامه دارد. حالا برای پیدا کرن جواب از درخت باید درخت را پیمایش کنیم. ابتدا یک حالت را با پیمایش عمقی درخت به‌دست می‌آوریم.

در پیمایش عمقی ابتدا ریشه دیده می‌شود و بعد از آن فرزندان به‌طوری که فرزندان چپ پیمایش می‌شوند. تا اینکه به فرزند برگ برسیم. مجدد از ریشه شروع می‌کنیم تا فرزند برگ یکی بعد از قبلی که پیمایش شد. با مشاهده نمونه‌های پایین متوجه نحوه پیمایش می‌شوید.

(1,1)(2,1)(3,1)(4,1) – (1,1)(2,1)(3,1)(4,2) – (1,1)(2,1)(3,1)(4,3) – (1,1)(2,1)(3,1)(4,4) – (1,1)(2,1)(3,2)(4,1) – (1,1)(2,1)(3,2)(4,2) – (1,1)(2,1)(3,2)(4,3) – (1,1)(2,1)(3,2)(4,4) – (1,1)(2,1)(3,3)(4,1) – (1,1)(2,1)(3,3)(4,2) – (1,1)(2,1)(3,3)(4,3) – (1,1)(2,1)(3,3)(4,4) – (1,1)(2,1)(3,4)(4,1) – (1,1)(2,1)(3,4)(4,2) – (1,1)(2,1)(3,4)(4,3) – (1,1)(2,1)(3,4)(4,4) – (1,1)(2,2)(3,1)(4,1) – (1,1)(2,2)(3,1)(4,2) – (1,1)(2,2)(3,1)(4,3) – (1,1)(2,2)(3,1)(4,4) – (1,1)(2,2)(3,2)(4,1) – (1,1)(2,2)(3,2)(4,2) – (1,1)(2,2)(3,2)(4,3) – (1,1)(2,2)(3,2)(4,4) – (1,1)(2,2)(3,3)(4,1) – (1,1)(2,2)(3,3)(4,2) – (1,1)(2,2)(3,3)(4,3) – (1,1)(2,2)(3,3)(4,4) – (1,1)(2,2)(3,4)(4,1) – (1,1)(2,2)(3,4)(4,2) – (1,1)(2,2)(3,4)(4,3) – (1,1)(2,2)(3,4)(4,4) …

بدین ترتیب با پیمایش عمقی درخت به‌صورت preorder تمامی حالات 4 وزیر به‌صورت منظم به‌دست می‌آیند برای رسیدن به جواب باید تک تک حالت‌ها رابررسی کنیم که آیا وزیرها همدیگر را تهدید می‌کنند یا نه. اگر هیچ وزیری همدیگر را تهدید نکردند معلوم می‌شود که به جواب رسیده ایم و آن را چاپ می‌کنیم.

سخن آخر در مورد آموزش مسئله 8 وزیر هوش مصنوعی

در این مقاله مسئله 8 وزیر هوش مصنوعی را مورد بررسی قرار دادیم. توضیح دادیم 8 وزیر به نحوی باید در صفحه شطرنج قرار بگیرند تا هیچ دو وزیری همدیگر را تهدید نکنند. تعداد حالات ممکن بررسی شد. با چندین روش الگوریتمی حل مسئله 8 وزیر را توضیح دادیم. با مطالعه این مقاله دید کلی در مورد این مسئله بسیار معروف هوش مصنوعی پیدا خواهید کرد و اگر مایل به یادگیری بیشتر در این مورد هستید می‌توانید از لینک زیر فایل پیاده سازی آن را تهیه کنید. ممنون که تا آخر مقاله ما را همراهی نمودید.