SAWA*: An Annealing-Based Heuristic Search

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

کلیدواژه ها:

الگوریتم های جستجو ، Sliding-tile Puzzle ، WA* ، BFS ، A* ، برج های هانوی