خوارزمية البحث بأولوية العمق والبحث بأولوية الاتساع - الذكاء الاصطناعي - ثالث ثانوي

رابط الدرس الرقمي الدرس الثاني خوارزمية البحث بأولوية العمق والبحث بأولوية الاتساع البحث في المخططات Searching in Graphs www.ien.edu.sa هناك بعض الحالات التي تحتاج فيها إلى البحث عن عُقدة مُحدَّدة في المُخطَّط، أو تفحص كل عُقدة في المخطّط لإجراء عملية بعينها مثل طباعة عُقد المخطّط، فتكون حالتك كشخص يبحث عن المدينة التي يريد السفر إليها؛ وليتحقق هذا ، تحتاج إلى فحص كل عُقدة في المُخطَّط حتى تجد تلك التي تحتاج إليها. يُطلق على هذا الإجراء: البحث في المُخطَّط أو مسح المُخطَّط، وهناك العديد من خوارزميات البحث التي تساعد على تنفيذه، مثل: • خوارزمية البحث بأولوية الاتساع - Breadth-First Search). • خوارزمية البحث بأولوية العمق - Depth-First Search). عقدة البث العقد المجاورة لعقدة البث العقد الأخرى مثال على خوارزمية البحث بأولوية العمق (DFS): حل المتاهة مثال على خوارزمية البحث بأولوية الاتساع (BFS): البث الشبكي خوارزمية البحث بأولوية الاتساع Breadth-First Search (BFS) Algorithm تستكشف خوارزمية البحث بأولوية الاتساع (BFS) المخطّط بحسب المستوى 0 المستوى واحدا تلو الآخر، حيث تبدأ بفحص عُقدة الجذر ( عُقدة البداية)، المستوى 1 ثم تفحص جميع العُقد المرتبطة بها بشكل مباشر واحدة تلو الأخرى. و بعد الانتهاء من فحص كل العُقد في المستوى، تنتقل إلى المستوى التالي وتتبع الإجراءات نفسها الموضحة في الشكل 2.6. يُستخدَم الطَّابور لتتبع العقد التي تم فحصها ، وبمجرّد استكشاف العقدة، المستوى 2 ستتم إضافة العقد الفرعية إلى الطابور ، ثم تحذف العقدة التالية الموجودة في أول الطابور التي تم استكشافها سابقًا. A 1 2 B C 3 D E F G 4 5 6 شكل :2.6 خوارزمية البحث بأولوية الاتساع (BFS) 79 وزارة التعليم Ministry of Education 2024-1446

المثال التالي يوضّح طريقة عمل خوارزمية البحث بأولوية الاتساع .(BFS) باستخدام المُخطَّط التالي، حدد العقد التي يجب فحصها للانتقال من عقدة الجذر A إلى العقدة F: ملاحظة: استخدم هيكل البيانات المناسب. عليك فحص كل العقد في المستوى 1 قبل الانتقال إلى العقد في المستوى 2. A B C D E F 0 1 2 الطابور المخطّط 1 البداية من العقدة الجذرية العقدة A) . أضف العُقدة الجذرية إلى الطابور. احذف العُقدة الجذرية من 6 الطابور لمعالجتها، ثم أضف فروع هذه العقدة إلى الطابور ( العُقدتين B و C ) . احذف العُقدة من مقدمة الطابور ( العُقدة (B) لمعالجتها، ثم أضف فروع هذه العقدة إلى الطابور ( العُقدتين D وE ) . وزارة التعليم Ministry of Education 2024-1446 A B C فحصت A B C D E F D E FL A B C D E F B C A B C A 0 0 1 0 C D E A B C 01 2 0 1 2 80

81 6 احذف العقدة D لمعالجتها. ( ليس لديها فروع . 6 احذف العُقدة E لمعالجتها. (ليس لديها فروع . A B C A B C احذف العقدة C وعالجها، ثم أضف فرعها إليها. A B C D E F D E F D E وزارة التعليم Ministry of Education 2024-1446 <-- E F D <-- E 0 0 A B C D E F LL F لا C D E بي 1 0 1 D EF 0 1 2 FL 2 احذف العُقدة F لمعالجتها، وبذلك أصبح الطابور الآن فارغًا وانتهت عملية البحث. العقد التي فُحصت باستخدام خوارزمية البحث بأولوية الاتساع (BFS) هي : F ،E ، C ، B ،A. لاحظ كيف يمكنك تطبيق خوارزمية البحث بأولوية الاتساع (BFS) بلغة البايثون (Python ) في المثال التالي: graph = { } "A" : ["B","C"], "B" : ["D","E"], "C" : ["F"], "D" : [], "E" : [], "F" : [] visitedBFS = [] # List to keep track of visited nodes = queue [ ] # bfs function # Initialize a queue def bfs (visited, graph, node): visited.append(node)

queue.append(node) while queue: n = queue.pop(0) print (n, end = "") for neighbor in graph[n]: if neighbor not in visited: visited.append(neighbor) queue.append(neighbor) # main program bfs (visited BFS, graph, "A") A B C D E F التطبيقات العملية لخوارزمية البحث بأولوية الاتساع Practical Applications of the BFS Algorithm تُستخدم في شبكات النظير للنظير ( Peer-to-Peer Networks) للعثور على كل العُقد المجاورة من أجل تأسيس الاتصال. تُستخدم في وسائل التواصل الاجتماعي ( Social Media) لربط عقد المستخدمين المرتبطين، مثل أولئك الذين لهم الاهتمامات نفسها أو الموقع نفسه. تُستخدم في نُظم الملاحة باستخدام مُحدِّد المواقع العالمي (GPS Navigation Systems ) للبحث عن الأماكن المتجاورة حتى تُحدِّد الاتجاهات التي يتبعها المستخدم. وزارة التعليم Ministry of Education 2024-1446 تُستخدم للحصول على البث الشبكي (Network Broadcasting) لبعض الحزم. معلومة يُمكن تطوير خوارزمية البحث بأولوية الاتساع (BFS) بتحديد نقطة البداية (الحالة الأوليّة) ونقطة الهدف ( الحالة المستهدفة) لإيجاد المسار بينهما. 82

خوارزمية البحث بأولوية العمق Depth-First Search (DFS) Algorithm المستوى 0 في البحث بأولوية العمق (DFS) ، ستقوم باتباع الحواف، وتتعمق أكثر وأكثر في المُخطَّط. يستخدم البحث بأولوية العمق إجراء استدعاء تكراري المستوى 1 للتنقل عبر العقد . عند الوصول إلى عُقدة لا تحتوي على حواف لأي عقدة جديدة، ستعود إلى العُقدة السابقة وتستمر العملية. تستخدم خوارزمية البحث بأولوية العمق هيكل بيانات المكدّس لتتبع مسار الاستكشاف. بمجرد استكشاف عُقدة، ستُضاف إلى المكدّس . عندما ترغب في العودة، المستوى 2 ستحذف العُقدة من المكدّس كما هو موضح في الشكل 2.7. A 1 B C 2 3 4 5 6 D E F G شكل :2.7 خوارزمية البحث بأولوية العمق (DFS) المثال التالي يوضّح طريقة عمل خوارزمية البحث بأولوية العمق (DFS) ، باستخدام المخطّط التالي، تتبع ترتيب استكشاف العقد (Traversal بحسب خوارزمية البحث بأولوية العمق. و 83 عالج الجذر A ثم أضفه إلى المكدّس. A B C ملاحظة: استخدم هيكل البيانات المناسب. A B C D E F D E F A یک المخطط Я المكدّس 2 عالج العُقدة B ثم أضفها إلى المكدّس. فحصت A عالج العُقدة D ثم أضفها إلى المكدّس، ستُحذَف العُقدة التي فُحِصَت وليس لهـا فـروع مـن المكدس (احذف العُقدة (D). A D D |<--- B C B B D E FL A A لمحة تاريخية طورت النسخة الأولى من خوارزمية البحث بأولوية العمق (DFS) في القرن التاسع عشر بواسطة عالم رياضيات فرنسى كاستراتيجية لحل المتاهات وزارة التعليم Ministry of Education 2024-1446 B C B D E F A عالج العُقدة E ثم أضفها إلى المكدّس، ستحذف العُقدة التي فُحِصَت وليس لها فروع من المكدّس. احذف العُقدة E. A E E B C B B D E FL A A 4

عالج العُقدة C ثم أضفها إلى المكدّس. A B C C A 5 احذف العقدة B . B B C C ---> D E F A A D E F A المكدّس خالي وبالتالي ستتوقف خوارزمية البحث بأولوية العمق (DFS) A F عالج العقدة F ثم أضفها إلى المكدّس. A LL F <-- F --> C B C B C C C C A D E F A A D E F A A وزارة التعليم Ministry of Education 2024-1446 والآن ستتعلم طريقة تنفيذ خوارزمية البحث بأولوية العمق (DFS) في لغة البايثون. العقد التي فُحِصَت باستخدام خوارزمية البحث بأولوية العمق (DFS) هي : ، ، ، ، ، . graph = { "A" : ["B", "C"], "B" : ["D","E"], "C" : ["F"], "D" : [], "E" : [], "F" : [] } visited DFS = # dfs function [ ] # list to keep track of visited nodes def dfs(visited, graph, node): if node not in visited: print(node, end = " ") visited.append(node) for neighbor in graph[node]: dfs(visited, graph, neighbor) # main program dfs(visited DFS, graph, "A") A B D ECF يُستخدم المكدّس بصورة غير مباشرة عبر مكدس أثناء التشغيل (Runtime Stack) لتتبع الاستدعاءات التكرارية 84

التطبيقات العملية لخوارزمية البحث بأولوية العمق Practical Applications of the DFS Algorithm تُستخدَم خوارزمية البحث بأولوية العمق في إيجاد المسارات (Path Finding) لاستكشاف المسارات المختلفة في العمق للخرائط والطرقات والبحث عن المسار الأفضل. تُستخدم خوارزمية البحث بأولوية العمق في حل المتاهات ) Solve Mazes) من خلال اجتياز كل الطرق الممكنة. يُمكن تحديد الدورات (Cycles) في المخطّط باستخدام خوارزمية البحث بأولوية العمق من خلال وجود حافة خلفية Back Edge ، تمر من خلال العقدة نفسها مرتين. جدول :2.4 مقارنة بين خوارزمية البحث بأولوية الاتساع (BFS) وخوارزمية البحث بأولوية العمق (DFS) خوارزمية البحث بأولوية الاتساع (BFS) خوارزمية البحث بأولوية العمق (DFS) معايير المقارنة طريقة التنفيذ التنقل حسب مستوى الشجرة. هيكل البيانات الاستخدام التنقل حسب عُمق الشجرة. تستخدم هيكل بيانات الطابور لتتبع الموقع تستخدم هيكل بيانات المكدس لتتبع التالي لفحصه. الموقع التالي لفحصه. يُفضّل استخدامها عندما يكون هيكل يُفضّل استخدامها عندما يكون هيكل المخطّط واسعًا وقصيرًا. المخطّط ضيقًا وطويلا. تبحث عن مسار الوجهة باستخدام أقل يتجة البحث إلى قاع الشجرة الفرعية طريقة البحث عدد من الحواف. ثم يتراجع. العقد التي تُفحص في فحص عقد الأشقاء قبل الفروع. فحص عقد الفروع قبل الأشقاء. البداية 85 وزارة التعليم Ministry of Education 2024-1446

86 1 تمرينات حدد الجملة الصحيحة والجملة الخاطئة فيما يلي: .1 تُنفّذ خوارزمية البحث بأولوية الاتساع (BFS) وخوارزمية البحث بأولوية العمق (DFS) باستخدام الاستدعاء الذاتي. 2. لا يمكن استخدام خوارزمية البحث بأولوية الاتساع (BFS) وخوارزمية البحث بأولوية العمق (DFS) في هيكل بيانات الشجرة. 3 تنفذ خوارزمية البحث بأولوية الاتساع (BFS) بمساعدة هيكل بيانات القائمة المترابطة. .4. يمكن تنفيذ خوارزمية البحث بأولوية العمق (DFS) بمساعدة هيكل بيانات المكدّس. 5. لا يمكن استخدام خوارزمية البحث بأولوية الاتساع (BFS ) في البث الشبكي. 2 3 صحيحة خاطئة اشرح كيف تعمل خوارزمية البحث بأولوية الاتساع (BFS) وخوارزمية البحث بأولوية العمق (DFS). قارن بين خوارزمية البحث بأولوية الاتساع (BFS) وخوارزمية البحث بأولوية العمق (DFS). وزارة التعليم Ministry of Education 2024-1446

87 وزارة التعليم Ministry of Education 2024-1446 A B C E F G H K L M J 4 في المخطط على اليسار، انتقل من عقدة البداية A إلى عقدة الهدف .. طبق خوارزمية البحث بأولوية الاتساع (BFS) وخوارزمية البحث بأولوية العمق (DFS) باستخدام هيكل البيانات المناسب المكدّس أو الطابور)، مع الإشارة إلى العقد التي فُحِصَت.

5 اكتب دالة بلغة البايثون تستخدم خوارزمية البحث بأولوية الاتساع (BFS) في مُخطَّط للتحقق مما إذا كان هناك مسار بين عُقدتين مُعطاتين. اكتب دالة بلغة البايثون تستخدم خوارزمية البحث بأولوية العمق (DFS) لإيجاد المسار الأقصر في مُخطَّط غير موزون وزارة التعليم Ministry of Education 2024-1446 6 88