ما معنى Best-First Search في الخوارزميات وهياكل البيانات؟ شرح مبسّط
البحث الأفضل أولًا (Best-First Search) هو عائلة من خوارزميات البحث في الرسوم البيانية (Graphs) تختار في كل خطوة العقدة "الأكثر وعدًا" للتوسّع بدلًا من استكشاف كل الاتجاهات بالتساوي. الفكرة الجوهرية بسيطة: نعطي كل عقدة درجة رقمية عبر دالة تقييم تُسمّى f(n)، ثم نوسّع دائمًا العقدة صاحبة أفضل درجة. بهذا نوجّه البحث نحو الهدف بسرعة أكبر من الخوارزميات العمياء مثل البحث بالعرض (BFS) أو بالعمق (DFS) التي لا تملك أي "حدس" عن اتجاه الهدف.
كيف تعمل الخوارزمية؟
الأداة التي تجعل هذا ممكنًا هي طابور الأولوية (Priority Queue)، وغالبًا يُنفَّذ كـ Min-Heap يُخرج دائمًا العقدة صاحبة أقل قيمة f(n). الخطوات العملية:
- ضع عقدة البداية في قائمة مفتوحة (Open List) هي طابور الأولوية.
- اسحب من الطابور العقدة صاحبة أفضل قيمة f(n).
- إن كانت هي الهدف، توقّف وأعِد المسار.
- وإلا، وسّعها: احسب f(n) لكل جار لها وأضِفه إلى الطابور.
- انقل العقدة الموسّعة إلى قائمة مغلقة (Closed List) حتى لا تُعالَج مرتين.
- كرّر من الخطوة 2 حتى تصل إلى الهدف أو يفرغ الطابور (أي لا يوجد حل).
القائمة المغلقة مهمة عمليًا: بدونها قد تدخل الخوارزمية في حلقات لا نهائية داخل الرسوم البيانية التي تحتوي دورات.
دالة التقييم: هنا يقع أشهر خلط
كثير من الشروحات تخلط بين نوعين مختلفين تحت اسم واحد، وهذا هو الفرق الذي يجب أن تحفظه:
- البحث الأفضل أولًا الجشِع (Greedy Best-First): يستخدم f(n) = h(n) فقط، أي التكلفة التقديرية المتبقية إلى الهدف (الدالة الاستكشافية / Heuristic). سريع جدًا لكنه "قصير النظر": يندفع نحو ما يبدو قريبًا من الهدف وقد يقع في مسار طويل أو مسدود، ولا يضمن أقصر طريق.
- خوارزمية A*: تستخدم f(n) = g(n) + h(n)، حيث g(n) هي التكلفة الفعلية المقطوعة من البداية حتى العقدة الحالية، وh(n) هي التقدير المتبقي. بجمع الماضي (g) مع المستقبل المتوقّع (h) توازن A* بين السرعة ودقة المسار.
بعبارة أخرى: A* ليست شيئًا منفصلًا عن Best-First، بل هي أشهر حالاته وأكثرها استخدامًا. الوصف الشائع بأن "Best-First يستخدم f = g + h" غير دقيق؛ فذلك تعريف A* تحديدًا، أما العائلة الأوسع فتتغيّر دالتها حسب النوع.
Greedy Best-First أم A*؟
| المعيار | Greedy Best-First | خوارزمية A* |
|---|---|---|
| دالة التقييم | f(n) = h(n) | f(n) = g(n) + h(n) |
| ضمان أقصر مسار | لا | نعم (بشرط أن يكون h مقبولًا) |
| السرعة | أسرع غالبًا | أبطأ قليلًا لكن أدق |
| استهلاك الذاكرة | أقل | أعلى (يحتفظ بمعلومات أكثر) |
| الأنسب لـ | حل سريع "مقبول" | مسار مثالي مضمون |
المقصود بـ"h مقبول (Admissible)" أن التقدير لا يبالغ أبدًا في التكلفة الحقيقية المتبقية؛ عند تحقّق هذا الشرط تضمن A* الوصول إلى المسار الأقصر.
أين تُستخدم عمليًا؟
- ألعاب الفيديو والخرائط: إيجاد طريق شخصية اللعبة بين نقطتين حول العوائق، وكذلك تطبيقات الملاحة التي تحسب أقصر طريق بين مدينتين.
- الذكاء الاصطناعي والتخطيط: التنقّل في فضاء حالات كبير لاتخاذ قرار، مثل حلّ الألغاز أو جدولة المهام.
- الروبوتات: تخطيط حركة الذراع أو المركبة في بيئة فيها عوائق.
نصيحة عملية وخطأ شائع
الخطأ الأكثر شيوعًا هو الاعتقاد بأن أي بحث "أفضل أولًا" يعطي دائمًا أقصر مسار. هذا صحيح لـ A* بشرط الدالة المقبولة، لكنه غير صحيح للنسخة الجشعة. إن كنت تحتاج ضمان المسار الأمثل فاستخدم A*، وإن كنت تحتاج فقط حلًا سريعًا "جيدًا بما يكفي" فالنسخة الجشعة أخف.
النصيحة الذهبية عند البناء العملي: جودة الدالة الاستكشافية h(n) هي كل شيء. دالة ضعيفة تجعل A* بطيئة كأنها بحث أعمى، ودالة ذكية (مثل مسافة مانهاتن في الشبكات المربّعة) تختصر الحساب بشكل هائل. ابدأ دائمًا بدالة بسيطة صحيحة ثم حسّنها بالقياس، لا بالتخمين.
الأسئلة الشائعة
هل Best-First Search و A الشيء نفسه؟* ليسا متطابقين. A* حالة خاصة من عائلة Best-First تستخدم f(n) = g(n) + h(n). العائلة أوسع وتشمل النسخة الجشعة التي تستخدم h(n) فقط.
ما الفرق بينها وبين خوارزمية دايكسترا (Dijkstra)؟ دايكسترا تعتمد على g(n) فقط (التكلفة الفعلية) دون دالة استكشافية، لذا تستكشف بالتساوي في كل الاتجاهات. يمكن اعتبار A* نسخة "موجَّهة" من دايكسترا تضيف تقديرًا للاتجاه نحو الهدف.
هل تضمن الخوارزمية الوصول إلى حل دائمًا؟ ليس بالضرورة. النسخة الجشعة قد لا تكون كاملة (Complete) في بعض الحالات، بينما A* كاملة ومثلى إذا كانت الدالة الاستكشافية مقبولة وكان فضاء البحث محدودًا.
ما هيكل البيانات الأساسي المستخدم؟ طابور الأولوية (Priority Queue) المنفَّذ عادةً عبر Min-Heap، بالإضافة إلى قائمة مغلقة لتتبّع العقد المعالَجة ومنع تكرارها.