تمرین شماره 1

یک برنامه (به زبان C یا Java) با الگوریتم جستجوی عمومی بنویسید که بازی 8 را به روش جستجو انجام می دهد. به این ترتیب که کاربر یک حالت ورودی و یک حالت هدف از بازی 8 را به برنامه می دهد. سپس برنامه از کاربر می پرسد که به کدامیک از استراتژی های انتخاب (گرهی در حافظه برای باز کردن فرزندانش) مساله را باید حل کند.

1. استراتژی انتخاب عمقی
2. استراتژی انتخاب سطحی
3. استراتژی انتخاب حریصانه کشف کنندگی با تابع کشف کنندگی h1
4. استراتژی انتخاب حریصانه کشف کنندگی با تابع کشف کنندگی h2
   
5. استراتژی انتخاب A* با تابع کشف کنندگی h1
6. استراتژی انتخاب A* با تابع کشف کنندگی h2
7. استراتژی انتخاب کمترین هزینه (با فرض اینکه هزینه حرکت های افقی دو برابر هزینه حرکتها عمودی باشد)
8. استراتژی انتخاب تکراری عمیق شونده
   

پس از اینکه کاربر گزینه را انتخاب کرد. برنامه در خروجی

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

توابع کشف کنندگی h1 و h2 بصورت زیر هستند.

h1(s)= تعداد مربعهایی که در سر جای خودشان با توجه به حالت هدف هستند

h2(s)=تعداد گامهایی که می تواند به حالت هدف رسید با این آزادی که بتوان از روی مربعها بصورت افقی و عمودی رد شد