Kruskal's Algoritma Maze Generator

Reiknirit Kruskal er lágmarksspennandi tré reiknirit sem hægt er að aðlaga fyrir völundarhúsmyndun. Það er sérstaklega áhrifaríkt til að búa til fullkomið völundarhús. Annar valkostur við reiknirit Kruskal er reiknirit Prim, sem er líka lágmarks span tré reiknirit, en þar sem þeir búa til eins völundarhús og Kruskal keyrir hraðar, hef ég ekki nennt að innleiða Prim.

Fullkomið völundarhús er völundarhús þar sem það er nákvæmlega ein leið frá hvaða stað sem er í völundarhúsinu til annars staðar. Það þýðir að þú getur ekki endað á því að fara í hringi, en þú munt oft lenda í blindgötum, sem neyðir þig til að snúa við og fara til baka.

Völundarkortin sem mynduð eru hér innihalda sjálfgefna útgáfu án upphafs- og lokastaða, svo þú getur ákveðið þær sjálfur: það verður lausn frá hvaða stað sem er í völundarhúsinu til hvers annars. Ef þú vilt innblástur geturðu virkjað tillögu um upphafs- og lokastöðu - og jafnvel séð lausnina á milli þeirra tveggja.

Um Kruskal's reiknirit

Kruskal's reiknirit var búið til af Joseph Bernard Kruskal, Jr., bandarískum stærðfræðingi, tölfræði- og tölvunarfræðingi. Hann lýsti reikniritinu fyrst árið 1956 í grein sinni "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem."

Reikniritinu er ætlað að finna lágmarks spennutré (MST) grafs, og tryggja að öll horn séu tengd með lágmarks mögulegu heildarbrúnarþyngd, án þess að myndast hringir.

Hvernig Kruskal’s reiknirit virkar fyrir völundarhúsagerð

Skref 1: Upphaf

• Beita hverri frumu í völundarhúsinu sem sérstökum mengi (einstökum hluta).
• Listi öll veggi milli aðliggjandi frumna sem mögulega brúnir.

Skref 2: Flokka veggi

• Rugla eða raða veggjunum í handahófsröð. Ef það er útfært sem raunverulegt Kruskal’s reiknirit, raða veggjum í handahófsröð (þar sem völundarhúsagerð krefst ekki þyngda).

Skref 3: Vinna úr veggjum

• Ferðast í gegnum ruglaða veggina.
• Ef tvær frumur sem veggurinn skiptir tilheyra mismunandi mengjum (þ.e.a.s. þær eru ekki enn tengdar í völundarhúsinu), fjarlægðu vegginn og sameina mengin.
• Ef þær eru þegar í sama mengi, sleppa veggnum (til að forðast hringi).

Skref 4: Halda áfram þar til lokið

• Endurtaktu þennan feril þar til allar frumur eru tengdar, sem myndar eitt spennitré.
• Í lokin er hver fruma tengd við aðrar án lykkja eða einangraðra svæða.

Þar sem Kruskal’s reiknirit byggir á sameiningu mengja, er hægt að hámarka það með því að nota Union-Find reiknirit, sem veitir skilvirkan hátt til að rekja tengdar frumur við völundarhúsagerð. Þú getur séð PHP útfærslu mína á Union-Find reikniritinu hér: Disjoint Set (Union-Find Algorithm) í PHP