mahdi68

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

bijibuji

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

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

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

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

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

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

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

موفق باشید

mahdi68

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

عكس ضميمه

Untitled.jpg (17.2 كيلو بايت, 112 نمايش)

bijibuji

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

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

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

موفق باشید

mahdi68

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

bijibuji

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

mahdi68

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

mahdi68

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

bijibuji

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

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

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

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

mahdi68

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