menu

حل معمای ۸ با روش A Star در سی شارپ

سلام. در این پست به آموزش حل معمای ۸ به وسیله ی الگوریتم A* در سیشارپ می پردازیم.

 

معمای هشت چیست؟

معمای هشت یک پازل ۳ در ۳ هست که در آن ۸ کاشی که اعداد یک تا هشت بر روی آنها نوشته شده، وجود دارند و یکی از خانه ها خالی است. شما باید با جابجا کردن کاشی های مجاور خانه ی خالی، وضعیت بهم ریخته ای از اعداد را به ترتیب شماره مرتب کنید.

معمای هشت چیست؟

معمای هشت چیست؟

حال ما سعی داریم تا این مسئله رو با زبان سیشارپ و روش جستجوی A* حل کنیم. فک میکنم براتون جالب باشه که بدونید من یک وضعیت رو با روش BFS حل کردم و ۸۰ ثانیه طول کشید، و همون وضعیت رو با روش A* حل کردم و کمتر از یک ثانیه طول کشید!

در کل چطوری میخوایم حلش کنیم؟

برای حل معمای هشت با هوش مصنوعی، ما از یک گراف خیلی بزرگ استفاده میکنیم. گراف ما به این صورت هست:

شکل گراف معمای هشت برای حل مسئله

شکل گراف معمای هشت برای حل مسئله

ما این گراف رو میسازیم، و بعد وقتی که در یک ردیفی به گل رسیدیم، مسیر رسیدن به گل رو چاپ میکنیم.

کلاس گره یا Node

برای ذخیره ی هر گره یا node گراف، به یک کلاس نیاز داریم تا اطلاعات گره را در آن بریزیم. برای اینکار، باید بدانیم در هر node چه چیز هایی را باید ذخیره کنیم:

[list icon=”enotype-icon-checkmark” icon_color=”#5bd604″ icon_color_hover=”#1e73be” ]state: آرایه ی دو بعدی از وضعیت پازل.,action: اکشنی که مارا از وضعیت پدر، به وضعیت فعلی رسانده.,depth: عمق گره.[/list]

 

وضعیت شروع و وضعیت پایان

برای تعریف وضعیت شروع و وضعیت گل، از دو آرایه ی دو بعدی از نوع عدد استفاده میکنیم، و خانه ی خالی را با صفر نمایش میدهیم:

صف FrontHere و صف Checked

همانطور که میدانید ما برای حل مسئله به صفی برای ذخیره ی گره های Front Here و صفی برای ذخیره ی گره هایی که آنها را بررسی کرده ایم نیاز داریم. از صف Front Here یک گره انتخاب میکنیم و با استفاده از صف چک شده ها بررسی میکنیم که آیا قبلا به چنین گره ای رسیده ایم یا نه. هر کدام از این صف ها، لیستی از node ها هستند و آنها را به این صورت تعریف میکنیم:

اولین گره ای که در صف Front Here قرار میگیرد، وضعیت شروع است. بنابراین آن را به این صورت به صف Front Here اضافه میکنیم:

حل مسئله ی ۸ puzzle

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

ما باید یک کدی بنویسیم که تا وقتی که نرم افزار به جواب نرسیده، و صف Front Here هم خالی نشده، (یا حتی اینکه مثلا تعداد حرکت هایی که انجام داده از یه مقداری بیشتر نشده باشه)، یه حلقه ای رو اجرا کنه، و درون اون حلقه، ابتدا یک گره رو انتخاب، و بعد بررسی کنه که اگه گره انتخاب شده گل بود، مسیر رو چاپ، و در غیر این صورت، فرزندان اون رو به صف Front Here اضافه کنه. همین!

خب حالا میریم حلقه ی while رو بنویسیم، همونطور که از توضیحات بالا متوجه شدید، باید یه bool تعریف کنیم تا داشته باشیم به گل رسیدیم یا نه. و بعد از اینکه تعریف کردیم این حلقه رو مینویسیم:

در ابتدای این حلقه باید یک گره رو انتخاب کنیم. برای اینکار این تابع رو مینویسیم:

توی تابع بالا از تابعی به نام h استفاده شده که همون تابع Heuristic هست تا ببینیم حداعقل چند حرکت دیگه مونده تا به جواب برسیم. این مقدار رو ما اینطوری در نظر گرفتیم که چن تا خونه سر جاشون نیستند، یعنی در نظر گرفتیم که ما میتونیم یک کاشی رو برداریم و هر جایی که خواستیم بذاریمش. اینم تابع h ما:

حالا توی اولین خط حلقه مینویسیم:

حالا باید چک کنیم که وضعیت انتخاب شده گل هست یا نه، برای مقایسه ی دو وضعیت این تابع رو مینویسیم:

و درون حلقه این کد رو اضافه میکنیم:

تابع print_path رو بعدا توضیح میدم.

خب حالا باید بگیم که در غیر این صورت، فرزندان گره انتخاب شده رو اضافه به صف Front Here اضافه کن، البته در صورتی که قبلا اضافه نشده باشند.

برای اضافه کردن فرزندان اون گره هم باید چک کنیم که میشه خانه ی خالی رو به راست | چپ | بالا | پایین حرکت داد یا نه. اگه آره، باید بررسی کنیم که اونا قبلا دیده شدند یا نه، اگه نه، اون وضعیت رو به صف Front Here اضافه کنیم.

کد چک کردن اینکه میتونیم به راست | چپ | بالا | پایین حرکتشون بدیم یا نه:

و این هم کدی وضعیتی که توش خونه ی خالی یک وضعیت رو به سمت راست | چپ | بالا | پایین حرکت کرده رو بر میگردونه:

برای پیدا کردن این وضعیت ها باید جایی که خونه ی خالی یا همون ۰ قرار گرفته رو بدونیم. که اون رو اینطوری بدست میاریم:

حالا کدی که توی حلقه قرار میگیره این خواهد بود:

خب حالا یه خورده کد ریز دیگه مونده و تابع print_path که چیز خاصی ندارند. اینم کد نهایی پروژه:

 

 

رفتن به نوارابزار