Uilsonun Alqoritmi Maze Generatoru

Uilsonun alqoritmi , mazut yaradılışı üçün vahid spanning ağaclarını meydana gətirən bir loop-erased təsadüfi gəzinti metodudur. Bu o deməkdir ki, verilmiş ölçüdə olan bütün mümkün mazutların eyni dərəcədə əmələ gəlmə ehtimalı var və bu da onu tərəfsiz mazut nəsil texnikası edir. Wilson alqoritmini Aldous-Broder alqoritminin təkmilləşdirilmiş versiyası hesab etmək olar, belə ki, o, eyni xarakterli mazutlar yaradır, lakin çox daha sürətli çalışır. Ona görə də mən burada Aldous-Broder alqoritmini həyata keçirməkdən bezməmişə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.

Uilsonun alqoritmi haqqında

Uilsonun ilgək silinmiş təsadüfi divardan istifadə edərək birtipli spanning ağaclarının əmələ gətirməsi alqoritmi David Brüs Uilson tərəfindən yaradılmışdır.

Uilson bu alqoritmi 1996-cı ildə ehtimal nəzəriyyəsində təsadüfi spanning ağaclarını və Markov zəncirlərini araşdırarkən təqdim etmişdir. Onun işi ilk növbədə riyaziyyat və statistik fizikada olsa da, o vaxtdan alqoritm mükəmməl vahid mazutlar istehsal etmək qabiliyyətinə görə mazut nəsli üçün geniş şəkildə qəbul edilmişdir.

Uilsonun alqoritmi Maze nəsli üçün necə işləyir?

Uilsonun alqoritmi təsadüfi gəzintilərdən istifadə edərək gözəgörunməz hüceyrələrdən yolları iterativ şəkildə oyaraq son mazutun heç bir döngə olmadan tam şəkildə qoşulmasını təmin edir.

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

• Divarlarla dolu şəbəkə ilə başlayın.
• Bütün mümkün keçid hüceyrələrinin siyahısını müəyyən edin.

2-ci addım: Təsadüfi Başlanğıc Hüceyrəsi Seçin

• Hər hansı təsadüfi hüceyrəni seçin və ziyarət edildiyi kimi işarə edin. Bu, nəsil dövründə mazutun başlanğıc nöqtəsinə xidmət edir.

Addım 3: Loop-Erasing ilə Random Walk

• Gözəgörunməz hüceyrəni seçin və təsadüfi gəzintiyə başlayın (təsadüfi istiqamətlərdə hərəkət edin).
• Əgər gəzinti artıq ziyarət edilən hüceyrəyə çatırsa, cığırdakı döngələri silin.
• Gəzinti baş çəkdiyin əraziyə bağlandıqdan sonra, baş çəkdiyin kimi, yoldakı bütün hüceyrələri işarələ.

Addım 4: Bütün Hüceyrələr ziyarət edilənə qədər təkrar edin:

• Hər hüceyrə labüdə daxil olana qədər gözəgörunməz hüceyrələri seçməyə və təsadüfi gəzintilər etməyə davam edin.