البحث الأفضل أولاً

في علوم الحاسوب ، يعتبر البحث الأفضل أولاً فئة من خوارزميات البحث التي تستكشف الرسم البياني عن طريق توسيع العقدة الأكثر وعدًا المختارة وفقًا لقاعدة محددة.

وصفت جوديا بيرل خوارزمية البحث الأفضل أولاً بأنها تقدير لإمكانية الوصول إلى العقدة n بواسطة "دالة تقييم استدلالية".${\displaystyle f(n)}$والتي قد تعتمد بشكل عام على وصف n ، ووصف الهدف، والمعلومات التي تم جمعها من خلال البحث حتى تلك النقطة، والأهم من ذلك، على أي معرفة إضافية حول مجال المشكلة. ^{[ 1 ] [ 2 ]}

استخدم بعض المؤلفين مصطلح "البحث الأفضل أولاً" للإشارة تحديدًا إلى البحث الذي يعتمد على أسلوب استدلالي يحاول التنبؤ بمدى قرب نهاية المسار من الحل (أو الهدف)، بحيث يتم توسيع المسارات التي يُعتقد أنها أقرب إلى الحل (أو الهدف) أولاً. يُطلق على هذا النوع من البحث اسم البحث الأفضل أولاً الجشع ^{[ 2 ]} أو البحث الاستدلالي البحت ^{[ 3 ]} .

يتم عادةً تنفيذ الاختيار الفعال لأفضل مرشح حالي للتوسيع باستخدام قائمة انتظار ذات أولوية .

تُعدّ خوارزمية البحث A* مثالاً على خوارزمية البحث الأفضل أولاً، وكذلك خوارزمية B* . تُستخدم خوارزميات البحث الأفضل أولاً عادةً لإيجاد المسار في البحث التوافقي . لا تُعتبر أيٌّ من خوارزميتي A* أو B* بحثًا جشعًا من نوع البحث الأفضل أولاً، لأنهما تُدمجان المسافة من نقطة البداية بالإضافة إلى المسافات المُقدّرة إلى الهدف.

باستخدام خوارزمية جشعة ، قم بتوسيع أول خليفة للأصل. بعد إنشاء خليفة: ^{[ 4 ]}

1. إذا كانت الطريقة الاستدلالية للخليفة أفضل من الطريقة الاستدلالية للأصل، يتم وضع الخليفة في مقدمة قائمة الانتظار (مع إعادة إدخال الأصل مباشرة خلفه)، وتبدأ الحلقة من جديد.
2. وإلا، يُضاف العنصر اللاحق إلى قائمة الانتظار (في موقع يُحدد بناءً على قيمته الاستدلالية). وسيقوم الإجراء بتقييم العناصر اللاحقة المتبقية (إن وجدت) للعنصر الأب.

فيما يلي مثالٌ برمجيٌّ زائفٌ لهذه الخوارزمية، حيث يُمثّل queue طابورًا ذا أولوية يُرتّب العُقد بناءً على مسافاتها التقريبية من الهدف. يحتفظ هذا التطبيق بسجلّ العُقد التي تمت زيارتها، وبالتالي يُمكن استخدامه مع الرسوم البيانية غير الموجّهة . كما يُمكن تعديله لاسترجاع المسار.

الإجراء GBS(start, target) هو : ضع علامة على بداية الزيارة. أضف البداية إلى قائمة الانتظار طالما أن قائمة الانتظار ليست فارغة، نفّذ ما يلي : العقدة_الحالية ← رأس الطابور ذو أقصر مسافة إلى الهدف إزالة العقدة الحالية من قائمة الانتظار لكل جار n للعقدة الحالية، نفّذ ما يلي : إذا لم يكن n ضمن العقدة التي تمت زيارتها ، فإذا كان n هو الهدف، فأرجع n، وإلا : ضع علامة n على الزيارة أضف n إلى قائمة الانتظار فشل الإرجاع

• بحث شعاعي
• خوارزمية البحث A*
• خوارزمية ديكسترا

• ويكي بوكس: الذكاء الاصطناعي: البحث الأفضل أولاً