Kruskalov generátor bludísk algoritmov

Kruskalov algoritmus je algoritmus minimálnej kostry, ktorý je možné prispôsobiť na generovanie bludísk. Je obzvlášť účinný na vytváranie dokonalých bludísk. Alternatívou ku Kruskalovmu algoritmu je Primov algoritmus, ktorý je tiež algoritmom minimálnej kostry, ale keďže generujú identické bludiská a Kruskalov algoritmus beží rýchlejšie, neobťažoval som sa implementovať Primov algoritmus.

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 ml., americký matematik, štatistik a informatik. Prvýkrát ho opísal v roku 1956 vo svojej práci „O najkratšom rozprestierajúcom podstrome grafu a probléme obchodného cestujúceho“.

Algoritmus je navrhnutý tak, aby našiel minimálnu kostru (MST) grafu, pričom zabezpečí, že všetky vrcholy sú spojené s minimálnou možnou celkovou hmotnosťou hrán a zároveň sa vyhne cyklom.

Ako funguje Kruskalov algoritmus pre generovanie bludiska

Krok 1: Inicializácia

• Každú bunku v bludisku považujte za samostatnú množinu (jedinečný komponent).
• Vypíš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í (pretože generovanie bludiska nevyžaduje váhy).

Krok 3: Spracovanie stien

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

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

• Tento postup opakujte, kým nebudú všetky bunky prepojené a vytvoria jeden spanning tree.
• Nakoniec je každá bunka prepojená s ostatnými bez slučiek alebo izolovaných úsekov.

Keďže Kruskalov algoritmus sa spolieha na zlučovanie množín, je možné ho optimalizovať pomocou algoritmu Union-Find, ktorý poskytuje efektívny spôsob sledovania prepojených buniek počas generovania bludiska. Moju implementáciu algoritmu Union-Find v PHP si môžete pozrieť tu: Odkaz

Ďalšie čítanie

Ak sa vám tento príspevok páčil, možno sa vám budú páčiť aj tieto návrhy:

• Generátor Bludiska Lov a Zabitie
• Rastúci strom Algoritmus bludisko generátor
• Ellerov generátor bludísk algoritmov