bijibuji

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



حالت هدف:


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


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

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

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

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

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

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

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

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

عكس ضميمه

	8_puzzle_start_state_a.png (8.5 كيلو بايت, 294 نمايش)
	8_puzzle.png (10.5 كيلو بايت, 271 نمايش)
	8_puzzle_goal_state_a.png (8.5 كيلو بايت, 265 نمايش)

mahdi68

متشکرم دوست عریز
من تونستم مثال بالا با روشی که گفتین حل کنم
ولی در یک مثال دیگه که f برابر دارند نمیدونم باید چیکار کنم !
این مثال در نظر بگیرین :
حالت شروع :
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 نوشتم .
اما جواب نمیگیرم . نمیدونم کلا الگوریتم رو اشتباه متوجه شدم یا اینکه کد هام مشکل دارن . میخوام اگر امکانش هست شما اساتید یه نگاهی بهش بندازید.
و یه مورد دیگه اینکه اول با تابع بازگشتی خواستم بنویسم اما خیلی زود به استک اورفلو میرسیدم این بود که که فعلا توی یه حلقه گزاشتم و نود های گذشته رو نگه نمیدارم.

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

فايل ضميمه

	code.rar (1.4 كيلو بايت, 42 نمايش)
	Eight-VB.zip (89.8 كيلو بايت, 42 نمايش)