Qədim dövrlərdən bəri labirintlər sirr və sirr hissi keçirirdi. Bəşəriyyətə məlum olan ilk labirintlərdən biri Herodotu təsvir edir - 5000 otağı olan Misir Labirinti. Zaman keçdikcə labirintlər dini və mistik əhəmiyyətini itirdilər və mürəkkəb konfiqurasiyanın yaşıl hedcinq şəklində bağlara və parklara çevrilərək əyləncə obyektlərinə çevrildilər. Labirentlərin həlli həmişə maraqlı bir fəaliyyət olmuşdur, lakin daha da maraqlısı Labirintdən keçə biləcək maşınların yaradılmasıdır. Bir labirentə keçməyin ən sadə qaydalarından biri "bir əlli" qaydadır: bir labirentlə hərəkət edərək həmişə sağ və ya sol əlinizlə divara toxunmalısınız. Bu alqoritmi yəqin ki, qədim yunanlar tanıyırdılar. Bütün ölü nöqtələrə gedərək uzun bir yol qət etməlisiniz, amma sonunda məqsədə çatacaqsınız. Bu qaydanın bir çatışmazlığı olsa da, bu barədə daha sonra danışacağıq. "Sağ əl" qaydasına uyğun hərəkət edən bir robotu təsvir etməyə çalışaq. İşinin əvvəlində robot təqib edəcəyi divarı tapmalıdır. Bunu etmək üçün, bir maneəyə keçməyincə sadəcə irəliləyə bilər. Robot bir maneəyə rast gəldikdən sonra "sağ əl" qaydasına uyğun hərəkət etməyə başlayır. Divar boyunca hərəkət edərək, robot sağ tərəfdə bir keçid varsa, nəzarət edir. Bir keçid varsa, robot özünü divardan sağa yırtmamaq üçün onun yanında gəzməlidir. Keçid yoxdursa - divarın qarşısında - robot sola dönür. Yenidən keçid yoxdursa, yenidən sola dönür və beləliklə 180 dərəcə dönərək əks istiqamətə gedir. Şəkildə "sağ qayda" ya uyğun olaraq işləyən bir robotun alqoritminin sxem diaqramı göstərilmişdir. Bu alqoritmin işini yoxlamağa və bunun üçün bir proqram yazmağa çalışaq. Bu məqsədlə GameLogo proqramlaşdırma mühitinə müraciət edirik. Bu mühit robot nəzarəti ilə əlaqəli müxtəlif alqoritmlərin modelləşdirilməsi üçün əlverişli bir vasitədir. Əslində əsl robotdan başqa bir şey olmayan bir ifaçı tısbağası var. Tısbağanın çox uyğun bir əmr dəsti var - irəli, sağa, sola, arxaya. Bundan əlavə, tısbağanın ortasında yerləşdiyi səthin tonundan asılı olaraq 0-dan 100-ə qədər bir dəyəri olan bir sensor var. İstifadə edəcəyimiz loqonun dil ləhcəsi çox sadə və Basic-ə oxşardır. Burada dil əmrləri ilə tanış ola bilərsiniz. GameLogo proqramlaşdırma mühitinin pulsuz yüklənməsi burada. Dağıtımın ölçüsü azdır - cəmi 1 Mb. GameLogo ilə arxivdə, istifadə edəcəyimiz labirintlərdən ibarət arxa plan var. |
Sahənin ölçüsü 800 ilə 600 pikseldir. Tısbağa üçün başlanğıc mövqeyi 115, 545 (ağ kvadrat) koordinatlarında yerləşir.
Labirent yollarının rəngi açıqdır, üzərindəki sensor 50-dən çox dəyərləri götürəcəkdir. Labirentin divarlarının rəngi qaranlıqdır, sensorun dəyəri 50-dən az olacaq. Labirentdən çıxma qara kvadrat ilə təmsil olunur, yuxarıda sensor dəyəri 0 olacaq.
Dəyişən bir bayraq elan edəcəyik, onunla labirentdən çıxmağın olub olmadığını nəzarət edəcəyik.
Proqramı yazacağıq və "Qırış" yazısı olan böyük qırmızı düymənin köməyi ilə başlayacağıq.
Əgər labirintdə ayrı divarlar olmadığı, yəni başlanğıc nöqtəsinə qayıda biləcəyiniz qapalı marşrutlar olmadığı bilinsə, belə bir labirintə sadəcə bağlı deyilir və həmişə "tək əlli" qaydanı tətbiq etməklə tamamilə xaric edilə bilər.
Labirintdə sərbəst dayanan divarlar varsa, "bir əlli" qaydanı tətbiq etməklə, bütün dəhlizlərdən və ölü nöqtələrdən keçmək həmişə mümkün olmur. Ayrı-ayrı divarları olan və qapalı marşrutları olan labirintlərə çoxlu bağlı deyilir. Bu vəziyyətdə, çoxlu bağlı labirintləri iki qrupa bölmək olar: hədəfin ətrafında "döngə" olmadan (qapalı marşrut hədəfin ətrafından keçmir) və hədəfin ətrafında qapalı bir "döngə" olmadan (hədəf qapalı marşrutu aşa bilər).
İkinci qrupun bir-birinə bağlı labirintlərində "bir tərəfdən" qayda işə yaramır və bundan istifadə edərək məqsədə çatmaq mümkün deyil. Ancaq hətta bu labirintləri dəqiq bir alqoritmə güvənərək aradan qaldırmaq olar.
Belə labirintlərin probleminin həlli nisbətən gec zamana aiddir və başlanğıcını Leonard Euler qoymuşdur. Euler, heç bir səbəb olmadan, hər hansı bir labirentdən bir çıxış yolu tapılacağına inanırdı və üstəlik, nisbətən sadə bir şəkildə.
Hər hansı bir labirintdən keçməyin universal alqoritmi yalnız bir əsr sonra Fransız riyaziyyatçısı E. Lukanın 1882-ci ildə nəşr olunan "İstirahət matematikləri" kitabında təsvir edilmişdir. Maraqlıdır ki, alqoritmi izah edərkən Luka başqa bir fransız riyaziyyatçısı M. Tremotun ibrətamizliyinə işarə etmişdir. Beləliklə, alqoritm Luc-Tremo alqoritmi kimi tanındı.
Tremo aşağıdakı qaydaları təklif edir: labirintin istənilən nöqtəsini tərk edərək, divarına bir işarə (xaç) qoyun və ixtiyari bir istiqamətdə son nöqtəyə və ya kəsişməyə doğru hərəkət edin, birinci halda geri qayıdın, yolun iki dəfə getdiyini göstərən ikinci bir xaç qoyun - geri və irəli , və əvvəllər heç getməmiş bir istiqamətə gedin, ikincisində - girişdə və çıxışda hər kəsişməni bir xaç ilə işarələyərək ixtiyari bir istiqamətə gedin, əgər çarmıxda bir xaç varsa, onda yeni bir yola getməlisiniz. deyil t - bu ikinci bir xaçla işarələnən yolu keçdi.
Tremo alqoritmini bilməklə, əfsanəvi Severusun davranışını tənzimləyə bilərsiniz. Sevimli Ariadne'nin hədiyyəsindən ilhamlanaraq labirentlə inamla gəzir. Birdən onun qabağında bir ip artıq çəkilmiş bir hərəkət var. Nə etməli Heç bir halda siz onu keçmirsiniz, ancaq başqa bir yerinə yetirilməmiş bir hərəkət tapana qədər ipi iki qat artıraraq, artıq bilinən yola qayıdın.
Tremo alqoritminin bir variantından istifadə edərək məlumat nəzəriyyəsinin atası Klod Elvud Şannon ilk özünü öyrənən robotlardan birini qurdu. Şannon ona son dərəcə məşhur "esus "adını verdi, lakin" Severus "tarixində daha yaxşı Şannonun" siçanı "kimi tanınmağa başladı. "Siçan" əvvəlcə bütün labirentləri araşdırdı, sonra (ikinci dəfə) iki dəfə keçən ərazilərdən qaçmaqla daha sürətli getdi.
İndi labirintdən keçən robotlar dünyanın bir neçə ölkəsində baş tutan düşüncə maşınlarının ən maraqlı yarışlarından birində iştirak edirlər. Bu yarışlar kollektiv olaraq Micromouse yarışları adlanır və texniki yenilikləri baxımından robot idman növlərinin liderlərindən biridir.
Yarışlar ilk Rus Robotlar Olimpiadasında keçirildi, məqsədi bir növ labirentə keçmək idi: ən qısa müddətdə divarlarda "açıq qapılar" dan keçərək robot başlanğıc nöqtəsindən sona çatmalı oldu. Robot labirentin döşəməsinə çəkilmiş qara xətlər boyunca hərəkətini idarə edə bildi.
BİR ƏLİNİN QAYDASI
İtirmək qorxusu olmadan hər hansı bir labirentə girməyin çox sadə yolu var. Bu qaydanı istifadə edərək, hər hansı bir labirintdən, keçişlərinin nə qədər qarışıq olmasından asılı olmayaraq hər zaman bir çıxış yolu tapa bilərsiniz. Burada labirentlərdə təhlükəsiz gəzmək qaydası var:
Dadına eyni əl ilə toxunaraq labirentdən keçmək lazımdır.
Bu o deməkdir ki, labirintin girişində divarınızı bir əlinizlə (eyni, sağa və ya sola) toxunmalısınız və içərisində gəzərkən eyni əllə divara toxunmağa davam edin.
Çalışın - bu üsulu sınamaq - Hampton Maze planı boyunca zehni gəzinti üçün "bir əlli qayda" tətbiq edin. Bir kibritlə silahlanaraq, bu bağ labirintinə girdiyinizi və divarlarınıza bir əllə toxunduğunuz müddətdə xəyal edin. Tezliklə labirentin mərkəzinə xarici girişdən alacaqsınız. Əlinizi buradan aşağı salmayın, divarlara toxunaraq hərəkət etməyə davam edin və yenidən qarmaqlarından çıxaraq xarici girişə doğru gedəcəksiniz.
Bu rahat qayda haradan gəldi? Bunu başa düşməyə çalışacağıq. Təsəvvür edin ki, yalnız bir girişi olan bir otağa girməyinizə göz yumur. Bütün bunları gəzib yenidən çıxmaq üçün nə etməlisən? Ən asan yol, əllərinizi divardan götürmədən divar boyunca gəzməkdir, sonra mütləq daxil olduğunuz qapıya çatacaqsınız. Burada "bir tərəfdən idarəetmə" nin rasionallığı özünü izah edir. İndi təsəvvür edin ki, otaq divarlarında əncirdə göstərildiyi kimi çıxıntılar var. 4 və 5. Daha əvvəl sadə otaqlar deyil, həqiqi labirintlər. Ancaq "bir əlli qayda", əlbəttə ki, və bu hallarda öz gücünü qorumalı, sizi etibarlı şəkildə sizi binadan çıxmağa aparır.
"Bir əlin qaydası" nın uyğunsuzluğu var. Ondan istifadə edərək hər hansı bir labirintə girib, şübhəsiz ondan çıxa bilərsiniz. Ancaq bu, labirentin bütün guşələrini istisnasız olaraq gəzəcəyiniz demək deyil. Yalnız divarları labirintin xarici divarı ilə bağlı olan yerlərə baş çəkəcəksiniz - olduğu kimi, davamı da. Ancaq labirintin divarları xarici divarları ilə əlaqəsi olmayan hissələrindən keçəcəksiniz. Hampton bağ labirintində yalnız belə bir sayt var və buna görə də "bir əlli" qaydanı istifadə edərək, bu labirintin bütün yollarını keçə bilməzsiniz: bir yol dəyişdirilmədən qalır. Əncirdə "Bir əlli qayda" dan istifadə etsəniz, 6 boşluqlu xətt hedcinqin divarları boyunca yolu göstərir və həmin xiyaban eyni anda təyin olunmamış qalır.
