Kruskalın Alqoritmi Maze Generatoru

Kruskalın alqoritmi mazut nəsli üçün uyğunlaşa bilən minimal spanning ağac alqoritmidir. Xüsusilə mükəmməl mazutların yaradılması üçün təsirlidir. Kruskalın alqoritminin alternativi Primin alqoritmidir. Bu alqoritm də minimal spanning ağac alqoritmidir. Lakin onlar eyni mazutlar və Kruskalın qaçışlarını daha sürətli yaratdığı üçün primin həyata keçirilməsi məni narahat etməyib.

Mükəmməl bir labirint, labirintdəki hər hansı bir nöqtədən hər hansı digər nöqtəyə tam olaraq bir yolun olduğu labirintdir. Bu o deməkdir ki, siz dövrələrə girə bilməyəcəksiniz, ancaq tez-tez çıxılmaz nöqtələrlə qarşılaşacaqsınız, sizi dönüb geri qayıtmağa məcbur edəcəksiniz.

Burada yaradılan labirint xəritələri heç bir başlanğıc və bitmə mövqeləri olmayan defolt versiyanı ehtiva edir, buna görə də özünüz üçün bunlara qərar verə bilərsiniz: labirintdə istənilən nöqtədən istənilən digər nöqtəyə həll yolu olacaq. Əgər ilham almaq istəyirsinizsə, təklif olunan başlanğıc və bitiş mövqeyini aktivləşdirə və hətta ikisi arasında həll yolu görə bilərsiniz.

Kruskalın alqoritmi haqqında

Kruskalın alqoritmi amerikalı riyaziyyatçı, statistikaçı və kompüter elmləri namizədi Cozef Bernard Kruskal tərəfindən yaradılmışdır. O, alqoritmi ilk dəfə 1956-cı ildə "On the Shortst Spanning Subtree of a Graph and the Traveling Salesman Problem" adlı yazısında təsvir etmişdir.

Alqoritm qrafikin minimal spanning ağacını (MST) tapmaq üçün nəzərdə tutulmuşdur, bütün vertikaların dövrələrdən qaçınmaqla yanaşı, mümkün olan minimal ümumi kənar çəkisi ilə bağlı olmasını təmin edir.

Kruskalın Alqoritmi Maze nəsli üçün necə işləyir?

1-ci addım: Başlanğıc

• Labirintdəki hər hüceyrəni ayrı bir dəstə (unikal komponent) kimi qəbul edin.
• Bitişik hüceyrələr arasındakı bütün divarları potensial kənarlar kimi sadalayın.

2-ci addım: Divarları sırala

• Divarları shuffle və ya təsadüfi sifariş. Əgər onu həqiqi Kruskalın alqoritmi kimi həyata keçirirsə, divarları təsadüfi ardıcıllıqla sıralayın (mazut nəsil ağırlıq tələb etmədiyindən).

3-cü addım: Proses divarları

• Burğalar vasitəsilə hərəkət edir.
• Divara bölünən iki hüceyrə müxtəlif setlərə aiddirsə (yəni onlar hələ mazutda bağlı deyillər), divarı çıxarın və setləri birləşdirsinlər.
• Əgər onlar (dünyada) eyni bir yerdə olsaydılar, divardan kənara çəkilərlər) ki,

4-cü addım: Başa çatana qədər davam edin

• Bütün hüceyrələr bir-biri ilə əlaqəli olana qədər bu prosesi təkrarlayın, bir spanning ağacı əmələ gətirir.
• Sonda hər bir hüceyrə digərləri ilə ilgəksiz və ya təcrid olunmuş hissələrlə birləşir.

Kruskalın alqoritmi birləşmə setlərinə arxalandığı üçün, o, "Union-Find" alqoritmindən istifadə etməklə optimallaşdırıla bilər. Bu alqoritm labirint nəsli zamanı bağlı hüceyrələri izləmək üçün effektiv üsul təqdim edir. Union-Find alqoritminin PHP tətbiqini burada görə bilərsiniz: PHP-də Disjoint Set (Union-Find Alqoritmi).