إن خوارزمية البحث A* هي طريقة شعبية لتقصي المسارات والرسوم البيانية تستخدم في مختلف التطبيقات مثل الروبوتات، وتطوير اللعب، ونظم الملاحة، وهي تجمع بين سمات البحث الموحد التكلفة والبحث عن أفضل البحث في البداية، مما يجعله كفؤا لإيجاد أقصر طريق في الرسوم البيانية المثقلة، وهذا الدليل يوفر نهجا تدريجيا لتنفيذ " ألف " مع أمثلة عملية.

فهم الـ * ألف *

ألف* يجد الخوارزمي أقصر طريق من عقد البداية إلى عقد الهدف بالنظر في التكلفة للوصول إلى عقدة معينة والتكلفة المقدرة لبلوغ الهدف من ذلك العقد، وهو يستخدم كشوفا ذا أولوية لاستكشاف العقد بأقل تكلفة مقدرة، وهو مبلغ التكلفة الفعلية والتقدير التراكمي.

تنفيذ خطة العمل

متابعة هذه الخطوات لتنفيذ ألف* بلغة برمجة مثل بايتون:

  • ابدأي القائمة المفتوحة مع عقدة البداية والقائمة المغلقة فارغة
  • حتى تكون القائمة مفتوحة فارغة:
  • إزالة العقد بأقل تكلفة من القائمة المفتوحة.
  • إذا كان هذا العقد هو الهدف، إعادة بناء الطريق وإنهاء.
  • وإلا، تولد جيرانها وتقيم كل منها:
  • حساب التكلفة للوصول إلى كل جار وتقدير المسافة المتبقية إلى الهدف باستخدام وظيفة تهيوية.
  • وإذا لم يكن أحد الجيران مدرجا في القائمة المفتوحة أو المغلقة، يضافها إلى القائمة المفتوحة بتكلفة إجمالية.
  • حرّك العقد الحالي إلى القائمة المغلقة.

نموذج عملي

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

موجز

ويتطلب تنفيذ " ألف " فهم عناصره الأساسية: القائمة المفتوحة، والقائمة المغلقة، وحسابات التكاليف، والوظيفة التعاقبية، وباتباع عملية الخطوة الأولى وتطبيقها على أمثلة عملية، يمكن للمطورين أن يدمجوا بشكل فعال ألف* في تطبيقاتهم من أجل التوصل إلى حلول أفضل.