الگوریتم جست و جوی A* - هفت خط کد انجمن پرسش و پاسخ برنامه نویسی

وبـــلاگ هــفت خــط کــد


آموزش های برنامه نویسی
۱۲۰ نفر آنلاین
۲ عضو و ۱۱۸ مهمان در سایت حاضرند

الگوریتم جست و جوی A*

+2 امتیاز
77 بازدید
جست و جوی *A در گراف به چه شکل هست ؟؟

تا اون جایی که من فهمیدم مثل Bfs هست ولی با این تفاوت که باید از یک تابع برای گسرش node ها استفاده کرد ؟

حالا این تابع چطور حساب میشه ؟ بعد آیا این الگوریتم optimal هم هست ؟
سوال شده آبان 11, 1393  بوسیله ی َAI (امتیاز 304)   1 3 26
این جا این الگ.وریتم رو توضیح داده: http://fa.wikipedia.org/wiki/%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85_%D8%AC%D8%B3%D8%AA%D8%AC%D9%88%DB%8C_%D8%A2*
در نسخۀ انگلیسشی هم در مورد optimality توضیح داده.

1 پاسخ

+1 امتیاز
الگوریتم UCS که توی این صفحه توضیح داده شده رو در نظر بگیرید :  الگوریتم جست و جوی ucs
 
حالا کافیه که داخل شبه کد ucs علاوه بر در نظر گرفتن مسیر تا راس مورد برای مرتب کردن  priority queue  که برای frontier استفاده شده  از یک تابع هم استفاده کنید که طول تخمینی از اون راس تا راس هدف رو بهمون میده و این مقدار رو با path cost جمع بزنید . 
 
 
 اگر این تخمینی که زده میشه "همیشه " مقدارش از مقدار واقعی کمتر باشه الگوریتم optimal هست .
 
و هر چه هم این تخمین نزدیکتر باشه به مقدار واقعی برای search space های بزرگ سریع تر به جواب میرسیم .
 
 
این که این تابع چطوری باید باشه هم کاملا بستگی به محیط جست و جو داره مثلا فرض کنید که داخل یک نقشه می خواهید از *A استفاده کنید می تونید از طول مسیر مستقیم بین 2 شهر استفاده کنید و چون مسیر مستقیم همیشه یا برابر با مقدار واقعی هست یا کمتر هست optimal هم میشه . 
 
یا مثلا در  8 puzzle برای تابع مورد نظر از manhatan distance  بین هر راس با محلی که قراره راس قرار بگیره میشه استفاده کرد .
 
 
پاسخ داده شده آبان 18, 1393 بوسیله ی BlueBlade (امتیاز 15,712)   13 16 85
...