Kruskalın Alqoritmi Maze Generatoru

Kruskalın alqoritmi labirint yaratmaq üçün uyğunlaşdırıla bilən minimum genişlənən ağac alqoritmidir. Xüsusilə mükəmməl labirintlər yaratmaq üçün təsirlidir. Kruskalın alqoritminə alternativ olaraq, eyni zamanda minimum genişlənən ağac alqoritmi olan Prim alqoritmini istifadə edə bilərsiniz, lakin onlar eyni labirintlər yaratdıqları və Kruskalın daha sürətli işlədiyi üçün Primləri tətbiq etməyə vaxt ayırmadım.

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çı, statistik və kompüter alimi Cozef Bernard Kruskal tərəfindən yaradılmışdır. O, alqoritmi ilk dəfə 1956-cı ildə "Qrafikin ən qısa uzanan alt ağacı və səyahət edən satıcı problemi haqqında" adlı məqaləsində təsvir etmişdir.

Alqoritm, dövrlərdən qaçınmaqla bütün təpələrin mümkün olan minimum ümumi kənar çəkisi ilə birləşdirildiyinə əmin olaraq, qrafikin minimum yayılma ağacını (MST) tapmaq üçün hazırlanmışdır.

Kruskalın Alqoritmi Labirint Yaradılması üçün Necə İşləyir

Addım 1: Başlanğıclaşdırın

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

Addım 2: Divarları sıralayın

• Divarları qarışdırın və ya təsadüfi şəkildə sıralayın. Əgər bunu əsl Kruskal alqoritmi kimi tətbiq edirsinizsə, divarları təsadüfi qaydada sıralayın (çünki labirint yaratmaq üçün çəkilər tələb olunmur).

Addım 3: Divarları emal edin

• Qarışdırılmış divarlar arasından keçin.
• Əgər divarla bölünmüş iki hücrə fərqli dəstlərə aiddirsə (yəni, onlar hələ labirintdə bir-birinə bağlı deyillərsə), divarı çıxarın və dəstləri birləşdirin.
• Əgər onlar artıq eyni dəstdədirlərsə, (dövrlərin qarşısını almaq üçün) divarı atlayın.

Addım 4: Tamamlanana qədər davam edin

• Bütün hüceyrələr birləşənə və tək bir ağac əmələ gələnə qədər bu prosesi təkrarlayın.
• Sonda hər bir hücrə digərlərinə ilgəklər və ya təcrid olunmuş hissələr olmadan bağlanır.

Kruskalın alqoritmi birləşmə dəstlərinə əsaslandığı üçün, labirint generasiyası zamanı bağlı hücrələri izləmək üçün səmərəli bir yol təqdim edən Union-Find alqoritmindən istifadə etməklə optimallaşdırıla bilər. Union-Find alqoritminin PHP tətbiqini burada görə bilərsiniz: Link

Əlavə Oxu

Bu yazı xoşunuza gəldisə, bu təklifləri də bəyənə bilərsiniz:

• Artan Ağac Alqoritmi Maze Generatoru
• Ellerin Alqoritmi Maze Generatoru
• Uilsonun Alqoritmi Maze Generatoru