Programming Exercises - كتاب الذكاء الإصطناعي - الصف 12 - الفصل 1 - المملكة العربية السعودية

سؤال 5: اكتب دالة بلغة البايثون تستخدم خوارزمية البحث بأولوية الاتساع (BFS) في مخطط للتحقق مما إذا كان هناك مسار بين عقدتين معطاتين.

الإجابة: س5: نُنشئ دالة تستقبل المخطط (قائمة تجاور)، وعقدة البداية وعقدة الهدف، ثم تطبّق BFS كالتالي: - نضع عقدة البداية في طابور (Queue). - ننشئ مجموعة visited لتتبع العقد التي تمت زيارتها. - طالما الطابور غير فارغ: - نُخرج عقدة من الطابور. - إذا كانت هي الهدف ⇐ نُرجع True (يوجد مسار). - وإلا نُدخل جميع جيرانها غير المزورين إلى الطابور ونضيفهم إلى visited. - إذا انتهى الطابور دون الوصول للهدف ⇐ نُرجع False (لا يوجد مسار).

خطوات الحل:

1. **الشرح:** لنفهم هذا السؤال. المطلوب هو كتابة دالة في لغة بايثون تستخدم خوارزمية البحث بأولوية الاتساع (BFS) للتحقق من وجود مسار بين عقدتين في مخطط (Graph). الفكرة هنا هي أن خوارزمية BFS تبدأ من عقدة البداية وتستكشف جميع العقد المجاورة لها أولاً (أي المستوى نفسه) قبل الانتقال إلى العقد الأبعد. هذا يجعلها مناسبة للتحقق من وجود مسار في مخطط غير موزون. لتنفيذ ذلك، نتبع المنطق التالي: 1. نستخدم بنية بيانات الطابور (Queue) لأن BFS تعمل بمبدأ "أول ما يدخل أول ما يخرج" (FIFO). 2. نحتفظ بمجموعة (Set) لتتبع العقد التي تمت زيارتها حتى لا نزور نفس العقدة مرتين. 3. نبدأ بوضع عقدة البداية في الطابور وفي المجموعة. 4. ثم ندخل في حلقة: طالما الطابور غير فارغ، نُخرج عقدة منه ونتحقق: - إذا كانت هذه العقدة هي عقدة الهدف، فهذا يعني وجدنا مساراً، ونرجع True. - إذا لم تكن الهدف، نضيف جميع جيرانها (من قائمة التجاور) الذين لم تتم زيارتهم إلى الطابور والمجموعة. 5. إذا انتهت الحلقة ولم نجد الهدف، فهذا يعني لا يوجد مسار، ونرجع False. إذن الإجابة هي: كتابة دالة بهذا المنطق، حيث نمرر لها المخطط (ممثلاً بقائمة تجاور)، وعقدة البداية، وعقدة الهدف، ثم نطبق الخطوات المذكورة.

سؤال 6: اكتب دالة بلغة البايثون تستخدم خوارزمية البحث بأولوية العمق (DFS) لإيجاد المسار الأقصر في مخطط غير موزون.

الإجابة: س6: نُنشئ دالة تستقبل المخطط والبداية والهدف، وتستخدم DFS مع تتبع جميع المسارات ثم تختار الأقصر كالتالي: - نُعرّف متغيراً shortest_path (في البداية: لا يوجد). - نُجري DFS (استدعاء ذاتي) مع مسار حالي path يبدأ بـ[البداية]. - عند الوصول إلى الهدف: - نقارن طول المسار الحالي بطول shortest_path، ونُحدّثه إذا كان الحالي أقصر. - أثناء التوسّع: - نزور الجيران بشرط ألا يكون الجار موجودًا في path (لتجنب الدورات). - يمكن تقليم البحث: إذا أصبح طول path الحالي ≥ طول shortest_path نتوقف. - في النهاية نُرجع shortest_path أو None.

خطوات الحل:

1. **الشرح:** هذا السؤال يطلب كتابة دالة في بايثون تستخدم خوارزمية البحث بأولوية العمق (DFS) لإيجاد المسار الأقصر في مخطط غير موزون. لاحظ أن DFS عادةً لا تضمن إيجاد المسار الأقصر في مخطط غير موزون لأنها تستكشف بعمق أولاً، وقد تجد مساراً طويلاً قبل القصير. لذلك، نحتاج إلى تعديلها لتتبع جميع المسارات الممكنة والمقارنة بينها. الفكرة هنا هي: 1. نستخدم DFS بشكل متكرر (استدعاء ذاتي) لاستكشاف جميع المسارات من البداية إلى الهدف. 2. نحتفظ بمسار حالي (path) أثناء التنقل، ونبدأه بعقدة البداية. 3. عند الوصول إلى عقدة الهدف، نقارن طول المسار الحالي بأقصر مسار وجدناه حتى الآن (نخزنه في متغير مثل shortest_path). إذا كان المسار الحالي أقصر، نحدث shortest_path. 4. أثناء التوسع، نزور جيران العقدة الحالية، بشرط ألا يكون الجار موجوداً بالفعل في المسار الحالي (لتجنب الدورات). 5. يمكن تحسين الكفاءة بتقليم البحث: إذا أصبح طول المسار الحالي مساوياً أو أكبر من طول shortest_path الحالي، نتوقف عن الاستكشاف من هذا الفرع لأنه لن يعطينا مساراً أقصر. 6. في النهاية، بعد استكشاف جميع الاحتمالات، نرجع shortest_path إذا وجد، أو None إذا لم يوجد مسار. إذن الإجابة هي: كتابة دالة تطبق هذا المنطق، حيث نمرر المخطط والبداية والهدف، ونستخدم DFS مع تتبع المسارات والمقارنة لإيجاد الأقصر.

سؤال 5: اكتب دالة بلغة البايثون تستخدم خوارزمية البحث بأولوية الاتساع (BFS) في مخطط للتحقق مما إذا كان هناك مسار بين عقدتين معطاتين.

• أ) استخدام قائمة انتظار (queue) وتتبع العقد المفحوصة
• ب) استخدام مكدس (stack) وتتبع العقد المفحوصة
• ج) استخدام خوارزمية ديكسترا (Dijkstra) للبحث عن المسار
• د) استخدام البحث الثنائي (binary search) على العقد

الإجابة الصحيحة: def bfs_path_exists(graph, start, target): from collections import deque visited = set() queue = deque([start]) visited.add(start) while queue: node = queue.popleft() if node == target: return True for neighbor in graph.get(node, []): if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) return False

الشرح: تستخدم الدالة BFS للبحث عن المسار بين عقدتين في مخطط تمثيله كقاموس (graph). تبدأ من العقدة start وتستمر حتى تصل إلى target أو تنتهي جميع العقد. تستخدم قائمة انتظار (deque) و مجموعة visited لتتبع العقد المفحوصة.

تلميح: تأكد من استخدام قائمة انتظار (queue) لتطبيق BFS، وتجنب العقد المكررة باستخدام visited set.

سؤال 6: اكتب دالة بلغة البايثون تستخدم خوارزمية البحث بأولوية العمق (DFS) لإيجاد المسار الأقصر في مخطط غير موزون.

• أ) استخدام العودية (recursion) ومقارنة أطوال المسارات
• ب) استخدام قائمة انتظار (queue) وحساب المسافات
• ج) استخدام خوارزمية بلمان-فورد (Bellman-Ford) للبحث
• د) استخدام البحث الخطي (linear search) على العقد

الإجابة الصحيحة: def dfs_shortest_path(graph, start, target): def dfs(node, path, visited): if node == target: return path + [node] visited.add(node) shortest = None for neighbor in graph.get(node, []): if neighbor not in visited: new_path = dfs(neighbor, path + [node], visited.copy()) if new_path and (shortest is None or len(new_path) < len(shortest)): shortest = new_path return shortest result = dfs(start, [], set()) return result if result else []

الشرح: تستخدم الدالة DFS العودية للبحث عن جميع المسارات من start إلى target في مخطط غير موزون، ثم تختار الأقصر. تتبع المسار الحالي (path) والعقد المفحوصة (visited) لتجنب الدوران.

تلميح: استخدم العودية (recursion) لاستكشاف جميع المسارات، وقارن أطوالها لإيجاد الأقصر.

اكتب دالة بلغة بايثون تستخدم خوارزمية البحث بأولوية الاتساع (BFS) للتحقق من وجود مسار بين عقدتين في مخطط.

الإجابة: تتضمن الدالة إعداد قائمة انتظار (queue) تحتوي على عقدة البداية، ومجموعة لتتبع العقد التي تمت زيارتها. يتم استخراج عقدة من قائمة الانتظار، وفحص جيرانها، وإضافتهم إلى قائمة الانتظار إذا لم تتم زيارتهم. تستمر العملية حتى يتم العثور على العقدة الهدف أو تفريغ قائمة الانتظار.

الشرح: خوارزمية BFS تستكشف المخطط على مستويات، مما يضمن العثور على أقصر مسار في حالة وجوده، وتستخدم هنا للتحقق من الاتصال بين عقدتين.

تلميح: فكر في هيكل البيانات الذي يساعد في استكشاف المخطط طبقة بعد طبقة.

ما هي خوارزمية البحث بأولوية العمق (DFS) المستخدمة لإيجاد المسار الأقصر في مخطط غير موزون؟

الإجابة: تستخدم خوارزمية DFS بنية بيانات مكدس (stack) أو الاستدعاء الذاتي لاستكشاف كل فرع من المخطط إلى أقصى عمق ممكن قبل التراجع. لإيجاد المسار الأقصر في مخطط غير موزون، يتم مقارنة طول كل مسار تم العثور عليه وتسجيل المسار الأقصر.

الشرح: بينما DFS مناسبة لاستكشاف جميع المسارات الممكنة، إلا أن البحث بأولوية الاتساع (BFS) هو الأكثر كفاءة لإيجاد أقصر مسار في المخططات غير الموزونة. ومع ذلك، يمكن استخدام DFS مع تعديلات لتتبع المسارات القصيرة.

تلميح: تخيل أنك تتتبع طريقًا في متاهة، وتتعمق في كل منعطف حتى تصل إلى طريق مسدود، ثم تعود لتجربة طريق آخر.

اشرح كيف يمكن تحسين خوارزمية البحث بأولوية العمق (DFS) لإيجاد المسار الأقصر في مخطط غير موزون.

الإجابة: لتحسين DFS لإيجاد المسار الأقصر، يمكن تتبع طول المسار الحالي أثناء التنقل. عند الوصول إلى عقدة، يتم مقارنة طول المسار الحالي بالمسار الأقصر المسجل حتى الآن، وتحديث المسار الأقصر إذا كان المسار الحالي أقصر. يجب الانتباه إلى تجنب الحلقات اللانهائية في المخططات.

الشرح: الطبيعة الاستكشافية لـ DFS تمكنها من إيجاد مسارات، لكن تتبع طول المسار وإجراء مقارنات دورية يسمح لها بتحديد المسار الأقصر، على الرغم من أن BFS لا يزال الأسلوب الأمثل للمخططات غير الموزونة.

تلميح: ما هي المعلومات الإضافية التي تحتاج لتتبعها أثناء تتبع المسار باستخدام DFS؟