إيجاد المسار في المتاهة – BFS و DFS و A*

ماذا تعرض

تُمثَّل المتاهة بشبكة من الخلايا؛ وكل حركة تنقل إلى خلية مجاورة في الأعلى أو الأسفل أو اليمين أو اليسار، ولكل الحركات الكلفة نفسها. يحفظ البحث بالعرض أولًا الخلايا المنتظرة في طابور، فيستكشف كل الخلايا التي تبعد خطوة واحدة، ثم خطوتين، وهكذا؛ لذلك يكون لديه أقصر مسار في أول مرة يبلغ فيها الهدف. أما البحث بالعمق أولًا فيستخدم مكدسًا ويتبع اتجاهًا واحدًا حتى يعلق، فيكون مساره في الغالب أطول. وترتّب خوارزمية A* الخلايا بحسب f = g + h، حيث h هي مسافة مانهاتن إلى الهدف.

طريقة الاستخدام

اختر BFS أو DFS أو A* واضغط «خطوة» لتتابع الخلايا المنتظرة المرقّمة، أو «▶ تشغيل» لرؤية الحركة. قارن جدول النتائج بعد كل تشغيل. استخدم «رسم جدران» و«مسح جدران» و«نقل البداية» و«نقل الهدف» لتغيير الشبكة، أو اختر «نوع الشبكة» واضغط «شبكة جديدة».

المعاملات القابلة للتغيير

• الخوارزمية BFS – البحث بالعرض أولًا, DFS – البحث بالعمق أولًا, A* – بتوجيه من تقدير المسافة
• نوع الشبكة متاهة فيها حلقات, عوائق عشوائية, شبكة فارغة
• عدد أعمدة الشبكة 11–41 خلية
• الجدران الإضافية المزالة (المتاهة) 0–60 %
• كثافة العوائق 0–45 %
• سرعة التشغيل 1–100 خطوة/s

أسئلة للاستكشاف

1. لماذا يكون المسار الذي يجده BFS أقصر مسار دائمًا، بينما لا يكون مسار DFS كذلك في الغالب؟
2. في شبكة فارغة، أي خوارزمية تستكشف أقل عدد من الخلايا، ولماذا؟
3. هل يمكنك بناء متاهة يبلغ فيها DFS الهدف بعد استكشاف خلايا أقل مما يستكشفه BFS؟