خب همونطور که قول دادم شرح کد ( البته ببخشید دیر شد
)
در مورد الگوریتم و روش به کار رفته:
در این برنامه از سه کلاس استفاده کردم :
الف) کلاس نود (node) که مربوط به اطلاعات هر حالت از قرار گیری اعداد روی صفحه، مقدار تابع منهتن در وضعیت خاص و ...
ب) کلاس صف اولویت که عناصر آن را وضعیت های ممکن از حالت شروع است و بر اساس دو مقدار فاصله طی شده (g(x)) و مقدار تابع اکتشافی اولویت آنها تعیین می گردد.
ب) کلاس عناصر صف (objectqueue) با توجه به اینکه باید در هر خانه از صف اولویت یک نمونه از کلاس نود قرار گیرد و با توجه به حجم بالایی از حافظه که ممکن است از این طریق هدر رود. عناصر مهم این کلاس به طور خلاصه شده و کم حجم در این کلاس قرار داده می شود و در صف اولویت قرار می گیرد و در هنگام نیاز به نوع اصلی یعنی کلاس نود تبدیل می شود.
برای کلاس نود به یکسری پارامتر نیاز داریم که شامل موارد زیر است:
1- یک ماتریس 3 در 3 که موقعیت اعداد در خانه های جدول را مشخص کند
2- یک عدد که مقدار تابع مکاشفه ای (فاصله منهتن) را نگه می دارد.
3- محل خانه خالی جدول
4- تعداد مراحل طی شده
5- و مقدار تابع h(x) که شامل جمع مراحل طی شده و مقدار تابع مکاشفه ای است.
در مورد توابع و یا متدهای کلاس صحبت نمی کنم و به اصل برنامه اشاره می کنم (البته اگر سوالی هست مطرح کنید)
همونطور که می دونید از هر چیدمانی از عناصر نمی توان به وضعیت مرتب شده رسید در واقع 9! حالت چیدمان عناصر امکان پذیر است و از نیمی از این تعداد برای ما قابل قبول هستند بنابراین باید از یک وضعیت مرتب شده خانه های جدول را درهم کنیم.
در این برنامه اساس کار مبنی بر حرکت دادن خانه خالی است.
خب تابع اصلی اجرای برنامه createtree() می باشد. در این تابع ابتدا وضعیت جاری جدول را در یک نمونه از کلاس نود قرار می گیرد پارامترهای کلاس را set می کنیم. حالا این کلاس را در صف اولویت قرار داده و وارد حلقه اصلی برنامه می شویم.
کارهایی که در حلقه اصلی برنامه انجام می شود:
با اولویت ترین عنصر (ابتدای صف) برداشته می شود. سپس حالتهای بعدی را مشخص می کنیم (از طریق یافتن اینکه خانه خالی به چه خانه هایی امکان حرکت دارد با استفاده از تابع availablemove() از کلای نود) در مرحله بعد به تعداد خانه هایی که امکان حرکت وجود دارد، یک نمونه از کلاس نود ایجاد شده و در هرکدام، خانه خالی را به یکی از سمت های مجاز برده و پارامترهای آن را ازجمله فاصله منهتن را حساب کرده و سپس آن را در صف اواویت قرار می دهیم. ضمنا مسیر حرکت نیز درآرایه ای به نام path نگهداری می شودیعنی قبل از قرار گرفتن عنصر در صف در این آرایه مشخص می شود که یک وضعیت خاص از وضعیت آغازین چه حرکتهایی را انجام داده تا به این وضعیت برسد. شکل زیر کلیات این کار را نشان می دهد:
در صورتی که فاصله منهتن یکی از نود های تولیدی صفر شود یعنی مسئله حل شده و بنابراین از حلقه اصلی خارج می شویم. در غیر این صورت به ابتدای حلقه بازگشته و با اولویت ترین نود را انتخاب کرده و مراحل بالا را دوباره انجام می دهیم.
نکته قابل ذکر این که یک نود بعد از خروج از صف علنا از صف کنار گذاشته می شود ولی در قسمتی از حافظه نگهداری می شود تا درصورتی که در مراحل بعد یک نود مشابه این نود تولید شود دوباره بررسی نشود (چون قبلا بررسی شده است.)
البته می خواستم در مورد کلاسها و توابع اونها هم بنویسم ولی گفتم درصورتی که کسی مشکلی داشت به اون ها بپردازم. بنابراین اگر متوجه قسمتی نشدید حتما اشاره کنید.