Gjeneratori i Mazes së Algoritmit të Kruskalit

Algoritmi i Kruskal është një algoritëm minimal pemësh që mund të përshtatet për gjenerimin e labirinteve. Është veçanërisht i efektshëm për krijimin e labirinteve të përsosura. Një alternativë ndaj algoritmit të Kruskal është algoritmi i Prim, i cili është gjithashtu një algoritëm minimal që shtrihet në pemë, por meqë ato gjenerojnë labirinte identike dhe vrapimet e Kruskal më shpejt, unë nuk e kam shqetësuar zbatimin e Prim.

Një labirint i përsosur është një labirint në të cilin ka saktësisht një rrugë nga çdo pikë në labirint në çdo pikë tjetër. Kjo do të thotë që nuk mund të përfundoni duke ecur në rreth, por shpesh do të hasni në rrugë pa krye, duke ju detyruar të ktheheni dhe të ktheheni.

Hartat e labirintit të krijuara këtu përfshijnë një version të paracaktuar pa asnjë pozicion fillimi dhe mbarimi, kështu që ju mund t'i vendosni ato vetë: do të ketë një zgjidhje nga çdo pikë në labirint në çdo pikë tjetër. Nëse dëshironi frymëzim, mund të aktivizoni një pozicion të sugjeruar fillimi dhe përfundimi - dhe madje të shihni zgjidhjen midis të dyjave.

Rreth algoritmit të Kruskalit

Algoritmi i Kruskal u krijua nga Joseph Bernard Kruskal, Jr., matematikan, statisticien dhe informaticien amerikan. Ai e përshkroi për herë të parë algoritmin në vitin 1956 në gazetën e tij "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem."

Algoritmi është projektuar për të gjetur pemën minimale të shtrirë (MST) të një grafiku, duke siguruar që të gjitha marramendjet të jenë të lidhura me peshën minimale të mundshme totale të skajit, duke shmangur ciklet.

Si funksionon algoritmi i Kruskalit për brezin Maze

Hapi 1: Initialize

• Trajtojeni çdo qelizë në labirint si një set të veçantë (një përbërës unik).
• Renditni të gjitha muret midis qelizave ngjitur si skaje potenciale.

Hapi 2: Zgjidh muret

• Shuffle ose rastësisht urdhërojnë muret. Nëse e zbatoni atë si një algoritëm të vërtetë Kruskal, trioni muret në një rend të rastësishëm (meqë brezi i labirinteve nuk kërkon pesha).

Hapi 3: Muret e procesit

• Iterate nëpër muret e hutuara.
• Nëse dy qelizat e ndara nga muri i përkasin seteve të ndryshme (pra, ato nuk janë ende të lidhura në labirint), hiqni murin dhe shkrini setet.
• Nëse janë tashmë në të njëjtin set, anashkaloni murin (për të shmangur ciklet).

Hapi 4: Vazhdoni deri në përfundim

• Përsëriteni këtë proces derisa të gjitha qelizat të lidhen, duke formuar një pemë të vetme që shtrihet.
• Në fund, çdo qelizë është e lidhur me të tjerat pa loops ose seksione të izoluara.

Meqë algoritmi i Kruskal mbështetet në setet e shkrirjes, ai mund të optimizohet duke përdorur algoritmin Union-Find, i cili ofron një mënyrë efikase për të ndjekur qelizat e lidhura gjatë gjenerimit të labirintit. Ju mund të shihni zbatimin tim PHP të algoritmit Union-Find këtu: Disjoint Set (Union-Find Algorithm) në PHP