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

في البداية، البحث بتفضيل الأولية خوارزمية بحث تستكشف مجموعة البيانات (Graph) من خلال توسيع نطاق العقدة الأكثر نجاحاً أي الأكثر مطابقة لقاعدة محددة يتم البحث بواسطتها. وتعرض الأقسام التالية جوانب أخرى من الموضوع.
وفي هذا الصدد، خوارزمية البحث بتفضيل الأولية مثال على البحث الأول-الأفضل (تعرف بـ A* بالإنجليزية)، أما الخوارزمية المعروفة بـ (B*) فهي تستعمل غالباً لإيجاد المسارات في البحث الإندماجي (combinatorial search). ولا تعتبر أي من أ* أو ب* خوارزمية بحث أول-أفضل جشع حيث أن كلاهما لا تتناغمان مع المسافة المقطوعة من البداية مجموعة مع المسافات المقدرة نحو الهدف وهي صفة خوارزمية البحث الأول-الأفضل الجشع.
وفي هذا الصدد، عادةً ما يتم تنفيذ كفاءة اختيار أفضل مرشح ليتم توسيعه باستخدام طابور الأولوية (priority queue).
في هذا الإطار، استعمل بعض الكتاب «البحث بتفضيل الأولية» للإشارة على وجه التحديد إلى البحث بخوارزمية الكشف عن مجريات الأمور (heuristic) التي تحاول التنبؤ بمدى قرب نهاية الطريق من الحل، بحيث توسّع المسارات التي تعتبر أقرب إلى الحل للوصول إلى الحل بشكل أسرع. ويسمى هذا النوع من البحث بـ بتفضيل الأولية الجشع أو البحث الإرشادي النقي (pure heuristic search) - بحث الكشف النقي عن مجريات الأمور.
وفي هذا السياق، يهودا بيرل وصف البحث بتفضيل الأولية بتقدير نجاح تلك العقدة n «وذلك بحسب دالة تقييم إرشادية (heuristic evaluation function) والتي قد تعتمد بشكل عام على كل من: وصف n، وصف الهدف، المعلومات التي تم جمعها بواسطة البحث عن تلك النقطة، والأهم من ذلك كله، أي معلومات إضافية حول نطاق المعضلة (problem domain)»
do
1. Remove the best node from OPEN, call it n.
CLOSED = []
علاوةً على ذلك، 4. Evaluate each successor, add it to OPEN, and record its parent.
من جانب آخر، doneهذا الإصدار من الخوارزمية ليس كاملاً، أي أنها لا تجد دائماً مساراً ممكناً بين عقدتين، وحتى لو كان هناك مسار. فمثلًا، قد يعلق في حلقة ما إذا وصلها عند نهاية مغلقة، ويحدث هذا عندما تكون العقدة الوحيدة التي تخلف (ن) هي أصلها. وبالتالي ترجع إلى أصلها، وهكذا يتم إدراج الخلف الواقع في النهاية المغلقة في قائمة م مرة أخرى.
while OPEN is not empty
كذلك، 2. If n is the goal state, backtrace path to n (through recorded parents) and return path.
3. Create n's successors.
من جانب آخر، النسخة التالية تمتد الخوارزمية إلى استخدام قائمة إضافية غ (ملاحظة م = مفتوحة، غ=مغلقة) وهي قائمة تحتوي على كافة العقد التي تم تقييمها ولن يتم النظر فيها مرة أخرى. وهذا سوف يجنب أي عقدة يجري تقييمها مرتين، وبالتالي فإنه لن يخضع لحلقات لانهائية.OPEN = [initial state]
do
- i. If it is not in OPEN add it to OPEN.
- ii. Otherwise, adjust its priority in OPEN using this new evaluation.
- done
- المراجع
- وصلات خارجية
3. Create n's successors.
من جهة ثانية، 1. Remove the best node from OPEN, call it n, add it to CLOSED.
وفي السياق ذاته، a. If it is not in CLOSED and it is not in OPEN: evaluate it, add it to OPEN, and record its parent.
وعلى صعيد آخر، 2. If n is the goal state, backtrace path to n (through recorded parents) and return path.
4. For each successor do:
وفي هذا السياق، b. Otherwise, if this new path is better than previous one, change its recorded parent.
الخوارزمية
while OPEN is not empty or until a goal is found
وفي هذا السياق، تكون خوارزمية البحث بتفضيل الأول على النحو التالي.OPEN = [initial state]
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟