بحث بتفضيل الأولية

البحث بتفضيل الأولية  خوارزمية بحث تستكشف مجموعة البيانات (Graph) من خلال توسيع نطاق العقدة الأكثر نجاحاً أي الأكثر مطابقة لقاعدة محددة يتم البحث بواسطتها.

يهودا بيرل وصف البحث بتفضيل الأولية بتقدير نجاح تلك العقدة n «وذلك وفقاً لدالة تقييم إرشادية (heuristic evaluation function)  والتي قد تعتمد بشكل عام على كل من: وصف n، وصف الهدف، المعلومات التي تم جمعها بواسطة البحث عن تلك النقطة، والأهم من ذلك كله، أي معلومات إضافية حول نطاق المعضلة (problem domain)»Pearl, J. Heuristics: Intelligent Search Strategies for Computer Problem Solving.Russell, Stuart J.; Norvig, Peter (2003), Artificial Intelligence: A Modern Approach (2nd ed. 

استخدم بعض الكتاب «البحث بتفضيل الأولية» للإشارة على وجه التحديد إلى البحث بخوارزمية الكشف عن مجريات الأمور (heuristic) التي تحاول التنبؤ بمدى قرب نهاية الطريق من الحل، بحيث توسّع المسارات التي تعتبر أقرب إلى الحل للوصول إلى الحل بشكل أسرع. ويسمى هذا النوع من البحث بـ  بتفضيل الأولية الجشع أو البحث الإرشادي النقي (pure heuristic search) - بحث الكشف النقي عن مجريات الأمور.Korf, Richard E. (1999). 

عادةً ما يتم تنفيذ كفاءة اختيار أفضل مرشح ليتم توسيعه باستخدام طابور الأولوية (priority queue).

خوارزمية البحث بتفضيل الأولية مثال على البحث الأول-الأفضل (تعرف بـ A* بالإنجليزية)، أما الخوارزمية المعروفة بـ (B*) فهي تستخدم غالباً لإيجاد المسارات في البحث الإندماجي (combinatorial search). ولا تعتبر أي من أ* أو ب*  خوارزمية بحث أول-أفضل جشع حيث أن كلاهما لا تتناغمان مع المسافة المقطوعة من البداية مجموعة مع المسافات المقدرة نحو الهدف وهي صفة خوارزمية البحث الأول-الأفضل الجشع.

 الخوارزمية 
تكون خوارزمية البحث بتفضيل الأول على النحو التالي.http://www.macs.hw.ac.uk/~alison/ai3notes/subsubsection2_6_2_3_2.html  Best First SearchOPEN = [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

 المراجع 

 وصلات خارجية 
 ويكي مصدر: الذكاء الاصطناعي: البحث الأول-الأفضل

تصنيف:خوارزميات بحث