البحث التنقيبي

المادة: الذكاء الاصطناعي (Artificial Intelligence)

المرحلة الرابعة / ( المحاضرة 6)

المصدر: ترجمة (Artificial Intelligence / George F. Luger)

1. البحث الموجه (Heuristic Search)

 

• إن التوجيه (التنقيب) هو طريقة قد لا تجد دائماً الحل الأفضل, لكنها تضمن إيجاد حل جيد في وقت معقول. إن البحث الموجه مفيد في الحالات التالية:

1. حل المشاكل التي لا يمكن حلها بأية طريقة أخرى.
2. عندما يكون الوقت المطلوب لحل المشكلة غير محدد أو طويل جداً.

• طرائق البحث الموجه ما يلي:

• خوارزمية تسلق الجبل (Hill Climbing).
• خوارزمية البحث الأفضل (Best First Search).
• خوارزمية (A) و خوارزمية (A*).

1. خوارزمية تسلق الجبل (Hill Climbing )

   إن الاسم “Hill Climbing” يأتي من فكرة أنك تحاول إيجاد قمة الجبل, و أنك تذهب في الاتجاه الأعلى منك أينما تكون. و في هذه الخوارزمية لا يتم الاحتفاظ بكل الحالات (العقد) و إنما يتم الاحتفاظ بمسار العقدة المحتسبة و المسار من عقدة البداية إلى تلك العقدة. عند كل عقدة يتم الوصول إليها, يتم اختيار العقدة الأقرب إلى الهدف (وفقاً للتقييم الموجه), و نستمر من هناك.

    

    

   Open	Closed
   [A]	[]
   [C3B2D1]	[A]
   [G4F2]	[AC3]
   [N5M4]	[AC3G4]
   [R4S4]	[AC3G4N5]
   []	[AC3G4N5R4]

    

    

2. مشاكل خوارزمية تسلق الجبل (Hill Climbing Problems )

• إن الخوارزمية قد تفشل لسبب أو أكثر من الأسباب التالية:

1. (Local Maxima):- و هي الحالة التي تكون أفضل من كل الحالات المجاورة لها, لكنها ليست أفضل من بعض الحالات الأخرى.

Local Maxima

 (Plateau):- و هي المنطقة من فضاء البحث التي تكون فيها كل الحالات لها نفس القيمة, و في هذه الحالة فإنه من غير الممكن تحديد الاتجاه الأفضل الذي سيتم الانتقال إليه.

 

Plateau

 

 

 

 

 

 

3.    (Ridge):- و هي المنطقة من فضاء البحث التي تكون أعلى من المناطق المحيطة بها, لكنها لا يمكن اجتيازها في نقلة واحدة في أي اتجاه.

 

 

 

4.6.           

Ridge

خوارزمية (Best-First)

 

إن الاسم “Hill Climbing” يأتي من فكرة أنك تحاول إيجاد قمة الجبل, و أنك تذهب في الاتجاه الأعلى منك أينما تكون. احتفاظ بكل الحالات (العقد) و إنما يتم الاحتفاظ بمسار العقدة المحتسبة و المسار من عقدة البداية إلى تلك العقدة. عند كل عقدة يتم الوصول إليها, يتم اختيار العقدة الأقرب إلى الهدف (وفقاً للتقييم الموجه), و نستمر من هناك.

 

5.6. استخدام دالة التخمين (Implementing Evaluation Function)

من مساوئ خوارزمية البحث عن الأفضل (Best-First-Search) أنها تركز عملية البحث على فرع في فضاء البحث على حساب بقية الأفرع. و يحدث ذلك إذا قمنا بإعطاء كلف أو قيم افتراضية جيدة للحالات الموجودة على فرع ما. و قد يكون ذلك سيئاً لعدم وجود الهدف على ذلك الفرع من فضاء البحث, أو بسبب وجود هدف أقرب (ذو مسار اقصر) على فرع آخر. 

و لتجنب هذه المشكلة ينصح عادة باستخدام دالة تخمين (Evaluation Function) تأخذ بنظر الاعتبار مقدار بعد الحالة المختارة عن حالة البداية بحيث تفضل الحالة الأقرب, و ذلك لتجنب الاستمرار في البحث في فرع واحد على حساب بقية الأفرع. إن دالة التخمين (Evaluation Function) ستكون صيغتها كما يلي:

f(n) = g(n) + h(n)                  Evaluation Function

حيث g(n):- طول المسار الفعلي من أية حالة (أو عقدة) إلى حالة (أو عقدة) البداية.

h(n):- البعد التقديري من العقدة (n) إلى الهدف.

·     عندما تستخدم خوارزمية (Best-First) مع دالة التخمين (Evaluation Function) أعلاه, فإن الخوارزمية الناتجة تسمى (A-Algorithm).

مثال:- لدينا الشجرة التالية قبل استخدام دالة التخمين (Evaluation Function)

بعد استخدام دالة التخمين تصبح الشجرة كما يلي:-