SAWA*: An Annealing-Based Heuristic Search

سال انتشار: 1385
نوع سند: مقاله کنفرانسی
زبان: انگلیسی
مشاهده: 2,613

استخراج به نرم افزارهای پژوهشی:

لینک ثابت به این مقاله:

شناسه ملی سند علمی:

ACCSI12_287

تاریخ نمایه سازی: 23 دی 1386

چکیده مقاله:

در این مقاله الگوریتم جدید Simulated Annealing Weighted A* که شکل کامل شدة الگوریتم مشهور A* می باشد ارائه خواهد شد. در صورتیکه در الگوریتمA* از یک تابع Admissible به عنوان Heuristic ، استفاده شود A* جواب بهینه را پیدا خواهد کرد . پیدا کردن جواب بهینه برای مسائلی نظیر ۲۴ پازل و حالاتی از ۱۶ هانوی توسط روشA* ممکن نیست. در روش WA* با ارائة یک تابع Inadmissible یک جواب زیربهینه ١ پیدا خواهد شدWA* یک جواب زیربهینه را با کاهش تعداد گرههای ٢ کمتر و در زمان سریعتر پیدا خواهد کرد. ایدة اصلی این مقاله یک الگوریتم بر پایة روشAnnealing می باشد که مقدار تابع Heuristic به تدریج از حالت Admissible به Inadmissibleمیل خواهد کرد. این روند باعث میگردد تا SAWA* جواب بهتر با تولید گرههای کمتر را پیدا کند.

نویسندگان

مهدی صمدی

دانشجوی رشته مهندسی کامپیوتر ، دانشگاه شیراز ، دانشکده مهندسی ، بخشی

زهره عظیمی فر

استادیار دانشگاه شیراز، دانشکده مهندسی ، بخش مهندسی و علوم کامپیوتر