بحث A*
ديكسترا مع حسّ بالاتجاه. تضيف إلى تكلفة كل مكان تقديرًا للتكلفة المتبقية، فتجرّب أولًا الأماكن التي تبدو الأقرب إلى الهدف.
- الوقت O((V + E) log V)
- الذاكرة O(V)
- طابور أولوية
طابور الأولوية: طابور يمر فيه الأرخص أولًا، لا من وصل أولًا.
مصطلحات أخرى في هذه الصفحة
- التكلفة: ثمن الحركة. في المتاهة تكلف الأرض 1 والوحل 3 والماء 9؛ وفي الرسم البياني هي الرقم على الحافة.
- التقدير (h): تخمين للتكلفة المتبقية. تبقى A* دقيقة فقط إذا لم يكن التخمين مرتفعًا أبدًا.
- إرخاء الحافة: التحقق مما إذا كان المرور عبر المكان الحالي يعطي جارًا تكلفة أقل، واعتمادها إن كان كذلك.
جرّب هذا: اختر الحقل المفتوح وبدّل بين ديكسترا وA*: كلاهما يجد طريقًا بالتكلفة نفسها، لكن A* تأخذ من الطابور خلايا أقل بكثير.
كيف يعمل
تعمل A* مثل ديكسترا، لكنها ترتّب الطابور حسب f = التكلفة حتى الآن + h، حيث تقدّر h التكلفة المتبقية. في المتاهة، h هي عدد الحركات حتى M مع تجاهل الجدران والوحل؛ وفي الرسم البياني، المسافة المستقيمة مقسومة على 10. ما دامت h لا تبالغ أبدًا، يكون الطريق الذي لدى A* عند أخذ الهدف هو الأرخص، تمامًا كما في ديكسترا. كلما كان التقدير أفضل، قلّت الأماكن التي يجب فحصها.
متى يكون خيارًا جيدًا
استخدم A* عندما تبحث عن هدف واحد وتستطيع تقدير بعده: إيجاد الطريق في الألعاب، والروبوتات، ومخططات المسارات على الخريطة. مع h = 0 تكون ديكسترا نفسها. التقدير الذي قد يبالغ يجعل A* أسرع لكنه قد يفوّت عليك أرخص طريق.