Intelligent Search Algorithm Theoretical Lec 2 PDF

‫‪800‬‬ ‫نظري‬ ‫‪Uniformed Search‬‬ ‫‪2‬‬ ‫‪17/10/2022‬‬ ‫‪16‬‬ ‫د‪.‬عمار النحاس‬ ‫فهرس المحاضرة‪:‬‬...

‫‪800‬‬ ‫نظري‬ ‫‪Uniformed Search‬‬ ‫‪2‬‬ ‫‪17/10/2022‬‬ ‫‪16‬‬ ‫د‪.‬عمار النحاس‬ ‫فهرس المحاضرة‪:‬‬ ‫‪Uniformed Search‬‬ ‫‪▪2‬‬ ‫مقدمة‬ ‫‪▪ 1‬‬ ‫‪UCS‬‬ ‫‪▪5‬‬ ‫‪BFS‬‬ ‫‪▪4‬‬ ‫‪DFS‬‬ ‫‪▪3‬‬ ‫مقدمة‬ ‫خالل حل مسألة نتبع الخوارزمية العامة وهي أننا ال نقوم بتوليد كل الحاالت بسبب صعوبة تخزين كل الحاالت لكثرتها‬ ‫كما رأينا في الشطرنج ومكعب الروبيك‪ ،‬وإنما ننطلق من الحالة البدائية على اعتبار أننا ال نعرف أبناءها‪ ،‬ومن خالل‬ ‫الـ‪ action‬نوجد أبناءها‪.‬‬ ‫في كل مرة سنقوم بالبحث عن عقدة ال نعرف من أبناءها وبعد ذلك تضاف هذه األبناء لمجموعة العقد التي ال نعرف‬ ‫ابناءها وبعد معرفة ابناءها نزيل تلك العقدة من المجموعة‪ ،‬ونأخذ عقدة ال نعرف ابناءها ونعاود الكرة وهكذا إلى أن‬ ‫نصل لحل أو إلى أن تصبح مجموعة العقد التي ال نعرف أبناءها (األوراق) فارغة وبالتالي تأكدنا أنه ليس لدينا حل‪.‬‬ ‫ولكن كيف سنختار العقدة التي ال نعرف ابناءها؟‬ ‫من هنا سنتعرف على الخوارزميات التالية‪.‬‬ ‫‪1‬‬  ‫‪ |Uniformed Search‬د‪.‬عمار النحاس‬ ‫‪Uninformed search strategies‬‬ ‫إن هذه االستراتيجية (الخوارزمية) ال تستخدم المعلومات ذات الصلة بالمشكلة المحددة‪ ،‬وإنما تعتمد على تجارب سابقة‬ ‫(معلومات تحصل عليها خالل الحل)‪.‬‬ ‫وهناك ثالث أنواع لهذه الخوارزمية‪:‬‬ ‫ ‪ : Depth-first search‬تعتمد هذه الخوارزمية على مسح شجرة البحث بالعمق‪.‬‬ ‫ ‪ : Breadth-first search‬تعتمد هذه الخوارزمية على مسح شجرة البحث بالعرض‪.‬‬ ‫ ‪: Uniform-cost search‬تعتمد هذه الخوارزمية على ايجاد العقدة ذات التكلفة األقل بعد حساب الكلف‬ ‫من العقدة الحالية لجميع مجاوراتها‪.‬‬ ‫تختلف طريقة تخزين العقد حاسوبيا بين الخوارزميات الثالثة‪:‬‬ ‫‪ :DFS‬تخزّن بـ ‪.stack‬‬ ‫▪‬ ‫‪ :BFS‬تخزّن بـ ‪.queue‬‬ ‫▪‬ ‫‪ :UCS‬تخزّن بـ‪ priority queue‬وهو ‪ queue‬مرتب تنازلياً دوما حسب التكلفة‪.‬‬ ‫▪‬ ‫‪Depth-first search‬‬ ‫تعتمد هذه الخوارزمية على مسح شجرة البحث بالعمق وتكون العقدة التالية هي أول عقدة ألبناء العقدة الحالية من‬ ‫جهة اليسار ويتم االنتقال للعقدة المجاورة للعقدة الحالية بعد االنتهاء من جميع العقد في الشجرة الجزئية للعقدة‬ ‫الحالية وذلك وفق الخوارزمية ذاتها‪.‬‬ ‫❖ أي أن شجرة العقد التي لم نقم بزيارتها بعد هي عبارة عن ‪ fringe = LIFO Queue‬وهذا يعني أن نضع عقد‬ ‫األبناء في المقدمة حيث )‪.LIFO = (last in fires out‬‬ ‫❖ في الـ ‪ DFS‬نخزن العقد )‪ (Nodes‬في الـ ‪ stack‬وليس الـ‪.State‬‬ ‫سنأخذ مثال على كيفية سير خوارزمية البحث بالعمق عن طريق البحث عن العقدة ‪ M‬بداية من العقدة ‪:A‬‬ ‫‪2‬‬ ‫‪/ITE.RBCs‬‬  ‫ عمار النحاس‬.‫| د‬Uniformed Search 3 /ITE.RBCs  ‫ عمار النحاس‬.‫| د‬Uniformed Search 4 /ITE.RBCs  ‫ عمار النحاس‬.‫| د‬Uniformed Search 5 /ITE.RBCs  ‫‪ |Uniformed Search‬د‪.‬عمار النحاس‬ ‫لنناقش خوارزمية الـ‪:DFS‬‬ ‫هل هي ‪Complete‬؟‬ ‫ال‪ ،‬فهي تفشل في حال كان عمق الشجرة (‪ )infinite-depth‬وأيضا عند تشكل الحلقات (إمكانية المرور على‬ ‫نفس الحالة مرتين بنفس الـ‪ ،)path‬ومنه عند وجود )‪ )finite-depth‬سوف تكون ‪.Complete‬‬ ‫‪Time Complexity‬؟‬ ‫التعقيد هو ) ‪، O( bm‬حيث ‪ : b‬هو الـ‪ Branch factor‬وسطي عدد التفرعات (الوصالت) الخارجة من كل عقدة إلى‬ ‫أبناءها‪ ،‬وبالتالي سوف يكون كبيرا جدا في حال ‪ m‬أكبر بكثير من ‪( d‬عمق الحل األفضل) ‪،‬أسوء حالة هي البحث في‬ ‫الشجرة وصوال ألقصى عقدة في اليمين (بحثنا في كافة األوراق)‪.‬‬ ‫‪Space Complexity‬؟‬ ‫)‪ " O (b*m‬خطي " فهي تحتاج مساحة تخزين كبيرة‪.‬‬ ‫تذكرة‪:‬‬ ‫‪( Branching factor :b‬عامل التفرع) متوسط‬ ‫‪Optimality‬؟‬ ‫عدد األبناء لكل عقدة‪.‬‬ ‫ال‪ ،‬فهي ال تعطي الحل األمثل‪.‬‬ ‫‪ Depth :d‬عمق الحل (ذو الكلفة الزمنية األقل)‪.‬‬ ‫‪ :m‬أعمق حل‪.‬‬ ‫‪6‬‬ ‫‪/ITE.RBCs‬‬  ‫‪ |Uniformed Search‬د‪.‬عمار النحاس‬ ‫)‪BFS (breadth first search‬‬ ‫تعتمد هذه الخوارزمية على مسح شجرة البحث بشكل عرضي‪ ،‬حيث نستخدم الرتل ‪ Queue‬من النوع‬ ‫)‪ FIFO (first in first out‬الذي يبدأ من عقدة البداية والتي تمثل المستوى الصفري ثم العقد الموصولة بها ومن ثم‬ ‫نبدأ بمعالجة العقدة تلو االخرى بحيث ال ننتقل من مستوى إلى الذي يليه حتى ننتهي من معالجة جميع عقده‪.‬‬ ‫مع التنويه أن الـ‪ BFS‬يمكن أن تكون من اليمين وممكن أن تكون من اليسار بحسب طريقة االدخال إلى الرتل في‬ ‫البداية‪.‬‬ ‫سنأخذ مثال على كيفية سير خوارزمية البحث بالعرض عن طريق البحث عن العقدة ‪ D‬بداية من العقدة ‪.A‬‬ ‫‪7‬‬ ‫‪/ITE.RBCs‬‬  ‫‪ |Uniformed Search‬د‪.‬عمار النحاس‬ ‫لنناقش اآلن‪:‬‬ ‫هل هي ‪Complete‬؟‬ ‫نعم‪ ،‬في حال ‪ b‬منتهي‪.‬‬ ‫‪ Time Complexity‬؟‬ ‫)‪O (bd+1‬‬ ‫‪ Space Complexity‬؟‬ ‫)‪ ، O (bd+1‬يتم تخزين كل عقدة في الذاكرة‪.‬‬ ‫‪ Optimality‬؟‬ ‫نعم‪ ،‬وذلك في حال عدم ازدياد الكلفة مع ازدياد العمق (كلفة كل العمليات متساوية) فهي تمسح كافة عقد‬ ‫المستوى الحالي ثم تنتقل للمستوى التالي‪.‬‬ ‫فمثال لو كان لدينا المعطيات التالية‪:‬‬ ‫‪B = 10, 10.000 node/sec, 1000 byte/node‬‬ ‫وفق تلك المعطيات يكون لدينا الزمن والحجم التاليين مع تزايد العقد والعمق‪:‬‬ ‫‪Depth‬‬ ‫‪Nodes‬‬ ‫‪Time‬‬ ‫‪Memory‬‬ ‫‪2‬‬ ‫‪1100‬‬ ‫‪.11 sec‬‬ ‫‪1 Megabyte‬‬ ‫‪4‬‬ ‫‪111,100‬‬ ‫‪11 sec‬‬ ‫‪106 Megabyte‬‬ ‫‪6‬‬ ‫‪107‬‬ ‫‪19 min‬‬ ‫‪10 Gigabyte‬‬ ‫‪8‬‬ ‫‪109‬‬ ‫‪31 hours‬‬ ‫‪1 Terabyte‬‬ ‫‪10‬‬ ‫‪1011‬‬ ‫‪129 days‬‬ ‫‪101 Terabyte‬‬ ‫‪12‬‬ ‫‪1013‬‬ ‫‪35 years‬‬ ‫‪10 Petabyte‬‬ ‫‪14‬‬ ‫‪1015‬‬ ‫‪3,523 years‬‬ ‫‪1 Exabyte‬‬ ‫‪8‬‬ ‫‪/ITE.RBCs‬‬  ‫‪ |Uniformed Search‬د‪.‬عمار النحاس‬ ‫)‪Uniform-Cost Search (Dijkstra‬‬ ‫تعتمد هذه الخوارزمية على إيجاد العقدة الجديدة (غير المزارة ذات الكلفة األقل بعد حساب الكلف من العقدة الحالية‬ ‫لجميع مجاوراتها) ثم االتمام بالطريق األقل كلفة بعد حساب الكلفة لكل الطرق في كل خطوة والمسير من‬ ‫الطريق األقصر غير المزار‪ ،‬ويكون الحل في هذه المسالة هو الطريق صاحب الكلفة األقل بين جميع الخيارات االخرى‪.‬‬ ‫ملحظة‪ :‬في هذه الخوارزمية نحتاج لحساب المسافات (الكلف) في كل مرحلة بخلف سابقتيها‪.‬‬ ‫ولسهولة الفهم يمكن مشاهدة الفيديو التالي‪:‬‬ ‫فمثال يكون الحل‪:‬‬ ‫𝐸→𝐶→𝐴‬ ‫وفق شجرة البحث التالية‪:‬‬ ‫لنناقش اآلن‪:‬‬ ‫هل هي ‪Complete‬؟ نعم‪.‬‬ ‫‪Time Complexity‬؟ عدد العقد باإلضافة لكلفة الحل األمثل‪.‬‬ ‫‪Space Complexity‬؟ عدد العقد باإلضافة لكلفة الحل األمثل‪.‬‬ ‫‪Optimality‬؟ نعم تعطي الحل األمثل‪.‬‬ ‫‪9‬‬ ‫‪/ITE.RBCs‬‬  ‫‪ |Uniformed Search‬د‪.‬عمار النحاس‬ ‫الخوارزمية العامة لخوارزميات البحث العمياء ‪Uniformed‬‬ ‫حيث أن‪:‬‬ ‫‪ :OPEN‬هي ‪ Queue‬سنضع فيها العقد المتاحة‬ ‫في كل خطوة ‪.‬‬ ‫‪ :CLOSE‬هي ‪ Queue‬أيضا سنضع فيها العقد‬ ‫المزارة‪.‬‬ ‫‪ :u‬العقة الحالية‪.‬‬ ‫‪ :v‬العقدة التالية‪.‬‬ ‫)‪ : K(u, v‬هي الكلفة بين العقدتين ‪ u‬و‪.v‬‬ ‫أن تحديد العقدة التالية في كل خطوة يختلف وفق‬ ‫كل نوع منها ففي‪:‬‬ ‫‪ :Depth-First Search‬تكون العقدة التالية‬ ‫هي أول عقدة ألبناء العقدة الحالية‪.‬‬ ‫‪ :Breadth-First Search‬تكون العقدة التالية‬ ‫هي العقدة المجاورة للعقدة الحالية‪.‬‬ ‫‪ :Uniform-CostSearch‬تكون العقدة التالية هي العقدة ذات الكلفة األقل (‪.)Dijkstra‬‬ ‫مسألة‬ ‫لدينا مجموعة مدن بينها طرق ونريد إيجاد أقصر طريق بين مدينتين معينتين‪ ،‬ما هو أقصر طريق من ‪ A‬لـ ‪.F‬‬ ‫سنحول مسألتنا لغراف‪:‬‬ ‫‪A‬‬ ‫‪2‬‬ ‫‪5‬‬ ‫كل عقدة ستدخل على مجموعة العقد التي سنبحث عن أبنائها‬ ‫‪2‬‬ ‫‪B‬‬ ‫‪C‬‬ ‫ستدخل معها كلفتها‪ ،‬وبعد ذلك العقد التي سنختارها‬ ‫‪1‬‬ ‫‪6‬‬ ‫‪2‬‬ ‫هي العقد ذات الكلفة األقل‪.‬‬ ‫‪4‬‬ ‫‪D‬‬ ‫‪E‬‬ ‫نبدأ من العقدة ‪ A‬كلفتها ‪ ,0‬أبناؤها (‪..)B,1(,)C,2‬‬ ‫‪1‬‬ ‫نزيل ‪ A‬ونختار ‪ B‬ونضع أبناءها وهكذا‪...‬‬ ‫‪5‬‬ ‫‪2‬‬ ‫‪F‬‬ ‫‪10‬‬ ‫‪/ITE.RBCs‬‬  ‫‪ |Uniformed Search‬د‪.‬عمار النحاس‬ ‫‪A,0‬‬ ‫‪B,2‬‬ ‫‪C,5‬‬ ‫‪C,4‬‬ ‫‪D,8‬‬ ‫‪B,7‬‬ ‫‪E,3‬‬ ‫‪D,6‬‬ ‫‪E,7‬‬ ‫‪D,5‬‬ ‫‪E,6‬‬ ‫‪D,7‬‬ ‫‪F,8‬‬ ‫‪C,8‬‬ ‫‪B,12‬‬ ‫‪E,7‬‬ ‫‪F,12‬‬ ‫‪E,6‬‬ ‫‪F,10‬‬ ‫‪D,7‬‬ ‫‪F,8‬‬ ‫‪F,9‬‬ ‫‪B,11‬‬ ‫‪F,8‬‬ ‫هل هذه الخوارزمية تعطي حل أمثل دائماً؟‬ ‫في حالة واحدة وهي كل أوزان موجبة‪.‬‬ ‫كم عقدة زرنا؟‬ ‫‪ 6‬عقد‬ ‫كم عقدة فتحنا؟‬ ‫‪ 13‬عقدة‬ ‫التعقيد‪:‬‬ ‫تعقيد هذه الخوارزمية بالمتوسط )𝑛(⁡‪ 𝑛 ∗ log‬وبأسوأ األحوال ‪𝑛2‬‬ ‫مالحظة‪:‬‬ ‫▪ العقد المفتوحة‪ :‬هي العقد التي قمنا بالبحث عن أبنائها‪.‬‬ ‫▪ العقد المزارة‪ :‬هي عقد الغراف التي قمنا بزيارتها‪.‬‬ ‫‪11‬‬ ‫‪/ITE.RBCs‬‬  ‫‪ |Uniformed Search‬د‪.‬عمار النحاس‬ ‫مسألة‪:‬‬ ‫لدينا الـ ‪ graph‬التالي ونريد االنتقال من ‪ A‬إلى ‪.E‬‬ ‫الحل‪:‬‬ ‫باستخدام خوارزمية الـ ‪:DFS‬‬ ‫▪‬ ‫هذه الخوارزمية ال تهتم بكلفة الوصلة بين العقد‪.‬‬ ‫لدينا ‪ stack‬لتخزين العقد و‪ history‬لتخزين العقد المزارة‪.‬‬ ‫‪12‬‬ ‫‪/ITE.RBCs‬‬  ‫‪ |Uniformed Search‬د‪.‬عمار النحاس‬ ‫ال يمكن زيارة العقدة ‪ A‬مجددا ألنها مزارة من قبل‪.‬‬ ‫وصلنا إلى العقدة ‪( E‬الهدف) لذلك نتوقف عن متابعة الحل بالخوارزمية‪.‬‬ ‫‪13‬‬ ‫‪/ITE.RBCs‬‬  ‫‪ |Uniformed Search‬د‪.‬عمار النحاس‬ ‫باستخدام خوارزمية ‪:BFS‬‬ ‫▪‬ ‫ال تهتم هذه الخوارزمية بكلفة الوصلة بين العقد‪.‬‬ ‫لدينا ‪ Queue‬لتخزين العقد و‪ history‬لتخزين العقد‬ ‫المزارة‪.‬‬ ‫‪14‬‬ ‫‪/ITE.RBCs‬‬  ‫‪ |Uniformed Search‬د‪.‬عمار النحاس‬ ‫باستخدام خوارزمية ‪:UCS‬‬ ‫▪‬ ‫تهتم هذه الخوارزمية بالكلفة بين‬ ‫العقد وفي كل مرة تختار الطريق‬ ‫ذات الكلفة األقل‪.‬‬ ‫‪15‬‬ ‫‪/ITE.RBCs‬‬  ‫‪ |Uniformed Search‬د‪.‬عمار النحاس‬ ‫تعتبر تقنيات البحث السابقة (الـ‪ BFS‬والـ‪ DFS‬والـ‪ )UCS‬بطيئة للغاية بالنسبة لمعظم المسائل‪.‬‬ ‫انتهت املحاضرة‬ ‫‪16‬‬ ‫‪/ITE.RBCs‬‬