/Evaluating Search Strategies

Evaluating Search Strategies

إكمالا لحديثنا عن الذكاء الاصطناعي ، نتحدث في هذا الموضوع عن عمليات البحث عن حل ، و الحل – solution – هو مجموعة من العمليات في مسار معين في ال state space من نقطة البداية لآخر نقطة للوصول لل gaol – الهدف – و مع كل خطوة يتم حساب ما يسمى بال Cost و هو ما يعبر عن عدد الخطوات حتى الوصول للهدف .

و نستطيع الحكم على أنواع ال بحث – Search – الممكنة من حيث الخواص التالية :

أولا : Completness
و هي إمكانية إيجاد حل أم لا .

ثانيا : Time Complexty
و هو الوقت المستغرق لإيجاد حل .

ثالثا: Space Complexty
المساحة المحجوزة لعدد ال nodes التي يمر عليها .

رابعا: Optimality
الحل سيكون أنسب و أفضل من حيث ال cost أم لا ؟ .

و طرق البحث نوعان و هم UnInformed Search و Informed Search .
و سوف نتطرق هذه المرة للنوع الأول و هو ال Uninformed Search .
يستخدم في حله المعلومات المتاحة فقط . و يندرج تحته ما يلي من الأنواع :-

1- Breadth First Search
يتبع ال nodes بطريقة FiFo حيث أول عنصر يدخل في ال Queue هي التي تبدأ بالخروج و خواصها ما يلي :
## Complete – مقدرتها على الوصول لحل .
## Time – تأخذ وقت للوصول لحل .
## Space – تحجز مساحة أكبر .
## Optimal – تكون في حالة أن كل ال nodes لهم نفس ال Cost .

هذه الرسمة بها مجموعة من ال nodes متصلة ببعض و الهدف هو ال G .

لنرى طريقة الألجورزم و تتبع الحل :
{s} {A B C } { B C D E G } { C D E G G } {  D E G G G } { E G G G } { G G G } { G G }
نأخذ أول عنصر و نحدد ال Childs له و نضعهم في آخر ال Queue ، مثلا ال A وضعنا آخر ال Q ابنائها و هم DEG و من ثم أخذنا ال B و وضعنا ال G في آخر ال Q و هكذااا~~ .. ف نستطيع القول أنها تبحث level level بالعرض .
ال cost لل nodes التي مر عليها حتى الوصول لل هدف.  Cost =S>> A >> G =  3 + 15 = 18
مر على كل ال Nodes المتاحة .  Nodes Expanding = { S A B C D E G } = 7

2- Uniform Cost Search
تتبع ال nodes بطريقة الـ FiFo نفس ال Breadth ، و لكن تقوم ب مراعاة ال Cost من حيث الترتيب و من خواصها :
## complete إذا كان هناك حل ستصل له .
## Optimal حيث تكلف Cost أقل .
## Time & Space مماثلة لل Breadth .

و طريقة تتبع الهدف كما يلي : على نفس الnodes السابقة .
{S} {B A C } { A C G } { D C E G G } { C E G G } { E G G G } { G G G } { G G }
بعد كل مرة مثل ال Breadth نقوم بترتيب ال nodes حسب ال cost من الأصغر ، ف أول ما كان S وضعنا مكانها ABC و لكن تم ترتيبهم من حيث ال Cost و يتم بعدها أخذ أول عنصر من بعد الترتيب و بنفس طريقة ال Breadth نضع أبنائه في الآخر و نقوم بالترتيب مرة أخرى .. و هكذا ~~ .
Cost = S >> C >> G = 13  فهذا هو أقل Cost ممكن .
nomber of nodes = { S B A D C E G } = 7  ف يمر أيضا بكل ال Nodes المتاحة .

3- Depth First Search
تتبع ال nodes يكون بحسب طريقة Lifo حيث أخر عنصر يدخل في ال Stack هو أول عنصر يخرج منها . و خواصها ما يلي :
## Not Complete : حيث أنها تسلك في مسار واحد إن لم يجد الحل فيهف يتوقف .
## Time أسرع  إن وجد حل .
## Space أقل مساحة .
## Not Optimal .

و ل نتتبع الهدف ..
{S} { A B C } { D E G B C } { E G B C } { G B C } { B C }
نأخذ أول عنصر و نضع أبناؤه في أول ال Fringe او ال stack .. حتى نصل إلى ال هدف G . و في هذه الحالة ف هي تبحث في فرع فرع .
Cost = S >> A >> G = 3 + 15 = 18
nomber of Nodes = { S A D E G } = 5

و هذه ليست كل أنواع ال UnInformed و لكنها أشهرها و أكثرها استخداما في ألجورزمات الألعاب و غيرها من التطبيقات التي تندرج تحت الذكاء الاصطناعي مثل ألعاب المتاهة و الشطرنج و ال tower of hanoi و غيرها ..

TAGS: