Penjana Maze Algoritma Kruskal

Algoritma Kruskal ialah algoritma pokok rentang minimum yang boleh disesuaikan untuk penjanaan maze. Ia amat berkesan untuk mencipta labirin yang sempurna. Alternatif kepada algoritma Kruskal ialah algoritma Prim, yang juga merupakan algoritma pepohon rentang minimum, tetapi memandangkan ia menghasilkan maze yang sama dan larian Kruskal lebih pantas, saya tidak peduli untuk melaksanakan Prim.

Labirin yang sempurna ialah labirin di mana terdapat betul-betul satu laluan dari mana-mana titik dalam mez ke mana-mana titik lain. Ini bermakna anda tidak boleh mengelilingi dalam bulatan, tetapi anda sering menemui jalan buntu, memaksa anda untuk berpusing dan kembali.

Peta maze yang dijana di sini termasuk versi lalai tanpa sebarang kedudukan mula dan penamat, jadi anda boleh memutuskannya sendiri: akan ada penyelesaian dari mana-mana titik dalam maze ke mana-mana titik lain. Jika anda mahukan inspirasi, anda boleh mendayakan kedudukan permulaan dan penamat yang dicadangkan - malah melihat penyelesaian antara kedua-duanya.

Tentang Algoritma Kruskal

Algoritma Kruskal dicipta oleh Joseph Bernard Kruskal, Jr., seorang ahli matematik, statistik, dan saintis komputer Amerika. Beliau pertama kali menerangkan algoritma ini pada tahun 1956 dalam kertas kerja beliau "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem."

Algoritma ini direka untuk mencari pokok penutupan minimum (MST) bagi graf, memastikan bahawa semua titik disambungkan dengan berat tepi total yang paling minima sambil mengelakkan kitaran.

Bagaimana Algoritma Kruskal Berfungsi untuk Penjanaan Labirin

Langkah 1: Inisialisasi

• Anggap setiap sel dalam labirin sebagai set yang berasingan (komponen unik).
• Senaraikan semua dinding antara sel yang bersebelahan sebagai tepi yang berpotensi.

Langkah 2: Susun Dinding

• Kocakkan atau susun dinding secara rawak. Jika melaksanakan algoritma Kruskal yang sebenar, susun dinding mengikut urutan rawak (kerana penjanaan labirin tidak memerlukan berat).

Langkah 3: Proses Dinding

• Iterasi melalui dinding yang telah dikocakkan.
• Jika dua sel yang dibahagikan oleh dinding itu tergolong dalam set yang berbeza (iaitu, mereka belum disambungkan dalam labirin), keluarkan dinding tersebut dan gabungkan set-set tersebut.
• Jika mereka sudah berada dalam set yang sama, lepaskan dinding tersebut (untuk mengelakkan kitaran).

Langkah 4: Teruskan Sehingga Selesai

• Ulangi proses ini sehingga semua sel disambungkan, membentuk satu pokok penutupan.
• Pada akhirnya, setiap sel disambungkan dengan sel lain tanpa gelung atau bahagian yang terasing.

Oleh kerana algoritma Kruskal bergantung pada penggabungan set, ia boleh dioptimumkan dengan menggunakan algoritma Union-Find, yang menyediakan cara yang cekap untuk mengesan sel yang disambungkan semasa penjanaan labirin. Anda boleh melihat pelaksanaan PHP saya bagi algoritma Union-Find di sini: Set Disjoint (Algoritma Pencarian Kesatuan) dalam PHP