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

إن خوارزمية البحث بأولوية الأفضل هي تبسيط عن خوارزمية *A التي قدمها Peter Hart في العام 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, هذا يجعل توليد العقد أسرع و لكن يمكن أن ينتج عن توالي البحث عدة مرات إذا تكررت العقد.

ملف:Do while cyklus.png

هذه بذرة مقالة عن برمجيات الحاسوب تحتاج للنمو والتحسين، فساهم في إثرائها بالمشاركة في تحريرها.

cs:A* de:A*-Algorithmus A* search algorithm]] es:Algoritmo de búsqueda A* fi:A*-algoritmi fr:Algorithme A* hy:Ա* it:A* ja:A* ko:A* 알고리즘 nl:A*-algoritme pl:Algorytm A* pt:Algoritmo A* ru:Алгоритм поиска A* th:ขั้นตอนวิธีเอสตาร์ uk:Алгоритм пошуку A* vi:Giải thuật tìm kiếm A* zh:A*搜寻算法