بحث A*
تجد خوارزمية ديكسترا أقصر طريق إلى الهدف، لكنها تبحث في كل الاتجاهات في آن واحد، حتى بعيدًا عن الهدف. يضيف بحث A* معلومة واحدة، تقديرًا لمدى بُعد الهدف، فإذا بالبحث يتجه إليه مباشرة.
الفكرة
حين تبحث عن طريق على خريطة، لا تستكشف الطرق المبتعدة عن وجهتك بالعناية نفسها التي تستكشف بها الطرق المؤدية إليها. وبحث A* يفعل الشيء نفسه. تحصل كل عقدة على درجة: المسافة من البداية حتى الآن، g، مضافًا إليها تقدير المسافة المتبقية، h. ويواصل البحث دائمًا من العقدة ذات أدنى درجة، فتأتي العقد الواقعة باتجاه الهدف أولاً.
خطوة بخطوة
أعطِ البداية المسافة 0 وضعها في طابور بالدرجة h(start). كرّر: خذ العقدة ذات أدنى درجة، واجعل مسافتها نهائية. إن كانت هي الهدف، فتوقف: تتبُّع العقد المحفوظة رجوعًا يعطي المسار. وإلا، فلكل جار لم يصبح نهائيًا، احسب مسافته عبر هذه العقدة. فإن كانت أقصر من مسافته حتى الآن، فاخفضها، وتذكّر هذه العقدة طريقًا إليه، وأعطِ الجار درجة تساوي مسافته الجديدة مضافًا إليها تقديره. وحين تتساوى درجتان، فإن أخذ العقدة ذات التقدير الأصغر أولاً يصل إلى الهدف أسرع عادةً.
مثال
لنأخذ البداية A والهدف D. طول A–B هو 2 وطول B–D هو 2، بينما طول A–C هو 1 وطول C–D هو 5. التقديرات بخط مستقيم إلى D هي 3 من A، و2 من B، و3 من C. تبدأ A بالدرجة 0 + 3 = 3. أخذ A يعطي B الدرجة 2 + 2 = 4 ويعطي C الدرجة 1 + 3 = 4. ومع التعادل يأخذ A* العقدة B، صاحبة التقدير الأصغر، وتعطي B العقدة D الدرجة 4 + 0 = 4. الآن لـD أدنى درجة مع أصغر تقدير، فتُؤخذ: أقصر مسار هو A → B → D، وطوله 4، أما C، التي تقود في الاتجاه الخاطئ، فلا تصبح نهائية أبدًا. كانت خوارزمية ديكسترا ستجعل C نهائية أولاً، لأنها أقرب عقدة إلى A.
التقدير الجيد
يجب ألا يكون التقدير أطول أبدًا من المسافة الحقيقية إلى الهدف؛ ويُسمى هذا التقدير مقبولاً، ومعه يجد A* دائمًا أقصر مسار. والخط المستقيم مقبول لأنه لا يوجد طريق أقصر من الخط المستقيم. وإذا كان التقدير أيضًا لا ينخفض أبدًا بأكثر من طول حافة من عقدة إلى التالية، فهو متسق، ولا تحتاج أي عقدة نهائية إلى إعادة النظر فيها. كلما اقترب التقدير من الحقيقة، قلّ عدد العقد التي يحتاجها A*. التقدير 0 مقبول لكنه عديم الفائدة: يصبح A* عندها خوارزمية ديكسترا. والتقدير الأكبر من اللازم يجعل A* أسرع لكنه قد يُفوّت أقصر مسار.
التاريخ والاستخدامات
نشر بيتر هارت ونيلز نيلسون وبيرترام رافائيل في معهد ستانفورد للأبحاث خوارزمية A* عام 1968، أثناء عملهم على شيكي، أحد أوائل الروبوتات المتنقلة. وكانت نسخهم السابقة تُسمى A1 وA2؛ وميّزت النجمة النسخة التي أثبتوا أنها مثلى. واليوم يحرّك A* الشخصيات حول العوائق في ألعاب الفيديو، ويخطط المسارات وحركات الروبوتات، ويحل ألغازًا مثل لغز الـ15، حيث يجمع التقدير بُعد كل بلاطة عن مكانها.
جرّبه بنفسك
افتح التطبيق واضغط «خطوة». الأرقام على الحواف هي أطوالها، وهي هنا تطابق أطوالها المرسومة، والخط المتقطع يُظهر التقدير بخط مستقيم إلى الهدف. ويسرد الطابور أسفل الرسم البياني العقد حسب الدرجة، الأدنى أولاً. وحين يصبح الهدف نهائيًا، يقارن سطر الحالة بين عدد العقد التي جعلها A* نهائية وعدد ما كانت خوارزمية ديكسترا ستحتاجه. جرّب هدفًا في زاوية بعيدة من رسم بياني كبير لترى أكبر فرق.
الأسئلة المتداولة
ماذا تعني النجمة في A*؟
وصف هارت ونيلسون ورافائيل أولاً خوارزميات سمّوها A1 وA2. وكانت A* («A ستار») النسخة التي أثبتوا أنها تجد أقصر مسار بأقل عدد من العقد الموسَّعة بين الخوارزميات المماثلة التي تستخدم التقدير نفسه، حين يكون التقدير متسقًا.
ما التعقيد الزمني لـA*؟
في أسوأ الحالات، مع تقدير عديم الفائدة، يؤدي A* العمل نفسه الذي تؤديه خوارزمية ديكسترا: O((V + E) log V) مع كومة ثنائية. ومع تقدير جيد لا يجعل نهائيًا إلا جزءًا صغيرًا من العقد، ولهذا هو سريع عمليًا.
ما الذي يجعل الدالة الاستدلالية جيدة لـA*؟
أن تكون سريعة الحساب، وألا تبالغ أبدًا في تقدير المسافة الحقيقية، وأن تكون أقرب ما يمكن إليها. على شبكة لا يمكن التحرك فيها إلا لأعلى وأسفل ويسار ويمين، تُعد مسافة مانهاتن خيارًا شائعًا؛ وعلى الخريطة، المسافة بخط مستقيم.
ماذا لو بالغت الدالة الاستدلالية في التقدير؟
عندها قد يعيد A* مسارًا ليس الأقصر، لأنه قد ينتهي قبل أن ينظر في الطريق الأفضل. وبعض البرامج تفعل ذلك عمدًا (A* الموزون) لمقايضة قليل من جودة المسار بكثير من السرعة.
هل أنت مستعد لتجربتها؟
افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.
جرّب بحث A*