سال انتشار: ۱۳۸۵

محل انتشار: دوازدهمین کنفرانس سالانه انجمن کامپیوتر ایران

تعداد صفحات: ۷

نویسنده(ها):

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

چکیده:

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