الگوریتم جستجوی *a در مسئله 8 پازل - صفحه 2 - Artificial Intelligence

bijibuji · ۰۹-۱۶-۱۳۸۹, ۱۲:۵۱ قبل از ظهر

حالت اولیه (شروع):

حالت هدف:

فرض کنید که حالت فعلی به این شکله:

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

با چند حرکت از حالت اولیه به حالت جاری رسیدیم؟ (این رو نمی شه یهو واسه یه حالت حساب کرد. بلکه باید به تدریج که مراحل رو جلو میاید، یکی یکی حساب کنید و در حافظه نگهداری کنید. اما در این مثال چون ساده است، می شه فهمید که با چند حرکت از حالت اولیه به اینجا رسیدیم.)

g=4

بعد از اون می ریم سراغ محاسبه h که هیورستیک یا تابع اکتشافی است.
تخمیی که به کار می خوایم ببریم فاصله منهتنه. یعنی هر خانه، نسبت به جایی که باید باشه چند خونه اختلاف داره. به عبارت بهتر با چند حرکت می تونیم ببریم بذاریم اش سر جاش، اگر هیچ عدد دیگه ای در بازی نباشه و راه کاملا هموار باشه. برای تک تک خانه ها (هر 8 تا) باید حساب کنیم و آخرش با هم جمع بزنیم.

h= فاصله منهتن خانه شماره 1 + فاصله منهتن خانه شماره 2 + فاصله منهتن خانه شماره 3 + فاصله منهتن خانه شماره 4 + ...

پس خواهیم داشت:

h=2+2+0+0+0+1+1+1=7

خوب حالا مقدار تابع ارزیابی f برای حالت جاری محاسبه شد:

f=g+h=4+7=11

اگر مقدار f رو برای حالت های دیگه حساب کردیم و کمترین شون این مقدار (یعنی 11) بود، باید حالت های دیگه رو بی خیال شیم و حالت جاری رو بسط بدیم.

امیدوارم متوجه شده باشید.

mahdi68 · ۰۹-۱۸-۱۳۸۹, ۱۲:۱۳ قبل از ظهر

متشکرم دوست عریز
من تونستم مثال بالا با روشی که گفتین حل کنم
ولی در یک مثال دیگه که f برابر دارند نمیدونم باید چیکار کنم !

نقل قول:

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

این مثال در نظر بگیرین :
حالت شروع :
54b
618
732
حالت هدف :
123
456
78b

در اولین مرحله 2 گره زیر ایجاد میشه که f هر دو برابر 18 هست
548
61b
732
---------------
5b4
618
732

حالا اگه طبق گفته شما بخواهیم سمت چپ ترین گره انتخاب کنیم کدوم یک باید انتخاب بشه ؟ چون هر دو میشه به عنوان گره چپ در نظر گرفت

متشکرم

bijibuji · ۰۹-۱۸-۱۳۸۹, ۱۱:۵۰ قبل از ظهر

شما باید مفاهیم هوش مصنوعی رو پله پله یاد بگیرید

من فرض کردم شما فصل جستجوهای ناآگاهانه (اول سطح، اول عرض، هزینه یکنواخت ...) رو بلد هستید.
درصورتیکه با نقشه رومانی سروکار داشته باشید، اولین سمت چپ ترین گره، شهری است که روی نقشه در سمت چپ آراد قرار داشته باشه به لحاظ جغرافیایی.
درمورد پازل 8، این به شیوه بسط شما بستگی داره. مهم اینه که شما یه شیوه استاندارد بسط داشته باشید.

مثلا اگر خانه های مجاور یک مربع خالی (b) حداکثر چهار خانه هستند، شما با خودتون قرارداد کنید همیشه کوچکترین خانه رو با با خانه خالی جابجا کنید.

یا اینکه در جهت عقربه های ساعت از ساعت 12 شروع کنید و بعد ساعت 3 و بعدش 6 و بعدش ساعت 9 رو .
تنها چیز که مهمه، رعایت یک استاندارد در بسط دادن هست. چن در نهایت الگوریتم *A راه حل بهینه رو خواهد یافت. پس کافیه شیوه کار شما ثابت باشه تا اگر شخص دیگه ای خواست مراحل شما رو دنبال کنه بتونه این کار رو انجام بده.

در مورد مثالی که زدید مثلا اگر با استاندارد بسط از ساعت 12 شروع کنیم، ابتدا حالت دوم رخ می ده، یعنی اول خانه شماره 8 و بعدش خانه شماره 4 می تونه بسط داده شه (به عنوان فرزندان حالت جاری)

موفق باشید

worldcomputer · ۱۰-۱۳-۱۳۹۰, ۰۶:۱۵ بعد از ظهر

با سلام خدمت دوستان اگه ميشه الگوريتم *a رو براي پازل خوب تشريح كنيد من اينطوري متوجه نشدم اصلا f,g چيه فقط يك مرحله ش حتي بنويسيد هم متوجه ميشم فقط زود باشه فداتون يا علي

shervinmina · ۰۲-۱-۱۳۹۱, ۰۵:۳۶ بعد از ظهر

سلام
كسي برنامه آراد به بخارست را به الگوريتم *a نداره؟
ممنون ميشم كمك كنيد.

sari-1369 · ۰۹-۱۵-۱۳۹۱, ۰۱:۰۸ قبل از ظهر

سلام خدمت دوستان عزیز

من میخوام پازل 8 رو به روش A* حل کنم . یه کدی هم (گرچه خیلی مبتدیا) با زبون vb.net نوشتم .
اما جواب نمیگیرم . نمیدونم کلا الگوریتم رو اشتباه متوجه شدم یا اینکه کد هام مشکل دارن . میخوام اگر امکانش هست شما اساتید یه نگاهی بهش بندازید.
و یه مورد دیگه اینکه اول با تابع بازگشتی خواستم بنویسم اما خیلی زود به استک اورفلو میرسیدم این بود که که فعلا توی یه حلقه گزاشتم و نود های گذشته رو نگه نمیدارم.

کد رو ضمیمه کردم