پروژه حل مساله تور اسب با گمز

توضیحات

پروژه حل مساله تور اسب با گمز

در این پروژه به بررسی موارد زیر میپردازیم:

مسئله تور اسب (Knight ‘ s Tour Problem) عبارت است از یافتن توالی حرکت اسب در صفحه شطرنج به طوری که از تمامی خانه ها عبور کند و از هر خانه فقط یک بار عبور کند. مدل ارضای محدودیت (Constraint Satisfaction مدلی است که پاسخ آن یک جواب شدنی برای مسئله است و لذا این مدل جهت بهینه سازی ندارد. در نرم افزار GAMS برای حل یک مدل ارضای محدودیت کافی است مدل را با کمینه یا بیشینه کردن یک تابع هدف مجازی مثل 3 = Max Z حل کنید تا نرم افزار بعد از رسیدن به اولین جواب شدنی فرآیند حل را متوقف کند.

الف) مسئله تور اسب را به یک مسئله فروشنده دوره گرد (TSP) تبدیل میکنیم. 

ب) مدل ریاضی مربوط به قسمت (الف) را در نرم افزار GAMS کد کرده و حل میکنیم

ج) مسئله تور اسب را به یک مدل ارضای محدودیت تبدیل میکنیم. چگونگی این تبدیل را توضیح میدهیم

د) مدل ریاضی مربوط به قسمت (ج) را در نرم افزار GAMS کد کرده و  جواب مدل را نشان میدهیم.

بخشهایی از صورت پروژه حل مساله تور اسب با گمز

ﭘﻴﺸﻴﻨﻪ ‫اوﻟﻴﻦ ﻧﻤﻮﻧﻪ ﻣﺴﺎﻟﻪ ﻓﺮوﺷﻨﺪه دوره ﮔﺮد ﺗﻮﺳﻂ اوﻳﻠﺮ2در9571 ﻣﻄﺮح ﺷﺪ ﻛﻪ ﻫﺪف آن ﺣﺮﻛﺖ دادن ﻳﻚ ﻣﻬﺮه اﺳـﺐ ﺑـﻪ ﻫﻤـﻪ ﻣﻮﻗﻌﻴـﺖ ‫ﻫﺎي ﺻﻔﺤﻪ ﺷﻄﺮﻧﺞ ﺑﻮد (مسئله تور اسب). مساله فروشنده دوره گرد (TSP ) یكی از مسائل مشهور بهینه سازی تركیبی است كه اساس آن به این صورت است كه یك فروشنده دوره گرد می خواهد بهN شهر (در مسئله تور اسب 64 شهر است) برود و كالای خود را به فروش برساند ، به طوری كه از هر شهر فقط یك بار عبور كند و تمام شهر ها را رفته باشد و در نهایت كمترین مسیر را طی كرده باشد.

می خواهیم مدل مسئله ای را بنویسیم که یک اسب را در یکی از خانه های شطرنج قرار دهد و اسب را طوری جا به جا کند که اسب از همه خانه های شطرنج عبور کند بدون این که از یک خانه بیش از یک بار عبور کند.

برنامه حرکت اسبی یا همان knight tour. اسب می تواند حرکاتی به شکل  L  انجام دهد(دو خانه در یک جهت و سپس یک خانه در جهت  عمود بر جهت اول )به این ترتیب یک اسب از خانه ای در وسط صفحه خالی شطرنج می تواند هر یک از هشت حرکت مختلف را که در شکل می بینید انجام دهد.

روشهای متفاوتی برای حل این مساله وجود دارد. استفاده از قانون وارنزدورف یکی از روش‌های اکتشافی برای این مساله است. اسب در هر حرکت به خانه‌ای می‌رود که آن خانه امکان کمترین حرکت رو به جلو را دارد. برای انتخاب خانه مناسب، تعداد حرکت‌های ممکن خانه کاندید (با حذف خانه‌های طی شده) را محاسبه می‌کنیم. خانه‌ای که کمترین عدد ممکن را داشته باشد انتخاب می‌شود.

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

مدل ارضای محدودیت مسئله تور اسب

i، j، i’، j’:  اندیس سطرها و ستون های شطرنج (i,j=1,…,8).

N: تعداد کل خانه های جدول که برابر است با i*j

 Constraint satisfaction problem (CSP(

پروژه حل مساله تور اسب با گمز توسط کارشناسان گروه ۱.۲.۳ پروژه پیاده سازی گردیده و به تعداد محدودی قابل فروش می باشد.

• فایلهای پروژه به صورت کامل پس از خرید فایل بلافاصله در اختیار شما قرار خواهد گرفت.