Kruskal's algoritme-doolhofgenerator

Het algoritme van Kruskal is een algoritme voor het vinden van een minimale opspannende boom dat kan worden aangepast voor het genereren van doolhoven. Het is bijzonder effectief voor het creëren van perfecte doolhoven. Een alternatief voor het algoritme van Kruskal is het algoritme van Prim, dat ook een algoritme voor het vinden van een minimale opspannende boom is, maar aangezien ze identieke doolhoven genereren en het algoritme van Kruskal sneller is, heb ik Prim's algoritme niet geïmplementeerd.

Een perfect doolhof is een doolhof waarin er precies één pad is van elk punt in het doolhof naar elk ander punt. Dat betekent dat je geen rondjes kunt lopen, maar dat je vaak op doodlopende paden stuit, waardoor je gedwongen wordt om te keren en terug te gaan.

De doolhofkaarten die hier worden gegenereerd bevatten een standaardversie zonder start- en eindposities, zodat je die zelf kunt bepalen: er is een oplossing van elk punt in het doolhof naar elk ander punt. Als je inspiratie wilt, kun je een voorgestelde start- en eindpositie inschakelen - en zelfs de oplossing tussen die twee bekijken.

Over het algoritme van Kruskal

Het algoritme van Kruskal werd ontwikkeld door Joseph Bernard Kruskal jr., een Amerikaanse wiskundige, statisticus en computerwetenschapper. Hij beschreef het algoritme voor het eerst in 1956 in zijn artikel "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem".

Het algoritme is ontworpen om de minimaal opspannende boom (MST) van een graaf te vinden, waarbij ervoor wordt gezorgd dat alle knooppunten met elkaar verbonden zijn met het minimaal mogelijke totale randgewicht, terwijl cycli worden vermeden.

Hoe het algoritme van Kruskal werkt voor het genereren van doolhoven.

Stap 1: Initialiseren

• Beschouw elke cel in het doolhof als een aparte set (een uniek onderdeel).
• Geef alle wanden tussen aangrenzende cellen weer als mogelijke randen.

Stap 2: Muren sorteren

• Schud de muren door elkaar of rangschik ze willekeurig. Als je het implementeert als een echt Kruskal-algoritme, sorteer de muren dan in een willekeurige volgorde (aangezien het genereren van een doolhof geen gewichten vereist).

Stap 3: Proceswanden

• Doorloop de herschikte muren.
• Als de twee cellen die door de muur gescheiden zijn tot verschillende verzamelingen behoren (d.w.z. ze zijn nog niet met elkaar verbonden in het doolhof), verwijder dan de muur en voeg de verzamelingen samen.
• Als ze al in dezelfde set zitten, sla dan de muur over (om herhalingen te voorkomen).

Stap 4: Ga door tot het voltooid is.

• Herhaal dit proces totdat alle cellen met elkaar verbonden zijn en een enkele opspannende boom vormen.
• Uiteindelijk is elke cel met de andere verbonden zonder lussen of geïsoleerde gedeelten.

Omdat het algoritme van Kruskal gebaseerd is op het samenvoegen van verzamelingen, kan het worden geoptimaliseerd met behulp van het Union-Find-algoritme. Dit algoritme biedt een efficiënte manier om verbonden cellen te volgen tijdens het genereren van een doolhof. Mijn PHP-implementatie van het Union-Find-algoritme is hier te vinden: Link

Verder lezen

Als je dit bericht leuk vond, vind je deze suggesties misschien ook interessant:

• Generator voor jacht- en doodsdoolhoven
• Wilson's algoritme doolhofgenerator
• Recursieve Backtracker Doolhof Generator