تصوّر خوارزميات إيجاد المسار
خوارزمية ديكسترا وخوارزمية A* كلتاهما تجد أقصر مسار، لكنهما تستكشفان بطريقتين مختلفتين جدًا. يرسم هذا المستكشف البحث وهو يجري لتشاهد A* وهي تتجه مباشرة نحو الهدف بينما تنتشر ديكسترا في كل الاتجاهات.
كيف تستخدم هذه المحاكاة
- اختر بين A* وديكسترا والبحث بالعرض أولًا
- ارسم الجدران وحدّد نقطتي البداية والهدف
- اضبط سرعة الحركة
ما الذي تلاحظه
- ديكسترا تتوسّع في دائرة متساوية؛ أما A* فتمتد نحو الهدف
- كلتاهما تجد مسارًا بنفس الطول، لكن A* تفحص مربعات أقل بكثير
- الجدران التي تفرض التفافًا تجعل سلوك الخوارزميتين أقرب إلى التشابه
الفيزياء وراءها
توسّع خوارزمية ديكسترا العقد بترتيب بعدها عن البداية، فتضمن أقصر مسار لكنها تستكشف مساحة كبيرة لا علاقة لها بالهدف. أما A* فتضيف تقديرًا استدلاليًا للمسافة المتبقية يوجّه البحث نحو الهدف. وما دام ذلك التقدير لا يبالغ أبدًا، تظل A* ضامنة لأقصر مسار مع زيارة عقد أقل بكثير.