Kruskali algoritmi labürindi generaator

Kruskali algoritm on minimaalse ulatuvusega puu algoritm, mida saab kohandada labürintide genereerimiseks. See on eriti efektiivne täiuslike labürintide loomiseks. Kruskali algoritmi alternatiiviks on Primi algoritm, mis on samuti minimaalse ulatuvusega puu algoritm, kuid kuna need genereerivad identseid labürinte ja Kruskali oma töötab kiiremini, pole ma Primi oma rakendamisega 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 Ameerika matemaatik, statistik ja arvutiteadlane Joseph Bernard Kruskal Jr. Esmakordselt kirjeldas ta algoritmi 1956. aastal oma artiklis "Graafi lühimast ulatuvast alampuust ja rändava müügimehe probleemist".

Algoritm on loodud graafi minimaalse ulatuvusega puu (MST) leidmiseks, tagades, et kõik tipud on ühendatud minimaalse võimaliku servakaaluga, vältides samal ajal tsükleid.

Kuidas Kruskali algoritm labürindi genereerimiseks töötab

1. samm: initsialiseerimine

• Käsitle iga labürindi rakku eraldi komplektina (unikaalse komponendina).
• Loetle kõik külgnevate lahtrite vahelised seinad potentsiaalsete servadena.

2. samm: sorteeri seinad

• Sega seinad või järjesta need juhuslikus järjekorras. Kui rakendad seda tõelise Kruskali algoritmina, sorteeri seinad juhuslikus järjekorras (kuna labürindi genereerimine ei vaja kaalusid).

3. samm: protsessi seinad

• Itereeri läbi segatud seinte.
• Kui seinaga eraldatud kaks lahtrit kuuluvad erinevatesse hulkadesse (st nad pole labürindis veel ühendatud), eemaldage sein ja ühendage hulgad.
• Kui need on juba samas komplektis, siis jäta sein vahele (tsüklite vältimiseks).

4. samm: Jätkake kuni lõpuni

• Korda seda protsessi, kuni kõik lahtrid on ühendatud, moodustades ühe ulatuvast puust.
• Lõpuks on iga rakk teistega ühendatud ilma silmuste või isoleeritud sektsioonideta.

Kuna Kruskali algoritm tugineb hulkude ühendamisele, saab seda optimeerida Union-Find algoritmi abil, mis pakub tõhusat viisi ühendatud lahtrite jälgimiseks labürindi genereerimise ajal. Minu Union-Find algoritmi PHP implementatsiooni näete siin: Link

Lisalugemist

Kui see postitus teile meeldis, võivad teile meeldida ka need soovitused:

• Wilsoni algoritmi labürindi generaator
• Jahti ja Tappa Labürindi Loodur
• Elleri algoritmi labürindi generaator