توليد متاهة بالبحث في العمق: ابن الممرات ثم اختبر اتصالها

يمكن توليد متاهة بزيارة الخلايا بالبحث في العمق وفتح الممرات عند الانتقال إلى خلايا جديدة. ينشر مرجع برنستون تطبيقًا لهذا الأسلوب. [1]

سنكتب تنفيذًا صغيرًا مختلفًا، ونحفظ الممرات كأزواج خلايا. ثم نطرح أسئلة أدق من «هل يبدو الرسم متاهة؟»: هل تصل إلى كل الخلايا؟ هل يوجد طريق دائري؟ وهل تطابق الجدران المرسومة الممرات التي يحتفظ بها البرنامج؟ المثال شبكة من خمسة صفوف وستة أعمدة، وله سجل خطوات يمكن مراجعته.

الخلاصة السريعة

• ابدأ بجدران مغلقة، وافتح ممرًا فقط عند الانتقال إلى خلية لم تُزر من قبل.
• احفظ المسار الجاري في مكدس؛ عند انسداد التقدم ارجع إلى الخلية السابقة دون فتح ممر جديد.
• مثالنا يحوي 30 خلية و29 ممرًا داخليًا، وجميع خلاياه متصلة ولا يحتوي دورة.
• المسار المحسوب من (0,0) إلى (4,5) يمر عبر 13 ممرًا، لا عبر جميع الممرات.
• اختبرنا 48 متاهة و245 تحققًا، منها فحص خلل متعمد بالحذف وآخر بالإضافة.

حدّد الخلية والممر قبل رسم الجدار

نكتب الخلية بصيغة (row, column)، وتبدأ الأرقام من الصفر. الخلية (0,0) أعلى اليسار، بينما (4,5) أسفل اليمين. نسمح بالحركة إلى جار يشارك الخلية ضلعًا؛ لا حركة قطرية. الممر بين خليتين غير موجه، لذلك يحفظ الاتصال في الاتجاهين حتى لو سُجلت خطوة فتحه من الأولى إلى الثانية.

هذه نقطة عملية مهمة: الخط البرتقالي في الصورة يربط مراكز الخلايا، بينما الجدار يقع على حدودها. لا ترسم الجدران مباشرة من سجل الزيارات؛ الزيارة حدث في الزمن، والممر جزء باقٍ من المتاهة. نحفظ قائمة الممرات أولًا، ثم نرسم كل حد داخلي ليس في القائمة جدارًا. هكذا لا يضيف الرجوع في السجل فتحة جديدة بالخطأ.

كيف يعمل الرجوع بالمكدس؟

في البحث بالعمق تُعلَّم العقدة عند زيارتها، ثم تُستكشف عقد مجاورة غير معلّمة. ويعرّف مرجع برنستون الشجرة بأنها رسم متصل خالٍ من الدورات. [2]

في تنفيذنا نضع البداية في قائمة تمثل المكدس. ننظر إلى آخر عنصر فيها، ونكوّن قائمة جيرانه الذين لم تُزر خلاياهم. إذا بقي خيار نختار واحدًا، ونسجل الممر ونعلّم الجار قبل دفعه إلى المكدس. وإذا لم يبق خيار نحذف آخر عنصر. يتكرر ذلك حتى يفرغ المكدس. يجب ألا تحذف علامة الزيارة عند الرجوع؛ لو فعلت، فقد تعامل خلية قديمة كأنها جديدة وتفتح دورة.

عند تنفيذ المثال ظهرت الخطوات التالية. الأرقام في عمود العمق هي عدد الخلايا المحفوظة في المكدس بعد الحدث. الصف الأخير يوضح أن الرجوع يستخدم ممرًا موجودًا ولا يزيد عدد الممرات المفتوحة.

تنفيذ يعيد قائمة ممرات قابلة للفحص

يحافظ هذا المثال على ترتيب الجيران: أعلى، يمين، أسفل، يسار. البذرة تثبت اختيارات هذا التنفيذ، لكنها لا تكفي لإعادة الصورة إذا غيرت ترتيب قائمة الجيران أو آلية الاختيار. شغّلناه باستخدام بايثون 3.12.14.

from random import Random

def maze(rows, cols, seed):
    if rows < 1 or cols < 1:
        raise ValueError("positive dimensions required")
    rng = Random(seed)
    seen = {(0, 0)}
    stack = [(0, 0)]
    passages = []
    while stack:
        r, c = stack[-1]
        neighbors = [(r-1,c), (r,c+1), (r+1,c), (r,c-1)]
        options = [q for q in neighbors
                   if 0 <= q[0] < rows and 0 <= q[1] < cols
                   and q not in seen]
        if not options:
            stack.pop()
            continue
        q = rng.choice(options)
        passages.append(((r, c), q))
        seen.add(q)
        stack.append(q)
    return passages

print(len(maze(5, 6, 73)))  # 29

القائمة الناتجة لا تحتوي الممر نفسه مرتين في اتجاهين متعاكسين؛ إنها تسجل فتحه مرة واحدة. عند بناء قائمة المجاورات للفحص نضيف العلاقة في الاتجاهين. أما حدود الشبكة فتُستبعد قبل الاختيار، ولذلك لا تحتاج خلية وهمية خارج الورقة كي تمنع الخروج منها.

لماذا ينتج اتصال بلا دورات؟

يمكن متابعة حجة بسيطة مع كل خطوة: البداية وحدها متصلة بنفسها. حين تفتح ممرًا إلى خلية جديدة تضيف عنصرًا واحدًا موصولًا بالمجموعة القديمة، ولا تصل نقطتين كانتا موصولتين سابقًا؛ فلا تنشئ دورة. بعد زيارة k خلايا يكون عدد الممرات k−1. عند اكتمال ثلاثين خلية نصل إلى تسعة وعشرين ممرًا.

ويبقى سؤال الاكتمال: هل يمكن أن يفرغ المكدس وتبقى خلية لم نزُرها؟ شبكتنا المستطيلة متصلة أصلًا من حيث الجيران الممكنين. لو بقي جزء لم نَزُره، لوجد حد بين خلية سبق أن زرناها وأخرى لم نزرها. كان يجب أن يبقى هذا الجار خيارًا قبل إخراج الخلية التي سبق أن زرناها من المكدس، وهذا يناقض شرط الرجوع. يعتمد الاستنتاج على تنفيذ الشروط كما كُتبت وعلى عدم وجود خلايا محذوفة من الشبكة.

لا يكفي العدد 29 وحده لضمان نجاح الملف: قد تحتوي قائمة معيبة دورة في جهة ومنطقة منفصلة في جهة أخرى مع العدد الكلي نفسه. لهذا نفحص الوصول والدورات مستقلين عن عدد الممرات. وبوجود اتصال خالٍ من الدورات يكون بين أي خليتين مسار بسيط واحد؛ أي مسارين مختلفين سيشكلان دورة عند اجتماعهما.

اختبارات تقبل الصحيح وتكشف خطأ مقصودًا

ولّدنا ستة أحجام، منها خلية واحدة وصف واحد وعمود واحد، عند ثماني بذور لكل حجم. لكل متاهة تحققنا من عدد الممرات، والتجاور الجانبي، ووصول بحث بالعرض إلى جميع الخلايا، وغياب الدورات بفحص مجموعات منفصل، وإعادة النتيجة عند تكرار البذرة. هذه خمسة فحوص لكل حالة، أي 240 تحققًا.

أضفنا ثلاث حالات أبعاد غير مقبولة، ثم أجرينا تعديلين على مثال الثلاثين خلية. حذف الممر بين (0,0) و(1,0) فصل البداية عن بقية المتاهة. وإضافة ممر بين (0,0) و(0,1) أنشأت دورة. نجح الفحص في كشف العيبين، فأصبح مجموع التحققات 245.

استخرجنا الحل بعد التوليد ببحث مستقل يحفظ الأب لكل خلية. أعطى 14 خلية في المسار، أي 13 انتقالًا. الفرق بين عدّ الخلايا وعدّ الممرات مهم هنا أيضًا: البداية محسوبة ضمن الخلايا، لكنها لا تحتاج انتقالًا للوصول إلى نفسها. لا يعني هذا أن البحث بالعمق يبحث عمومًا عن أقصر طريق في أي رسم؛ خاصية المسار الوحيد تخص المتاهة التي بنيناها.

غيّر التجربة مع إبقاء معيار الصحة

غيّر البذرة أولًا وأبقِ الأبعاد وترتيب الجيران ثابتين، ثم قارن مواضع النهايات المغلقة وطول الحل. صحة الاتصال لا تعطي وحدها درجة لصعوبة اللغز، ولم نقس زمن حل بشري أو ندّع تساوي احتمالات جميع المتاهات الممكنة. قد يعيد اختياران عشوائيان مختلفان البنية نفسها، فلا تستخدم البذرة بديلًا من مقارنة الممرات إذا أردت منع تكرار الألغاز.

بعد ذلك افتح جدارًا إضافيًا عمدًا وشاهد كيف تتغير نتيجة فحص الدورات، أو احذف ممرًا وشاهد فحص الوصول. بهذه التجربة يصبح الاختبار مرتبطًا بخطأ يمكن ملاحظته. وللمقارنة مع استعمال آخر للعقد والروابط اقرأ استرجاع الرسوم البيانية ونوع العلاقة؛ هنا الجيران يصفون إمكانية الحركة في شبكة محددة.

المصادر

1. Princeton — Maze.java
2. Princeton — Undirected Graphs

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