خوارزمية البحث بأولوية الأفضل

خوارزمية البحث بأولوية الأفضل

بيانات عامّة

الصنف	خوارزمية حساب مسار — خوارزمية مخصصة لبيان — complete search algorithm (en) — admissible search algorithm (en)
بنية البيانات	بيان
مشتق من	jump point search (en)
المكتشف	Peter E. Hart (en) — Nils John Nilsson (en) — برترام رافائيل

الأداء

أسوء حالة	$O(|E|)=O(b^{d})$
أسوأ حالة تعقيد مكاني	$O(|V|)=O(b^{d})$

خوارزمية البحث بأولوية الأفضل، (بالإنجليزية: A* search algorithm)‏ هي تبسيط عن خوارزمية *A التي قدمها بيتر هارت في العام 1968. تستخدم هذه الخوارزمية الأدوات التالية:

1. قائمة (OPEN) للعقد التي ولدت وطبقت دالة الكشف (Heuristic Function) عليها ولكن لم تفحص بعد أي لم يتم توليد عقد تابعة منها. هذه القائمة هي من نوع صف تفضيل للأولوية (Priority Queue) حيث العقد ذات القيم الأعلى في دالة الكشف لها أولوية أكبر.
2. قائمة (CLOSED) للعقد التي فحصت وتم توليد العقد التابعة منها. هذه القائمة تبقى في الذاكرة لفحصها عند توليد عقد جديدة لمعرفة إن كانت مولدة سابقاً وتم المرور بها.
3. دالة الكشف (Heuristic Function) التي تخمن أحقية كل عقدة يتم توليدها. هذه الدالة تمكن الخوارزمية من البحث في الطرق الواعدة في الوصول للهدف أولاً.
4. الدالة g التي تقيس التكلفة للوصول من العقدة الابتدائية إلى العقدة الحالية. هذه الدالة تعطي قيم حقيقية وليست تقدير.
5. الدالة 'h التي تخمن التكلفة الإضافية للوصول من العقدة الحالية إلى العقدة الهدف. هي إذن قياس لتكلفة الوصول للحل أي العقد الأفضل تأخذ قيماً دنيا والعقد الأسوء تأخذ قيماً عليا، وليست قياس لجودة العقد أي العقد الأفضل تأخذ قيماً أعلى.
6. الدالة 'f التي تعرف كحاصل جمع للدالتين السابقتين أي ('g + h) و قيمتها إذن تمثل تخمين للوصول من الحالة الابتدائية إلى الحالة الهدف عن طريق العقدة الحالية.

الخوارزمية

1. نبدأ بالقائمة OPEN تحتوي فقط على عقدة للحالة الابتدائية قيمتها للدالة g صفر، إذن قيمة الدالة 'f هي 0 +'h أو فقط 'h , و القائمة CLOSED تكون خالية من العقد.
2. إلى أن نجد العقدة للحالة الهدف نكرر الإجراء التالي:

• نختار العقدة في القائمة OPEN ذات القيمة الأدنى للدالة 'f و نسميها العقدة الأفضل (BESTNODE) ثم ننقلها من القائمة OPEN إلى القائمة CLOSED.
• نفحص إن كانت BESTNODE هي العقدة الهدف، فإن كانت وجدنا الحل وإلا نولد العقدة التابعة (SUCCESSOR) لها.
• لكل عقدة تابعة نقوم بالآتي:

1. نجعل SUCCESSOR تشير رجعياً إلى BESTNODE , و هذه الإشارة ستساعد في استرجاع الطريق إن وجدنا العقدة الهدف.
2. نحسب g(SUCCESSOR) = g(BESTNODE) + the cost from BESTNODE to SUCCESSOR أي التكلفة للوصول لSUCCESSOR هو مقدار التكلفة BESTNODE إضافة للتكلفة من BESTNODE إلى SUCCESSOR .
3. إن كانت SUCCESSOR موجودة في القائمة OPEN , أي مولدة ولكن لم يتم توليد عقد منها، نسمي العقدة الموجودة في القائمة ب OLD و نقارن بين OLD و طريق الوصول إليها وبين SUCCESSOR و طريق الوصول إليها من BESTNODE ,أي نقارن قيمة g لكل منهما فإن كانت (g(OLD أقل لا نفعل شيئاً وإن كانت (g(SUCCESSOR أقل نجعل الرابط الرجعي ل OLD يشير إلى BESTNODE و نجعل القيمة الأدنى محفوظة في (g(OLD و نعدل قيمة (f'(OLD .
4. إن لم تكن SUCCESSOR في القائمة OPEN نرى أن كانت موجودة في CLOSED , أي تم فحصها سابقاً وإن كانت موجودة نسميها OLD و نكرر عملية المقارنة بين SUCCESSOR و OLD . هنا علينا أن ننقل التعديلات إلى توابع OLD و هذا معقد لأن OLD تشير إلى توابعها والتوابع بدورهم يشيرو إلى توابعهم إلى أن ينتهي كل فرع عند عقدة في القائمة OPEN لديها قيمة g مكافئة أو أقل أو أن لا يكون لديها توابع إي نستخدم خوارزمية المسح بأولوية العمق عند العقدة OLD و نغير قيمة g و 'f لكل عقدة نمر بها. بهذه الطريقة كل رابط رجعي لعقدة يشير إلى أفضل عقدة سابقة، ومن انتشار قيمة g باتجاه الأسفل أصبح من الممكن أن يصبح الطريق الذي نتبعه أفضل من الطريق من خلال العقدة السابقة الحالية فإن كانت الحالة هكذا نغير العقدة السابقة ونكمل المسح.

ملاحظات على الخوارزمية

• إن دور الدالة g يدعنا نختار أي عقدة نتوسع بعد ذلك ليس فقط على أساس قيمة 'h بل أيضاً على جودة الطريق إلى العقدة كان، فإن أردنا إيجاد الحل بأقل عدد من الخطوات نضع التكلفة من الانتقال من عقدة إلى عقدة كثوابت، وإن أردنا إيجاد الطريق الأرخص وكانت التكلفة مختلفة للانتقال من عقدة إلى أخرى فعلينا أن نأخذ هذه القيم بالاعتبار. إذن يمكن استخدام هذه الخوارزمية إن كنا مهتمين لإيجاد الطريق الأكثر تكلفة أو الأسرع وصولاً.
• المسافة من عقدة إلى الهدف الذي يقدر عن طريق الدالة 'h يعتمد على خوارزمية التخمين، فإن كانت القيمة أقرب للحقيقة فإن الخوارزمية ستلتقي حالاً بالهدف بطريقة مباشرة ولكن كلما ابتعدت 'h عن الواقع أي أصبحت قيمتها 0 اعتمد البحث أكثر على قيمة g. فإن كانت قيمة g هي ,0 أصبحت استيراجية البحث عشوائية. و إن كانت دائماً 1, أصبح البحث بأولوية العمق. أما إن كانت قيمة 'h معتدلة فإن طريقاً أمثل للهدف سيكتشف.
• الخوارزمية يمكن أن تمثل في أفضل حالة إذا طبقت باستعمال السم البياني (GRAPHS) , و يمكن أن تكون تبسط بتطبيق الرسم الشجري (TREES)إن لم نقم بفحص إذا ما كانت العقدة الجديدة في قائمة OPEN أو CLOSED, هذا يجعل توليد العقد أسرع ولكن يمكن أن ينتج عن توالي البحث عدة مرات إذا تكررت العقد.