Kruskali algoritmi labürindi generaator
Avaldatud: 16. veebruar 2025, kell 17:57:26 UTC
Labürindigeneraator, mis kasutab Kruskali algoritmi täiusliku labürindi loomiseks. See algoritm kipub looma keskmise pikkusega koridoride ja paljude ummikteedega labürinte, aga ka üsna sirget lahendust.Kruskal's Algorithm Maze Generator
Kruskali algoritm on minimaalse ulatusega puu algoritm, mida saab labürindi genereerimiseks kohandada. See on eriti tõhus täiuslike labürindi loomiseks. Alternatiiviks Kruskali algoritmile on Primi algoritm, mis on ka minimaalselt ulatuva puu algoritm, aga kuna need genereerivad identseid labürinte ja Kruskal jookseb kiiremini, pole ma Primi oma juurutamisega vaeva näinud.
Täiuslik labürint on labürint, kus on täpselt üks tee labürindi mis tahes punktist mis tahes teise punkti. See tähendab, et te ei saa sattuda ringiratastesse, kuid sageli satute ummikteedesse, mis sunnib teid ümber pöörama ja tagasi minema.
Siin genereeritud labürindi kaardid sisaldavad vaikimisi versiooni ilma algus- ja lõpp-punktideta, nii et saate need ise otsustada: labürindi mis tahes punktist mis tahes teise punkti on olemas lahendus. Kui soovite inspiratsiooni, saate lubada soovitatud algus- ja lõpupositsiooni - ja isegi näha lahendust nende kahe vahel.
Kruskali algoritmi kohta
Kruskali algoritmi lõi Joseph Bernard Kruskal, Jr., Ameerika matemaatik, statistik ja arvutiteadlane. Algoritmi kirjeldas ta esmakordselt 1956. aastal oma artiklis "Graafi lühimast alampuust ja reisiva müügimehe probleemist".
Algoritm on loodud graafiku minimaalse ulatusepuu (MST) leidmiseks, tagades, et kõik tipud on ühendatud minimaalse võimaliku serva kogukaaluga, vältides tsükleid.
Kuidas Kruskali algoritm labürindi genereerimise jaoks töötab
1. samm: lähtestamine
- Käsitlege labürindi iga rakku eraldi komplektina (unikaalne komponent).
- Loetlege kõik seinad külgnevate lahtrite vahel potentsiaalsete servadena.
2. samm: sorteerige seinad
- Seinad segatakse või tellitakse juhuslikult. Kui rakendate seda tõelise Kruskali algoritmina, sortige seinad juhuslikus järjekorras (kuna labürindi genereerimine ei nõua kaalusid).
3. samm: seinte töötlemine
- Korda läbi segatud seinte.
- Kui kaks seinaga jagatud lahtrit kuuluvad erinevatesse komplektidesse (st nad ei ole veel labürindis ühendatud), eemaldage sein ja ühendage komplektid.
- Kui need on juba samas komplektis, jätke sein vahele (tsüklite vältimiseks).
4. samm: jätkake kuni lõpetamiseni
- Korrake seda protsessi, kuni kõik lahtrid on ühendatud, moodustades ühtse ulatuva puu.
- Lõpuks ühendatakse iga rakk teistega ilma silmuste või eraldatud sektsioonideta.
Kuna Kruskali algoritm tugineb komplektide ühendamisele, saab seda optimeerida Union-Find algoritmi abil, mis annab tõhusa viisi ühendatud rakkude jälgimiseks labürindi genereerimise ajal. Näete minu Union-Find algoritmi rakendamist PHP-s siin: Disjoint Set (Union-Find Algorithm) PHP-s