Kruskalov generátor bludísk algoritmov

Kruskalov algoritmus je algoritmus s minimálnym spanning tree, ktorý je možné prispôsobiť na generovanie bludiska. Je obzvlášť účinný pri vytváraní dokonalých bludísk. Alternatívou ku Kruskalovmu algoritmu je Primov algoritmus, ktorý je tiež minimálnym algoritmom spanning tree, ale keďže generuje identické bludiská a Kruskalove bežia rýchlejšie, neobťažoval som sa implementáciou Primovho algoritmu.

Dokonalé bludisko je bludisko, v ktorom existuje presne jedna cesta z ktoréhokoľvek bodu bludiska do ktoréhokoľvek iného bodu. To znamená, že nemôžete skončiť v kruhu, ale často narazíte na slepé uličky, ktoré vás prinútia otočiť sa a vrátiť sa späť.

Tu vygenerované mapy bludiska obsahujú predvolenú verziu bez počiatočnej a cieľovej pozície, takže si ich môžete určiť sami: z ľubovoľného bodu bludiska do ľubovoľného iného bodu bude existovať riešenie. Ak sa chcete inšpirovať, môžete zapnúť navrhovanú počiatočnú a cieľovú pozíciu - a dokonca si pozrieť riešenie medzi nimi.

O Kruskalovom algoritme

Kruskalov algoritmus vytvoril Joseph Bernard Kruskal, Jr., americký matematik, štatistik a počítačový vedec. Algoritmus prvýkrát opísal v roku 1956 vo svojom článku „On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem“.

Algoritmus je navrhnutý tak, aby našiel minimálnu kostru (MST) grafu, pričom zaisťuje, že všetky vrcholy sú spojené s minimálnou možnou celkovou hmotnosťou hrany, pričom sa vyhýbajú cyklom.

Ako Kruskalov algoritmus funguje pri vytváraní bludiska

Krok 1: Inicializujte

• S každou bunkou v bludisku zaobchádzajte ako so samostatnou súpravou (jedinečný komponent).
• Uveďte všetky steny medzi susednými bunkami ako potenciálne hrany.

Krok 2: Zoraďte steny

• Zamiešajte alebo náhodne usporiadajte steny. Ak to implementujete ako skutočný Kruskalov algoritmus, zoraďte steny v náhodnom poradí (keďže generovanie bludiska nevyžaduje váhy).

Krok 3: Spracujte steny

• Iterujte cez zamiešané steny.
• Ak dve bunky rozdelené stenou patria do rôznych skupín (tj ešte nie sú spojené v bludisku), odstráňte stenu a zlúčte skupiny.
• Ak sú už v rovnakej súprave, preskočte stenu (aby ste sa vyhli cyklom).

Krok 4: Pokračujte až do dokončenia

• Tento postup opakujte, kým nie sú všetky bunky spojené, čím sa vytvorí jeden kostra.
• Na konci je každá bunka spojená s ostatnými bez slučiek alebo izolovaných sekcií.

Keďže Kruskalov algoritmus sa spolieha na zlučovanie množín, možno ho optimalizovať pomocou algoritmu Union-Find, ktorý poskytuje efektívny spôsob sledovania spojených buniek počas vytvárania bludiska. Moju implementáciu algoritmu Union-Find v PHP si môžete pozrieť tu: Disjoint Set (Union-Find Algorithm) v PHP