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

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

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

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

الگوریتم بازگشتی بازگشتی یک روش جستجوی عمقی برای تولید پیچ ​​و خم های کامل (پیچ وخم های بدون حلقه و یک مسیر واحد بین هر دو نقطه) است. این ساده، کارآمد است و پیچ و خم های بصری جذابی با راهروهای طولانی و پیچ در پیچ ایجاد می کند.

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

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

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

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

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

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