Kruskal se algoritme doolhof kragopwekker

Kruskal se algoritme is 'n minimum omvattende boomalgoritme wat aangepas kan word vir doolhofgenerering. Dit is veral effektief om perfekte doolhowe te skep. 'n Alternatief vir Kruskal se algoritme is Prim se algoritme, wat ook 'n minimum omvattende boomalgoritme is, maar aangesien hulle identiese doolhowe genereer en Kruskal vinniger loop, het ek nie die moeite gedoen om Prim's 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 referaat "On the Shortest Spanning Subtree of a Graph and the Travelling Salesman Problem."

Die algoritme is ontwerp om die minimum spanningsboom (MST) van 'n grafiek te vind, om te verseker dat alle hoekpunte met die minimale moontlike totale randgewig verbind word, 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

• Skuifel of bestel die mure lukraak. As jy dit as 'n ware Kruskal se algoritme implementeer, sorteer mure in 'n ewekansige volgorde (aangesien doolhofgenerering nie gewigte benodig nie).

Stap 3: Verwerk mure

• Herhaal deur die geskommelde mure.
• As die twee selle wat deur die muur gedeel word, aan verskillende stelle behoort (dit wil 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 alle selle verbind is en 'n enkele span boom vorm.
• Aan die einde is elke sel aan die ander gekoppel sonder lusse of geïsoleerde afdelings.

Aangesien Kruskal se algoritme staatmaak op samesmeltingsstelle, kan dit geoptimaliseer word deur die Union-Find-algoritme te gebruik, wat 'n doeltreffende manier bied om gekoppelde selle tydens doolhofgenerering op te spoor. U kan my PHP-implementering van die Union-Find-algoritme hier sien: Onsamehangende stel (Unie-Vind-algoritme) in PHP