Kruskalin algoritmi sokkelogeneraattori
Julkaistu: 16. helmikuuta 2025 klo 17.57.28 UTC
Labyrinttigeneraattori, joka käyttää Kruskalin algoritmia täydellisen sokkelon luomiseen. Tällä algoritmilla on taipumus luoda sokkeloita, joissa on keskipitkät käytävät ja monet umpikujat, sekä melko suora ratkaisu.Kruskal's Algorithm Maze Generator
Kruskalin algoritmi on minimivirittävän puun algoritmi, joka voidaan mukauttaa sokkeloiden luomiseen. Se on erityisen tehokas luomaan täydellisiä sokkeloita. Vaihtoehtona Kruskalin algoritmille on Primin algoritmi, joka on myös minimivirittävän puualgoritmi, mutta koska ne luovat identtisiä sokkeloita ja Kruskalin algoritmit juoksevat nopeammin, en ole vaivautunut toteuttamaan Primin.
Täydellinen sokkelo on sokkelo, jossa on täsmälleen yksi reitti mistä tahansa sokkelon pisteestä mihin tahansa toiseen pisteeseen. Tämä tarkoittaa, että et voi päätyä kiertämään ympyrää, mutta joudut usein umpikujaan, jolloin sinun on pakko kääntyä ympäri ja palata takaisin.
Tässä luotuihin sokkelokarttoihin sisältyy oletusversio, jossa ei ole alku- ja loppupisteitä, joten voit päättää ne itse: mistä tahansa sokkelon pisteestä mihin tahansa muuhun pisteeseen on olemassa ratkaisu. Jos haluat inspiraatiota, voit ottaa käyttöön ehdotetun alku- ja maalipaikan - ja jopa nähdä ratkaisun näiden kahden välissä.
Tietoja Kruskalin algoritmista
Kruskalin algoritmin loi Joseph Bernard Kruskal, Jr., amerikkalainen matemaatikko, tilastotieteilijä ja tietojenkäsittelytieteilijä. Hän kuvaili algoritmia ensimmäisen kerran vuonna 1956 artikkelissaan "Kävijän lyhyimmästä osapuusta ja matkustavan myyjän ongelmasta".
Algoritmi on suunniteltu etsimään graafin pienin virittävä puu (MST) varmistaen, että kaikki kärjet ovat yhteydessä mahdollisimman pienellä kokonaisreunapainolla välttäen jaksoja.
Kuinka Kruskalin algoritmi toimii sokkelosukupolvessa
Vaihe 1: Alusta
- Käsittele jokaista sokkelon solua erillisenä sarjana (ainutlaatuinen komponentti).
- Luettele kaikki vierekkäisten solujen väliset seinät mahdollisiksi reunuksiksi.
Vaihe 2: Lajittele seinät
- Sekoita tai tilaa seinät satunnaisesti. Jos toteutat sen todellisena Kruskal-algoritmina, lajittele seinät satunnaisessa järjestyksessä (koska sokkelon luominen ei vaadi painoja).
Vaihe 3: Käsittele seinät
- Iteroi sekoitettujen seinien läpi.
- Jos seinällä jaetut kaksi solua kuuluvat eri ryhmiin (eli ne eivät ole vielä yhteydessä toisiinsa), poista seinä ja yhdistä joukot.
- Jos ne ovat jo samassa sarjassa, ohita seinä (kiertojen välttämiseksi).
Vaihe 4: Jatka loppuun asti
- Toista tämä prosessi, kunnes kaikki solut ovat yhteydessä toisiinsa muodostaen yhden virittävän puun.
- Lopussa jokainen solu on yhdistetty muihin ilman silmukoita tai eristettyjä osia.
Koska Kruskalin algoritmi perustuu joukkojen yhdistämiseen, se voidaan optimoida käyttämällä Union-Find-algoritmia, joka tarjoaa tehokkaan tavan seurata yhdistettyjä soluja sokkelogeneroinnin aikana. Voit nähdä Union-Find-algoritmin PHP-toteutuksen täällä: Disjoint Set (Union-Find Algorithm) PHP:ssä