Rekursiv Backtracker labirent generatoru

Recursive backtracker alqoritmi həqiqətən ümumi məqsədli dərinlik-ilk axtarışdır. Mazut nəsli üçün istifadə edildikdə, o, yolu təsadüfi seçmək üçün bir az dəyişdirilmişdi, halbuki əgər faktiki axtarış məqsədləri üçün istifadə edilsəydi, adətən hər səviyyəni sadəcə sətirli qaydada axtarmaq olardı. O, uzun, küləkli koridorlarla və çox uzun, burulmuş həll olan mazutlar əmələ gətirir.

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.

Recursive backtracker alqoritmi mükəmməl mazutların (heç bir döngəsi olmayan mazutlar və hər hansı iki nöqtə arasında vahid yol olan mazes) əmələ gətirməsi üçün dərinlik-ilk axtarış metodudur. O, sadə, keyfiyyətlidir və uzun və küləkli koridorlarla vizual cəhətdən cəlbedici mazutlar əmələ gətirir.

Adına baxmayaraq, rekursion istifadə edərək mütləq həyata keçirmək lazım deyil. Tez-tez LİVO növbəsi (yəni bir yığın) istifadə edərək iterativ yanaşmada həyata keçirilir. Çox böyük mazutlar üçün rekursion istifadə proqramlaşdırma dilindən və mövcud yaddaşdan asılı olaraq zəng yığını aşma ehtimalı daha çoxdur. LifO sırası böyük miqdarda verilənlərin işlənməsinə daha asan uyğunlaşa bilər, hətta mövcud yaddaş kifayət deyilsə, növbəni diskdə və ya verilənlər bazasında saxlaya bilər.

Necə işləyir?

Alqoritm yığına əsaslanan dərinlik-birinci axtarış üsulu ilə fəaliyyət göstərir. Addım-addım qırılma:

1. Başlanğıc hüceyrə seçin və ziyarət edildiyi kimi işarə edin.
2. Görünməz hüceyrələr olduğu halda:
   • Hələ ziyarətə çıxmayan qonşu hüceyrələrə baxın.
   • Əgər ən azı bir qeyri-üzvi qonşu mövcuddursa:
     • Təsadüfi olaraq görünməyən qonşulardan birini seçin.
     • Cari hüceyrə ilə seçilmiş qonşu arasındakı divarı silin.
     • Seçdiyin qonşunun yanına köç və onu ziyarət etdiyin kimi işarələ.
     • Hazırkı hüceyrəni yığının üzərinə itələyin.
   • Əgər heç bir qeyb qonşu mövcud deyilsə:
     • Sonuncu hüceyrəni yığından popülasiya edərək arxaya doğru.
3. Yığın boş olana qədər bu prosesi davam etdir.

Bu alqoritmlə bağlı maraqlı fakt ondan ibarətdir ki, o həm mazut generatoru, həm də mazut həll edən kimi işləyir. Əgər siz onu artıq yaranmış mazut üzərində işə salsanız və sadəcə qərara alınmış son nöqtəyə vurduqda dayandırsanız, yığında mazutun həlli olacaq.

Əslində bu alqoritmin iki versiyası bu saytda oynanmaqdadır: bu səhifədə mazutların generasiyası üçün bir Lİ LIFO sırası və bir rekursiya əsasında mazutlar, həmçinin digər alqoritmlər tərəfindən əmələ gələn mazutlar (bu yolla həll olan xəritələr hazırlanır). İki fərqli versiyaya sahib olmaq sadəcə idman üçündür, çünki mən bunu maraqlı hesab edən bir nerdəm, ya hər ikisi üçün işləyə bilərdi ;-)