أفضل-البحث الأول هو خوارزمية بحث تستكشف مجموعة البيانات (Graph) من خلال توسيع نطاق العقدة الأكثر نجاحاً أي الأكثر مطابقة لقاعدة محددة يتم البحث بواسطتها.
يهودا بيرل وصف البحث الأول الأفضل من خلال تقدير تقدير نجاح تلك العقدة n "وذلك وفقاً لدالة تقييم إرشادية (heuristic evaluation function) والتي قد تعتمد بشكل عام على كل من : وصف n، وصف الهدف، المعلومات التي تم جمعها بواسطة البحث عن تلك النقطة، والأهم من ذلك كله، أي معلومات إضافية حول نطاق المعضلة (problem domain)"[1][2]
استخدم بعض الكتاب "البحث الأول-الأفضل" للإشارة على وجه التحديد إلى البحث بواسطة خوارزمية الكشف عن مجريات الأمور (heuristic) التي تحاول التنبؤ بمدى قرب نهاية الطريق من الحل، بحيث توسّع المسارات التي تعتبر أقرب إلى الحل للوصول إلى الحل بشكل أسرع. ويسمى هذا النوع من البحث بـ الأول-الأفضل الجشع[2] أو البحث الإرشادي النقي (pure heuristic search) - بحث الكشف النقي عن مجريات الأمور.[3]
عادةً ما يتم تنفيذ كفاءة اختيار أفضل مرشح ليتم توسيعه باستخدام طابور الأولوية (priority queue).
خوارزمية البحث بأولوية الأفضل هي مثال على البحث الأول-الأفضل (تعرف بـ A* بالإنجليزية)، أما الخوارزمية المعروفة بـ (B*) فهي تستخدم غالباً لإيجاد المسارات في البحث الإندماجي (combinatorial search). ولا تعتبر أي من أ* أو ب* خوارزمية بحث أول-أفضل جشع حيث أن كلاهما لا تتناغمان مع المسافة المقطوعة من البداية مجموعة مع المسافات المقدرة نحو الهدف وهي صفة خوارزمية البحث الأول-الأفضل الجشع.
الخوارزمية
خوارزمية البحث الأول-الأفضل تكون على النحو التالي.[4]
OPEN = [initial state] while OPEN is not empty or until a goal is found do 1. Remove the best node from OPEN, call it n. 2. If n is the goal state, backtrace path to n (through recorded parents) and return path. 3. Create n's successors. 4. Evaluate each successor, add it to OPEN, and record its parent. done
هذا الإصدار من الخوارزمية ليس كاملاً، أي أنها لا تجد دائماً مساراً ممكناً بين عقدتين، وحتى لو كان هناك مسار. فعلى سبيل المثال، قد يعلق في حلقة ما إذا وصلها عند نهاية مغلقة، ويحدث هذا عندما تكون العقدة الوحيدة التي تخلف (ن) هي أصلها. وبالتالي ترجع إلى أصلها، وهكذا يتم إدراج الخلف الواقع في النهاية المغلقة في قائمة م مرة أخرى.
النسخة التالية تمتد الخوارزمية إلى استخدام قائمة إضافية غ (ملاحظة م = مفتوحة، غ=مغلقة) وهي قائمة تحتوي على كافة العقد التي تم تقييمها ولن يتم النظر فيها مرة أخرى. وهذا سوف يجنب أي عقدة يجري تقييمها مرتين، وبالتالي فإنه لن يخضع لحلقات لانهائية.
OPEN = [initial state] CLOSED = [] while OPEN is not empty do 1. Remove the best node from OPEN, call it n, add it to CLOSED. 2. If n is the goal state, backtrace path to n (through recorded parents) and return path. 3. Create n's successors. 4. For each successor do: a. If it is not in CLOSED and it is not in OPEN: evaluate it, add it to OPEN, and record its parent. b. Otherwise, if this new path is better than previous one, change its recorded parent. i. If it is not in OPEN add it to OPEN. ii. Otherwise, adjust its priority in OPEN using this new evaluation. done
المراجع
- Pearl, J. Heuristics: Intelligent Search Strategies for Computer Problem Solving.
- Russell, Stuart J.; Norvig, Peter (2003), Artificial Intelligence: A Modern Approach (2nd ed. نسخة محفوظة 30 يوليو 2017 على موقع واي باك مشين.
- Korf, Richard E. (1999).
- http://www.macs.hw.ac.uk/~alison/ai3notes/subsubsection2_6_2_3_2.html Best First Search