الگوریتم جستجوی *a در مسئله 8 پازل
 

سلام
امکان داره الگوریتم جستجوی *a در مسئله 8 پازل توضیح بدین ؟ من در مورد این الگوریتم از کتاب راسل مطالعه کردم و مثالی که برای پیدا کردن کوتاه ترین مسیر برای شهر بخارست زده بود متوجه شدم ولی نمیدونم این الگوریتم تو 8 پازل چجوری پیاده سازی کنم !؟!؟!؟ اگه امکان داره راهنماییم کنید
متشکرم

این مثال هم عین همون مثال بخارست هست. اگر اون رو فهمیدید این هم ساده است.
در این مثال (پازل 8)

بخارست ما ، رسیدن به چیدمان هدفه که با شکل نشون داده می شه در هر مسئله خاص.
ممکنه ترتیب صعودی از 1 تا 8 به ترتیب از بالاترین ردیف تا پایین ترین ردیف ملاک باشه. به هر جهت مساله حتما حال هدف رو می ده.

شهر آراد در این مثال حال شروع هست، که این هم در صورت مساله داده می شه.

شهرهای بین راه، هر کدوم یک چیدمان هستند که نه هدف هستند و نه حال شروع.

هیورستیک (تخمین هر حالت تا هدف) از دو راه پیشنهاد شده در کتاب اسل (گرچه هیورستیک های خفن تری هم هست که باید سرچ کنید در اینترنت اگر علاقه من هستید) . این دو هیورستیک به شرح زیر هستند:

هیورستیک 1: تعداد خانه هایی (شماره هایی) که در جای صحیح خود (با توجه به حال هدف بخارست) نیستند.
هیورستیک 2: فاصله منهتن (جمع فواصل افقی و عمودی) هر خانه (شماره) نسبت به حالت هدف(بخارست).

حالا بای تابع f=g+h رو مثل مثال بخارست برای هر حالت تشکیل بدید و با اینتخاب کمترین f در هر حالت مسیر بهینه رسیدن از حالت شروع (آراد) به هدف (بخارست) رو پیدا کنید.

موفق باشید

متشکر از پاسخ شما
حالت شروع زیر در نظر بگیرید
اینجا تابع f برای 8 و 3 بررسی میکنیم . درسته ؟ واسه هر کدوم f کمتر باشه اونو حرکت میدیم ؟اگه f واسه هر 2 برار باشه چیکار میکنیم ؟
آیا برای 8 :
h =2 , g =4 هست ؟
تو این مسئله g چجوری باید حساب کنم ؟
متشکرم

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

اما در هر صورت الگوریتم *a در شرایط مساوی، اولین سمت چپ ترین گره رو بسط می ده (این یه قرارداده)
پس بسته به این که این دو حالت مساوی فرزند کدام گره ها هستند و با توجه به اینکه اول پدر کدوم شون بسط داده شده، اون گره سمت چپ تر و مقدم تره.
از طرفی چون الگورتیم همیشه راه بهینه و هدف بهینه رو پیدا می کنه پس نیاز نیست نگران این باشید.

اگر نیازمند تحلیل دقیق تر هستید، شکل مورد نظرتون رو اینجا بذارید تا به کمک دوستان بحث کنیم در موردش.

موفق باشید

سلام
ببخشید یادم رفته بود عکس بزارم , پست قبلی وبرایش شد

ببینید
برای محاسبه این مساله نیاز به حالت شروع و حالت هدف دارید
شما یه عکس گذاشتید فقط.
ضمن اینکه برای محاسبه g و h در هر حالت نیاز به حالت جاری هم هست (یعنی سه عکس)

عکس قبلی که گذاشتم حالت شروع هست . حالت هدف هم ب این شکل هست
123
456
78b
bهمون خالی هست
متشکرم

f فاصله تا خانه هدف هست و g تعداد خانه های جابجا شده .
در اولین مرحله خانه 8 جابجا میشه و پازل به شکل زیر در میاد
126
45b
738
در این مرحله چون 5 در خانه هدف هست f برای 8 و 6 بررسی میکنم و 6 جابجا میشه
در این مرحله پازل به شکل زیر در میاد
12b
456
738
در این مرحله چیکار باید کرد ؟ چون 2 و 6 در خانه هدف هستن ولی f2 = 0 , F6 = 1
آیا برای خانه ای که در هدف هست باید F حساب کنیم ؟
متشکرم

ببینید، شما باید مقدار h رو برای هر حالت حساب کنید که می شه مجموع فاصله منهتن برای یک یک خانه ها.

هر خانه برای خودش f نداره بلکه یک f برای همه خانه ها در یک حالت مشخص (چه شروع، چه هدف، چه میانی) می تونید حساب کنید که این عدد از جمع g و h حاصل میشه.

g می شه هزینه اومدن به این حالت (تعداد حرکات)
h می شه فاصله جمع فواصل منهتن برای یک یک خانه ها

جمع این دو مقدار در هر حالت که باشید، f شماست.

امکان داره 2 مرحله از اون حالت شروع توضیح بدین چجوری جلو میرین ؟!؟!
متشکرم