نبذة الكتاب:

يشرح الفرق بين البحث المنظم والغير منظم Uninformed vs. informed search
ماهو البحث المنظم  Informed Search تحتوي خوارزميات البحث المنظم على معلومات عن حالة الهدف مما يساعد في بحث أكثر كفاءة. يتم الحصول على هذه المعلومات من خلال وظيفة تقدر مدى قرب الحالة من حالة الهدف. وانواع البحث المنظم Informed Search
1-Heuristic Functions
2-A*

1-Heuristic Functions

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

Pure Heuristic Search

البحث عن مجريات الأمور البحتة هو أبسط شكل من أشكال خوارزميات البحث الإرشادية. يوسع العقد بناءً على قيمتها الاستكشافية h (n). يحتفظ بقائمتين ، القائمة المفتوحة والمغلقة. في القائمة المغلقة ، فإنه يضع تلك العقد التي تم توسيعها بالفعل وفي القائمة المفتوحة ، فإنه يضع العقد التي لم يتم توسيعها بعد.

في كل تكرار ، يتم توسيع كل عقدة n ذات أدنى قيمة إرشادية وتولد كل ما يتبعها ويتم وضع n في القائمة المغلقة. تستمر الخوارزمية في الوحدة تم العثور على حالة الهدف.

في البحث المستنير سنناقش خوارزميتين رئيسيتين موضحة أدناه:

• 1-Best First Search Algorithm(Greedy search)

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

و (ن) = ز (ن).
كانت ، h (n) = التكلفة المقدرة من العقدة n إلى الهدف.

يتم تنفيذ أفضل الخوارزمية الأولى الجشعة من خلال قائمة انتظار الأولوية.

Best first search algorithm

•  
•  
• Step 1: Place the starting node into the OPEN list.
• Step 2: If the OPEN list is empty, Stop and return failure.
• Step 3: Remove the node n, from the OPEN list which has the lowest value of h(n), and places it in the CLOSED list.
• Step 4: Expand the node n, and generate the successors of node n.
• Step 5: Check each successor of node n, and find whether any node is a goal node or not. If any successor node is goal node, then return success and terminate the search, else proceed to Step 6.
• Step 6: For each successor node, algorithm checks for evaluation function f(n), and then check if the node has been in either OPEN or CLOSED list. If the node has not been in both list, then add it to the OPEN list.
• Step 7: Return to Step 2.

• 2-A* Search Algorithm

البحث A * هو الشكل الأكثر شيوعًا للبحث الأفضل أولاً. يستخدم الدالة الاستكشافية h (n) والتكلفة للوصول إلى العقدة n من حالة البداية g (n). لقد جمعت بين ميزات UCS والبحث الجشع الأفضل أولاً ، والذي من خلاله يحل المشكلة بكفاءة. تعثر خوارزمية البحث * على أقصر مسار عبر مساحة البحث باستخدام وظيفة الكشف عن مجريات الأمور. تقوم خوارزمية البحث هذه بتوسيع شجرة بحث أقل وتوفر أفضل النتائج بشكل أسرع. خوارزمية * تشبه UCS فيما عدا أنها تستخدم g (n) + h (n) بدلاً من g (n).

في خوارزمية البحث A * ، نستخدم البحث الاسترشادي بالإضافة إلى تكلفة الوصول إلى العقدة. ومن ثم يمكننا الجمع بين كلتا الكلفتين على النحو التالي ، ويسمى هذا المجموع كرقم لياقة. البحث * هو الشكل الأكثر شيوعًا للبحث الأفضل أولاً. يستخدم الدالة الاستكشافية h (n) والتكلفة للوصول إلى العقدة n من حالة البداية g (n). لقد جمعت بين ميزات UCS والبحث الجشع الأفضل أولاً ، والذي من خلاله يحل المشكلة بكفاءة. تعثر خوارزمية البحث * على أقصر مسار عبر مساحة البحث باستخدام وظيفة الكشف عن مجريات الأمور. تقوم خوارزمية البحث هذه بتوسيع شجرة بحث أقل وتوفر أفضل النتائج بشكل أسرع. خوارزمية * تشبه UCS فيما عدا أنها تستخدم g (n) + h (n) بدلاً من g (n).

في خوارزمية البحث A * ، نستخدم البحث الاسترشادي بالإضافة إلى تكلفة الوصول إلى العقدة. ومن ثم يمكننا الجمع بين كلتا التكاليف على النحو التالي ، ويسمى هذا المبلغ كرقم لياقة.