مولد پیچ ​​و خم عقبگرد بازگشتی

الگوریتم بازگشتی backtracker در واقع یک جستجوی عمق-اول همه منظوره است. وقتی برای تولید هزارتو استفاده می‌شود، کمی تغییر می‌کند تا مسیر را به صورت تصادفی انتخاب کند، در حالی که اگر برای اهداف جستجوی واقعی استفاده شود، معمولاً فقط هر سطح را به ترتیب خطی جستجو می‌کند. این الگوریتم تمایل دارد هزارتوهایی با راهروهای طولانی و پر پیچ و خم و یک راه حل بسیار طولانی و پیچ در پیچ تولید کند.

پیچ و خم کامل، پیچ و خم هایی است که در آن دقیقاً یک مسیر از هر نقطه در پیچ و خم به هر نقطه دیگر وجود دارد. این بدان معناست که شما نمی توانید در نهایت به دور زدن در دایره بپردازید، اما اغلب با بن بست هایی روبرو می شوید که شما را وادار می کند که بچرخید و به عقب برگردید.

نقشه های پیچ و خم تولید شده در اینجا شامل یک نسخه پیش فرض بدون هیچ موقعیت شروع و پایان است، بنابراین شما می توانید آن ها را برای خود تصمیم بگیرید: از هر نقطه در پیچ و خم تا هر نقطه دیگر راه حلی وجود خواهد داشت. اگر می خواهید الهام بگیرید، می توانید یک موقعیت پیشنهادی شروع و پایان را فعال کنید - و حتی راه حل بین این دو را ببینید.

الگوریتم بازگشتیِ پس‌گرد (recursive backtracker algorithm) یک روش جستجوی عمق-اول برای تولید هزارتوهای کامل (هزارتوهایی بدون حلقه و دارای یک مسیر واحد بین هر دو نقطه) است. این الگوریتم ساده و کارآمد است و هزارتوهایی با راهروهای طولانی و پرپیچ‌وخم از نظر بصری جذاب تولید می‌کند.

برخلاف نامش، لزوماً نباید با استفاده از بازگشت پیاده‌سازی شود. اغلب با رویکردی تکراری و با استفاده از صف LIFO (یعنی یک پشته) پیاده‌سازی می‌شود. برای هزارتوهای بسیار بزرگ، استفاده از بازگشت، بسته به زبان برنامه‌نویسی و حافظه موجود، احتمالاً منجر به سرریز پشته فراخوانی می‌شود. صف LIFO را می‌توان راحت‌تر برای مدیریت حجم زیادی از داده‌ها تطبیق داد، حتی اگر حافظه موجود کافی نباشد، صف را روی دیسک یا در پایگاه داده نگه داشت.

چگونه کار می‌کند؟

این الگوریتم با استفاده از رویکرد جستجوی عمقی مبتنی بر پشته عمل می‌کند. در اینجا جزئیات گام به گام آمده است:

1. یک سلول شروع انتخاب کنید و آن را به عنوان بازدید شده علامت گذاری کنید.
2. تا زمانی که سلول‌های بازدید نشده‌ای وجود دارند: به سلول‌های همسایه‌ای که هنوز بازدید نشده‌اند نگاه کنید. اگر حداقل یک همسایه بازدید نشده وجود داشته باشد: به طور تصادفی یکی از همسایه‌های بازدید نشده را انتخاب کنید. دیوار بین سلول فعلی و همسایه انتخابی را بردارید. به همسایه انتخابی بروید و آن را به عنوان بازدید شده علامت‌گذاری کنید. سلول فعلی را به پشته فشار دهید. اگر هیچ همسایه بازدید نشده‌ای وجود ندارد: با برداشتن آخرین سلول از پشته، به عقب برگردید.
3. این روند را تا زمانی که پشته خالی شود ادامه دهید.

یک واقعیت جالب در مورد این الگوریتم این است که هم به عنوان تولیدکننده‌ی هزارتو و هم به عنوان حل‌کننده‌ی هزارتو عمل می‌کند. اگر آن را روی یک هزارتوی از قبل تولید شده اجرا کنید و وقتی به نقطه‌ی پایانی تعیین‌شده رسیدید، متوقف شوید، پشته شامل راه‌حل هزارتو خواهد بود.

من در واقع دو نسخه از این الگوریتم را در این سایت دارم: یک نسخه مبتنی بر صف LIFO برای تولید هزارتوها در این صفحه و یک نسخه مبتنی بر بازگشت برای حل هزارتوها، همچنین هزارتوهایی که توسط الگوریتم‌های دیگر تولید می‌شوند (به این ترتیب نقشه‌های حاوی راه‌حل‌ها ساخته می‌شوند). داشتن دو نسخه مختلف فقط برای سرگرمی است زیرا من یک خوره هستم که آن را جالب می‌دانم، هر کدام می‌توانست برای هر دو کار کند ;-)

مطالعه بیشتر

اگر از این پست لذت بردید، ممکن است این پیشنهادات را نیز بپسندید:

• شکار و کشتن ژنراتور پیچ و خم
• مولد پیچ ​​و خم الگوریتم ویلسون
• مولد پیچ ​​و خم الگوریتم الر