الگوریتم Kruskal مولد پیچ و خم

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

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

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

درباره الگوریتم کروسکال

الگوریتم کروسکال توسط جوزف برنارد کروسکال جونیور، ریاضیدان، آماردان و دانشمند کامپیوتر آمریکایی، ایجاد شد. او اولین بار این الگوریتم را در سال ۱۹۵۶ در مقاله خود با عنوان «درباره کوتاه‌ترین زیردرخت فراگیر یک گراف و مسئله فروشنده دوره‌گرد» شرح داد.

این الگوریتم برای یافتن درخت پوشای کمینه (MST) یک گراف طراحی شده است، و تضمین می‌کند که همه رئوس با حداقل وزن یال کل ممکن به هم متصل هستند و در عین حال از ایجاد چرخه‌ها جلوگیری می‌کند.

نحوه‌ی عملکرد الگوریتم کروسکال برای تولید هزارتو

مرحله ۱: مقداردهی اولیه

• هر سلول در هزارتو را به عنوان یک مجموعه جداگانه (یک جزء منحصر به فرد) در نظر بگیرید.
• تمام دیوارهای بین سلول‌های مجاور را به عنوان لبه‌های بالقوه فهرست کنید.

مرحله 2: مرتب سازی دیوارها

• دیوارها را به صورت تصادفی یا تصادفی مرتب کنید. اگر آن را به عنوان یک الگوریتم واقعی کروسکال پیاده‌سازی می‌کنید، دیوارها را به ترتیب تصادفی مرتب کنید (زیرا تولید هزارتو نیازی به وزن ندارد).

مرحله 3: دیوارها را پردازش کنید

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

مرحله ۴: ادامه تا تکمیل

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

از آنجایی که الگوریتم کروسکال بر ادغام مجموعه‌ها متکی است، می‌توان آن را با استفاده از الگوریتم Union-Find بهینه کرد، که روشی کارآمد برای ردیابی سلول‌های متصل در طول تولید هزارتو فراهم می‌کند. می‌توانید پیاده‌سازی PHP من از الگوریتم Union-Find را اینجا ببینید: لینک

مطالعه بیشتر

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

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