📄 النص الكامل للصفحة
رابط الدرس الرقمي
www.ien.edu.saالدرس الثاني خوارزمية البحث بأولوية العمق والبحث بأولوية الاتساع--- SECTION: البحث في المخططات --- البحث في المخططات
Searching in Graphsهناك بعض الحالات التي تحتاج فيها إلى البحث عن عقدة محددة في المخطط، أو تفحص كل عقدة في المخطط لإجراء عملية بعينها مثل طباعة عقد المخطط. فتكون حالتك كشخص يبحث عن المدينة التي يريد السفر إليها؛ وليتحقق هذا، تحتاج إلى فحص كل عقدة في المخطط حتى تجد تلك التي تحتاج إليها. يُطلق على هذا الإجراء: البحث في المخطط أو مسح المخطط. وهناك العديد من خوارزميات البحث التي تساعد على تنفيذه، مثل:
• خوارزمية البحث بأولوية الاتساع (Breadth-First Search - BFS)
• خوارزمية البحث بأولوية العمق (Depth-First Search - DFS)--- SECTION: مثال على خوارزمية البحث بأولوية العمق (DFS) : حل المتاهة --- مثال على خوارزمية البحث بأولوية العمق (DFS) : حل المتاهة--- SECTION: مثال على خوارزمية البحث بأولوية الاتساع (BFS) : البث الشبكي --- مثال على خوارزمية البحث بأولوية الاتساع (BFS) : البث الشبكي--- SECTION: خوارزمية البحث بأولوية الاتساع --- خوارزمية البحث بأولوية الاتساع
Breadth-First Search (BFS) Algorithmتستكشف خوارزمية البحث بأولوية الاتساع (BFS) المخطط مستوى واحدًا تلو الآخر، حيث تبدأ بفحص عقدة الجذر (العقدة البدائية)، ثم تفحص جميع العقد المرتبطة بها بشكل مباشر واحدة تلو الأخرى. بعد الانتهاء من فحص كل العقد في المستوى، تنتقل إلى المستوى التالي، وتتبع الإجراءات نفسها الموضحة في الشكل 2.6.
يُستخدم الطابور لتتبع العقد التي تم فحصها، وبمجرد استكشاف العقدة، ستتم إضافة العقد الفرعية إلى الطابور، ثم تحذف العقدة التالية الموجودة في أول الطابور التي تم استكشافها سابقًا.--- SECTION: شكل 2.6: خوارزمية البحث بأولوية الاتساع (BFS) --- شكل 2.6: خوارزمية البحث بأولوية الاتساع (BFS)2023 - 1447--- VISUAL CONTEXT ---
**DIAGRAM**: مثال على خوارزمية البحث بأولوية العمق (DFS) : حل المتاهة
Description: A maze diagram illustrating the Depth-First Search (DFS) algorithm. The maze has a complex path structure. A pink dashed line indicates the path taken by the DFS algorithm, starting from an entry point at the top-center and navigating through the maze to an exit point at the bottom-center. The path shows deep exploration into one branch before backtracking.
Context: This diagram visually explains how DFS explores a path completely before backtracking, which is useful for solving mazes by trying one path to its end.**DIAGRAM**: مثال على خوارزمية البحث بأولوية الاتساع (BFS) : البث الشبكي
Description: A network graph illustrating the Breadth-First Search (BFS) algorithm. It features a central grey node labeled 'عقدة البث' (broadcast node). This central node is connected by arrows to several pink-colored nodes, which are labeled 'العقد المجاورة لعقدة البث' (neighboring nodes of the broadcast node). These pink nodes are further connected to white-colored nodes labeled 'العقد الأخرى' (other nodes). The arrows indicate the direction of connection, showing a spread from the central node to its immediate neighbors first.
Key Values: عقدة البث, العقد المجاورة لعقدة البث, العقد الأخرى
Context: This diagram demonstrates how BFS explores nodes level by level, starting from a source node and visiting all its direct neighbors before moving to the next level of nodes, simulating a broadcast.**DIAGRAM**: شكل 2.6: خوارزمية البحث بأولوية الاتساع (BFS)
Description: A hierarchical graph (tree-like structure) illustrating the Breadth-First Search (BFS) algorithm's level-by-level exploration. Node A is at 'المستوى 0' (Level 0). Nodes B and C are at 'المستوى 1' (Level 1), connected to A. Nodes D, E, F, and G are at 'المستوى 2' (Level 2), connected to B and C. Numbered pink arrows (1 to 6) indicate the order of exploration: A to B (1), A to C (2), B to D (3), B to E (4), C to F (5), C to G (6). The dashed lines represent connections between nodes, and the numbers on the arrows show the sequence of visiting nodes in a BFS traversal.
Key Values: A, B, C, D, E, F, G, المستوى 0, المستوى 1, المستوى 2, 1, 2, 3, 4, 5, 6
Context: This diagram provides a step-by-step visual representation of BFS, showing how it systematically explores nodes level by level, which is crucial for understanding its mechanism and the order of node visitation.
🎴 بطاقات تعليمية للمراجعة
عدد البطاقات: 5 بطاقة لهذه الصفحة
ما هو الإجراء الذي يُطلق عليه "البحث في المخطط" أو "مسح المخطط"؟
الإجابة: هو الإجراء الذي يتطلب البحث عن عقدة محددة في المخطط، أو تفحص كل عقدة في المخطط لإجراء عملية بعينها مثل طباعة عقد المخطط.
الشرح: هذا الإجراء ضروري عندما تحتاج إلى تحديد موقع معلومة معينة داخل هيكل بيانات معقد مثل المخطط، أو لتنفيذ عملية شاملة على جميع مكوناته.
تلميح: فكر في الهدف الأساسي من إجراء استكشاف كامل لعناصر المخطط.
اذكر اثنتين من خوارزميات البحث الشائعة المستخدمة في المخططات.
الإجابة: خوارزمية البحث بأولوية الاتساع (BFS) وخوارزمية البحث بأولوية العمق (DFS).
الشرح: هاتان الخوارزميتان هما من الطرق الأساسية لاستكشاف المخططات، ولكل منهما منهجية مختلفة في ترتيب زيارة العقد.
تلميح: ابحث عن الاختصارات BFS و DFS في النص، ثم استخرج الأسماء الكاملة للخوارزميات التي تمثلها.
كيف تعمل خوارزمية البحث بأولوية الاتساع (BFS)؟
الإجابة: تبدأ بفحص عقدة الجذر، ثم تفحص جميع العقد المرتبطة بها بشكل مباشر واحدة تلو الأخرى (المستوى الأول). بعد الانتهاء من فحص كل العقد في المستوى، تنتقل إلى المستوى التالي وتكرر نفس الإجراء.
الشرح: تتبع BFS مبدأ الاستكشاف الأفقي، حيث تزور كل عقدة قريبة قبل الانتقال إلى العقد الأبعد. يُستخدم الطابور (Queue) لتتبع العقد التي تم فحصها.
تلميح: ركز على طريقة استكشاف الخوارزمية للعقد، هل تتعمق في فرع واحد أم تستكشف كل العقد في نفس المستوى أولاً؟
ما هي الأداة المستخدمة في خوارزمية البحث بأولوية الاتساع (BFS) لتتبع العقد التي تم فحصها؟
الإجابة: يُستخدم الطابور (Queue) لتتبع العقد التي تم فحصها.
الشرح: الطابور هو هيكل بيانات مثالي لـ BFS لأنه يسمح بإضافة العقد الفرعية عند اكتشافها (إلى نهاية الطابور) ثم معالجة العقد بترتيب اكتشافها (من بداية الطابور)، مما يضمن استكشاف المخطط مستوى بمستوى.
تلميح: فكر في هيكل البيانات الذي يسمح بإضافة العناصر في نهاية واستخراجها من البداية، وهو ما يتماشى مع مبدأ "أول ما يدخل، أول ما يخرج" (FIFO).
ما هو المبدأ الأساسي الذي تتبعه خوارزمية البحث بأولوية العمق (DFS) كما هو موضح في حل المتاهة؟
الإجابة: تتعمق الخوارزمية في استكشاف فرع واحد من المتاهة إلى أقصى حد ممكن قبل الرجوع (Backtracking) وتجربة فرع آخر.
الشرح: DFS تستكشف المسار الأعمق أولاً، وهذا يجعلها فعالة في حل المتاهات أو تتبع المسارات المتشعبة حيث قد يكون الحل في نهاية مسار طويل.
تلميح: انظر إلى وصف الرسم البياني للمتاهة، وكيف يصف مسار البحث.