Kruskalin algoritmi sokkelogeneraattori

Kruskalin algoritmi on minimaalisen virityspuun algoritmi, jota voidaan soveltaa sokkeloiden generointiin. Se on erityisen tehokas täydellisten sokkeloiden luomiseen. Vaihtoehto Kruskalin algoritmille on Primin algoritmi, joka on myös minimaalisen virityspuun algoritmi, mutta koska ne generoivat identtisiä sokkeloita ja Kruskalin algoritmi toimii nopeammin, en ole vaivautunut toteuttamaan Primin algoritmia.

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 yhdysvaltalainen matemaatikko, tilastotieteilijä ja tietojenkäsittelytieteilijä Joseph Bernard Kruskal Jr. Hän kuvasi algoritmin ensimmäisen kerran vuonna 1956 artikkelissaan "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem".

Algoritmi on suunniteltu löytämään graafin pienimmän virittävän puun (MST) varmistaen, että kaikki solmut on yhdistetty mahdollisimman pienellä kaaren kokonaispainolla ja välttäen syklejä.

Kuinka Kruskalin algoritmi toimii sokkeloiden luomisessa

Vaihe 1: Alusta

• Käsittele jokaista sokkelon solua erillisenä joukkona (ainutlaatuisena komponenttina).
• Listaa kaikki vierekkäisten solujen väliset seinät mahdollisina reunoina.

Vaihe 2: Lajittele seinät

• Sekoita tai järjestä seinät satunnaisessa järjestyksessä. Jos toteutat sen aidolla Kruskalin algoritmilla, lajittele seinät satunnaiseen järjestykseen (koska sokkelon luominen ei vaadi painoja).

Vaihe 3: Prosessiseinät

• Toista läpi sekoittuneiden seinien.
• Jos seinän erottamat kaksi solua kuuluvat eri joukoihin (eli ne eivät ole vielä yhteydessä toisiinsa sokkelossa), poista seinä ja yhdistä joukot.
• Jos ne ovat jo samassa joukossa, jätä seinä väliin (välttääksesi syklejä).

Vaihe 4: Jatka loppuun asti

• Toista tätä prosessia, kunnes kaikki solut on yhdistetty muodostaen yhden virittävä puun.
• Lopulta jokainen solu on yhdistetty muihin ilman silmukoita tai erillisiä osia.

Koska Kruskalin algoritmi perustuu joukkojen yhdistämiseen, sitä voidaan optimoida käyttämällä Union-Find-algoritmia, joka tarjoaa tehokkaan tavan seurata yhdistettyjä soluja sokkelon luomisen aikana. Voit nähdä PHP-toteutukseni Union-Find-algoritmista täällä: Linkki

Lisälukemista

Jos pidit tästä postauksesta, saatat pitää myös näistä ehdotuksista:

• Ellerin algoritmin sokkelogeneraattori
• Rekursiivinen Backtracker Maze Generator
• Wilsonin algoritmin sokkelogeneraattori