Kruskal se algoritme doolhof kragopwekker

Kruskal se algoritme is 'n minimum-omspannende boom-algoritme wat aangepas kan word vir doolhofgenerering. Dit is veral effektief vir die skep van perfekte doolhowe. 'n Alternatief vir Kruskal se algoritme is Prim se algoritme, wat ook 'n minimum-omspannende boom-algoritme is, maar aangesien hulle identiese doolhowe genereer en Kruskal s'n vinniger loop, het ek nie die moeite gedoen om Prim s'n te implementeer nie.

'n Volmaakte doolhof is 'n doolhof waarin daar presies een pad van enige punt in die doolhof na enige ander punt is. Dit beteken dat jy nie uiteindelik in sirkels kan rondloop nie, maar jy sal dikwels doodloopstrate teëkom, wat jou dwing om om te draai en terug te gaan.

Die doolhofkaarte wat hier gegenereer word, bevat 'n verstekweergawe sonder enige begin- en eindposisies, so jy kan dit self besluit: daar sal 'n oplossing wees van enige punt in die doolhof na enige ander punt. As jy inspirasie wil hê, kan jy 'n voorgestelde begin- en eindposisie aktiveer - en selfs die oplossing tussen die twee sien.

Oor Kruskal se Algoritme

Kruskal se algoritme is geskep deur Joseph Bernard Kruskal, Jr., 'n Amerikaanse wiskundige, statistikus en rekenaarwetenskaplike. Hy het die algoritme die eerste keer in 1956 beskryf in sy artikel "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem".

Die algoritme is ontwerp om die minimum spanningsboom (MST) van 'n grafiek te vind, wat verseker dat alle hoekpunte met die minimaal moontlike totale randgewig verbind is terwyl siklusse vermy word.

Hoe Kruskal se Algoritme Werk vir Doolhofgenerering

Stap 1: Inisialiseer

• Behandel elke sel in die doolhof as 'n aparte stel (’n unieke komponent).
• Lys al die mure tussen aangrensende selle as potensiële rande.

Stap 2: Sorteer Mure

• Skommel of rangskik die mure willekeurig. Indien dit as 'n ware Kruskal-algoritme geïmplementeer word, sorteer mure in 'n ewekansige volgorde (aangesien doolhofgenerering nie gewigte benodig nie).

Stap 3: Verwerk Mure

• Itereer deur die geskuifde mure.
• As die twee selle wat deur die muur verdeel word, aan verskillende stelle behoort (d.w.s. hulle is nog nie in die doolhof verbind nie), verwyder die muur en voeg die stelle saam.
• As hulle reeds in dieselfde stel is, slaan die muur oor (om siklusse te vermy).

Stap 4: Gaan voort tot voltooiing

• Herhaal hierdie proses totdat al die selle verbind is en 'n enkele omspannende boom vorm.
• Aan die einde is elke sel aan die ander gekoppel sonder lusse of geïsoleerde afdelings.

Aangesien Kruskal se algoritme staatmaak op die samesmelting van stelle, kan dit geoptimaliseer word deur die Union-Find-algoritme te gebruik, wat 'n doeltreffende manier bied om gekoppelde selle tydens doolhofgenerering op te spoor. Jy kan my PHP-implementering van die Union-Find-algoritme hier sien: Skakel

Verdere Leeswerk

As jy hierdie plasing geniet het, sal jy dalk ook van hierdie voorstelle hou:

• Wilson se algoritme doolhof kragopwekker
• Groeiende boom algoritme doolhof kragopwekker
• Rekursiewe Backtracker Maze Generator