خوارزمية حل المتاهات

خوارزمية حل المتاهة هي طريقة آلية لحل المتاهة . صُممت خوارزميات الفأر العشوائي، وتتبع الجدار، وبليدج، وتاري، وتريموكس ليتم استخدامها داخل المتاهة من قبل مسافر ليس لديه معرفة مسبقة بها، بينما صُممت خوارزميات ملء الطريق المسدود وأقصر مسار ليتم استخدامها من قبل شخص أو برنامج حاسوبي يمكنه رؤية المتاهة بأكملها دفعة واحدة.

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

يمكن تطبيق هذه الطريقة البسيطة بواسطة روبوت بسيط للغاية أو حتى فأر، لأنها لا تتطلب أي ذاكرة. يتابع الروبوت مساره الحالي حتى يصل إلى مفترق طرق، ثم يتخذ قرارًا عشوائيًا بشأن الاتجاه التالي الذي سيسلكه. على الرغم من أن هذه الطريقة ستصل دائمًا إلى الحل الصحيح في النهاية ، إلا أن الخوارزمية قد تكون بطيئة للغاية. ^{[ 2 ]}

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

ثمة منظور آخر لفهم آلية عمل تتبع الجدران، وهو المنظور الطوبولوجي. فإذا كانت الجدران متصلة، فقد تتشكل على هيئة حلقة أو دائرة. ^{[ 3 ]} عندئذٍ، يصبح تتبع الجدران مجرد دوران حول دائرة من البداية إلى النهاية. ولتوضيح هذه الفكرة، لاحظ أنه بتجميع المكونات المتصلة لجدران المتاهة، فإن الحدود بينها هي الحلول نفسها، حتى لو كان هناك أكثر من حل.

إذا لم تكن المتاهة متصلة ببساطة (أي إذا كانت نقاط البداية أو النهاية في مركز الهيكل محاطة بحلقات المرور، أو إذا كانت المسارات تتقاطع فوق بعضها البعض وتحتها، وكانت أجزاء من مسار الحل محاطة بحلقات المرور)، فلن تصل هذه الطريقة بالضرورة إلى الهدف.

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

يمكن تطبيق تتبع الجدران في المتاهات ثلاثية الأبعاد أو ذات الأبعاد الأعلى إذا أمكن إسقاط مساراتها ذات الأبعاد الأعلى على المستوى ثنائي الأبعاد بطريقة حتمية. على سبيل المثال، إذا افترضنا في متاهة ثلاثية الأبعاد أن المسارات "الصاعدة" تؤدي إلى الشمال الغربي، والمسارات "الهابطة" تؤدي إلى الجنوب الشرقي، فإنه يمكن تطبيق قواعد تتبع الجدران القياسية. مع ذلك، وعلى عكس الوضع ثنائي الأبعاد، يتطلب هذا معرفة الاتجاه الحالي لتحديد أي اتجاه هو الأول على اليسار أو اليمين.

يمكن العثور على محاكاة لكيفية عمل هذه الخوارزمية هنا .

يمكن حل المتاهات المنفصلة (حيث لا تتصل الجدران بالحدود الخارجية/الحدود غير مغلقة) باستخدام طريقة تتبع الجدران، بشرط أن يكون مدخل ومخرج المتاهة على جدرانها الخارجية. أما إذا بدأ الحل من داخل المتاهة، فقد يكون في قسم منفصل عن المخرج، وبالتالي ستدور عناصر تتبع الجدران باستمرار حول حلقتها. يمكن لخوارزمية بليدج (المسماة نسبةً إلى جون بليدج من إكستر) حل هذه المشكلة. ^{[ 4 ] [ 5 ]}

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

لا تُرفع اليد عن الجدار إلا عندما يكون كل من "مجموع عدد المنعطفات" و"الاتجاه الحالي" مساويًا للصفر. يسمح هذا للخوارزمية بتجنب الفخاخ التي على شكل حرف "G" كبير. بافتراض أن الخوارزمية تنعطف يسارًا عند الجدار الأول، فإنها تدور دورة كاملة 360 درجة حول الجدران. أما الخوارزمية التي تتعقب "الاتجاه الحالي" فقط، فتؤدي إلى حلقة لا نهائية، حيث تغادر الجدار السفلي الأيمن متجهةً يسارًا، ثم تصطدم بالجزء المنحني على الجانب الأيسر مرة أخرى. لا تغادر خوارزمية "التعهد" الجدار الأيمن لأن "مجموع عدد المنعطفات" لا يساوي صفرًا عند تلك النقطة (لاحظ أن 360 درجة لا تساوي صفرًا ) . تتبع الخوارزمية الجدار بالكامل، لتغادره أخيرًا متجهةً يسارًا للخارج وأسفل شكل الحرف مباشرةً.

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

خوارزمية تريمو، التي اخترعها تشارلز بيير تريمو ، ^{[ 6 ]} هي طريقة فعالة لإيجاد مخرج من متاهة تتطلب رسم خطوط على الأرض لتحديد مسار، وهي مضمونة العمل لجميع المتاهات التي تحتوي على ممرات محددة جيدًا، ^{[ 7 ]} ولكنها ليست مضمونة لإيجاد أقصر طريق.

مدخل الممر إما غير مُزار، أو مُعلّم مرة واحدة، أو مُعلّم مرتين. لا يُعدّ تعليم المدخل مُرادفًا لتعليم مفترق طرق أو ممر، لأن مفترق الطرق قد يحتوي على عدة مداخل، بينما يحتوي الممر على مدخل من كلا الطرفين. ويمكن اعتبار الطرق المسدودة بمثابة مفترق طرق ذي مدخل واحد.

تعمل الخوارزمية وفقًا للقواعد التالية:

• عند المرور عبر مدخل، سواء كان ذلك للدخول إلى تقاطع أو الخروج منه، يكون المدخل مُعلَّماً.
• عند الوصول إلى مفترق طرق، تحدد القاعدة الأولى المطبقة المدخل الذي يجب الخروج منه:
  1. إذا كان المدخل الذي مررنا منه للتو فقط هو المُعلّم، فسيتم اختيار مدخل عشوائي غير مُعلّم، إن وُجد. وينطبق هذا الشرط أيضاً في حال عدم وجود مداخل مُعلّمة.
  2. يتم اختيار المدخل الذي مر منه الشخص للتو إذا تم تحديد أي مداخل أخرى، إلا إذا تم تحديده مرتين.
  3. يتم اختيار أي مدخل بأقل عدد من العلامات (صفر إن أمكن، وإلا علامة واحدة).

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

عند الوصول إلى المخرج، تشير المداخل المميزة بعلامة واحدة إلى طريق العودة إلى نقطة البداية. في حال عدم وجود مخرج، تعيد هذه الطريقة الشخص إلى نقطة البداية حيث تكون جميع المداخل مميزة بعلامتين. في هذه الحالة، يُسلك كل ممر مرتين بالضبط، مرة في كل اتجاه. تُسمى هذه العملية بالتتبع المزدوج ثنائي الاتجاه. ^{[ 8 ]}

في الأساس، تم استخدام هذه الخوارزمية، التي تم اكتشافها في القرن التاسع عشر، بعد حوالي مائة عام كبحث في العمق أولاً . ^{[ 9 ] [ 10 ]}

خوارزمية تاري، التي نشرها غاستون تاري عام 1895 في كتابه "مشكلة المتاهات "، هي طريقة لاجتياز المتاهة أو الرسم البياني المتصل غير الموجه دون معرفة مسبقة بتصميم المتاهة. وهي تشبه خوارزمية تريمو في استخدامها لعلامات المتاهة لتسجيل تقدم الاستكشاف. تضمن الخوارزمية اجتياز المتاهة بالكامل وإنهاء المسار؛ حيث يتم اجتياز كل حافة مرتين على الأكثر، مرة في كل اتجاه. ويمكن التعبير عنها بقاعدة واحدة، وصفها موقع MacTutor بأنها "مناسبة بشكل خاص للتنفيذ الحاسوبي": لا تخرج من التقاطع من نفس الطريق الذي دخلت منه حتى يتم استكشاف جميع المخارج الأخرى. وتُعتبر الآن إجراءً مبكرًا يشبه البحث العميق أولًا . ^{[ 11 ] [ 9 ] [ 12 ]}

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

1. اعثر على جميع الطرق المسدودة في المتاهة، ثم
2. قم بـ"ملء" المسار من كل طريق مسدود حتى تصل إلى أول مفترق طرق.

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

لا يمكن لعملية ملء النهايات المسدودة أن تقطع بداية المتاهة عن نهايتها عن طريق الخطأ، لأن كل خطوة من خطوات العملية تحافظ على بنية المتاهة. علاوة على ذلك، لن تتوقف العملية "مبكرًا جدًا" لأن النتيجة لا يمكن أن تحتوي على أي نهايات مسدودة. وبالتالي، إذا تم ملء النهايات المسدودة في متاهة مثالية (متاهة بدون حلقات)، فسيبقى الحل فقط. أما إذا تم ملؤها في متاهة ذات حلقات جزئية (متاهة بها بعض الحلقات)، فستبقى جميع الحلول الممكنة فقط.

إذا توفرت رؤية شاملة للمتاهة، يمكن لخوارزمية تكرارية بسيطة أن تحدد كيفية الوصول إلى النهاية. تُعطى الخوارزمية قيمتي X وY الابتدائيتين. إذا لم تكن هاتان القيمتان على جدار، فستستدعي الخوارزمية نفسها مع جميع القيم المجاورة، للتأكد من عدم استخدامها مسبقًا. أما إذا كانت القيمتان هما قيمتا النهاية، فستحفظ الخوارزمية جميع الاستدعاءات السابقة للخوارزمية كمسار صحيح.

هذا في الواقع بحثٌ متعمقٌ مُعبَّرٌ عنه بنقاط الشبكة. تمنع الرؤية الشاملة الدخول في حلقات تكرارية عن طريق الحفظ. إليك نموذجًا برمجيًا بلغة جافا :

boolean [][] maze = new boolean [ width ][ height ] ; // المتاهة boolean [][] wasHere = new boolean [ width ][ height ] ; boolean [][] correctPath = new boolean [ width ][ height ] ; // حل المتاهة int startX , startY ; // قيمتا البداية X و Y للمتاهة int endX , endY ; // قيمتا النهاية X و Y للمتاهةpublic void solveMaze () { maze = generateMaze (); // إنشاء متاهة (false = path, true = wall)// التعيين أدناه إلى false زائد عن الحاجة لأن Java تُعيّن عناصر المصفوفة إلى false افتراضيًا، ولكن تم تضمينه لأن اللغات الأخرى قد لا تتصرف بنفس الطريقة. for ( int row = 0 ; row < maze.length ; row ++ ) // تعيين المصفوفات المنطقية إلى القيم الافتراضية for ( int col = 0 ; col < maze [ row ] .length ; col ++ ) { wasHere [ row ] [ col ] = false ; correctPath [ row ][ col ] = false ; } boolean b = recursiveSolve ( startX , startY ) ; // سيترك لك مصفوفة منطقية (correctPath) // مع المسار المشار إليه بالقيم true. // إذا كانت b تساوي false، فلا يوجد حل للمتاهة } public boolean recursiveSolve ( int x , int y ) { if ( x == endX && y == endY ) return true ; // إذا وصلت إلى النهاية if ( maze [ x ][ y ] || wasHere [ x ][ y ] ) return false ; // إذا كنت على جدار أو كنت هنا بالفعل wasHere [ x ][ y ] = true ; if ( x != 0 ) // يتحقق مما إذا كنت لست على الحافة اليسرى if ( recursiveSolve ( x - 1 , y )) { // يستدعي الطريقة الأولى إلى اليسار correctPath [ x ][ y ] = true ; // يضبط قيمة هذا المسار إلى true; return true ; } if ( x != width -1 ) // يتحقق مما إذا كان المسار ليس على الحافة اليمنى إذا ( recursiveSolve ( x + 1 , y )) { // يستدعي الطريقة الأولى إلى اليمين correctPath [ x ][ y ] = true ; return true ; } إذا ( y != 0 ) // يتحقق مما إذا كان المسار ليس على الحافة العلوية إذا ( recursiveSolve ( x , y - 1 )) { // يستدعي الطريقة الأولى للأعلى correctPath [ x ][ y ] = true ; return true ; } إذا ( y != height - 1 ) // يتحقق مما إذا كان المسار ليس على الحافة السفلية إذا ( recursiveSolve ( x , y + 1 )) { // يستدعي الطريقة الأولى للأسفل correctPath [ x ][ y ] = true ; return true ; } return false ; }

خوارزمية توجيه المتاهة ^{[ 13 ]} هي طريقة منخفضة التكلفة لإيجاد المسار بين أي موقعين داخل المتاهة. طُرحت الخوارزمية في البداية لمعالجات الرقاقات المتعددة (CMPs)، وهي مضمونة العمل مع أي متاهة شبكية. بالإضافة إلى إيجاد المسارات بين موقعين في الشبكة (المتاهة)، تستطيع الخوارزمية اكتشاف عدم وجود مسار بين نقطة البداية والوجهة. كما يمكن استخدامها من قِبل مستخدم داخلي لا يملك معرفة مسبقة بالمتاهة، مع تعقيد ذاكرة ثابت بغض النظر عن حجم المتاهة؛ إذ تتطلب 4 متغيرات فقط لإيجاد المسار واكتشاف المواقع غير القابلة للوصول. مع ذلك، لا تهدف الخوارزمية إلى إيجاد أقصر مسار.

تعتمد خوارزمية توجيه المتاهة على مفهوم مسافة مانهاتن ، وتستند إلى خاصية الشبكات التي تنص على أن مسافة مانهاتن تزيد أو تنقص بمقدار 1 بالضبط عند الانتقال من موقع إلى أي 4 مواقع مجاورة. إليك الشفرة الزائفة دون إمكانية اكتشاف المواقع التي لا يمكن الوصول إليها.

Point src , dst ; // إحداثيات المصدر والوجهة // cur تشير أيضًا إلى إحداثيات الموقع الحالي int MD_best = MD ( src , dst ); // تخزن أقرب مسافة MD لدينا إلى dst // المسار الأمثل هو الذي يجعل مسافة MD إلى dst أصغر while ( cur != dst ) { if ( there exists a productive path ) { Take the product path ; } else { MD_best = MD ( cur , dst ); تخيل خطًا بين cur و dst ؛ خذ المسار الأول على يسار / يمين الخط ؛ // يؤثر اختيار اليسار/اليمين على قاعدة اليد التالية while ( MD ( cur , dst ) ! = MD_best || there does not exist a product path ) { اتبع قاعدة اليد اليمنى / اليسرى ؛ // عكس الجانب المحدد من الخط } }

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

يشير الاستكشاف الجماعي إلى استكشاف بيئة غير معروفة بواسطة عدة عوامل متحركة تتحرك بنفس السرعة. طُرح هذا النموذج لدراسة إمكانية التوازي في حل المتاهات، ^{[ 14 ]} وخاصة في حالة الأشجار . تعتمد الدراسة على نموذج الاتصال بين العوامل. في نموذج الاتصال المركزي، يُسمح للعوامل بالتواصل فيما بينها في جميع الأوقات. أما في نموذج الاتصال الموزع ، فيمكن للعوامل التواصل فقط عن طريق القراءة والكتابة على جدران المتاهة. بالنسبة للأشجار ذات${\displaystyle n}$العقد والعمق${\displaystyle D}$، مع${\displaystyle k}$الروبوتات، أفضل خوارزمية حالية موجودة في${\displaystyle O\left({\frac {n}{k}}+kD\right)}$في نموذج الاتصالات المركزي وفي${\displaystyle O\left({\frac {n}{\log k}}+D\right)}$في نموذج الاتصال الموزع. ^{[ 14 ]}

• المتاهة
• خوارزمية توليد المتاهة

• فكر في المتاهة: خوارزميات المتاهة (تفاصيل حول هذه الخوارزميات وغيرها من خوارزميات حل المتاهات)
• مدونة المتاهات: حل المتاهات باستخدام تحليل الصور. مؤرشفة بتاريخ ٢٠ سبتمبر ٢٠١٥ على موقع Wayback Machine.
• فيديو: محاكاة حل المتاهة
• سيمون أيرينهاك، التيار الكهربائي يحل المتاهات ، © 2014 IOP Publishing Ltd.