Užitočné tipy

Ako nájsť cestu z bludiska

Pin
Send
Share
Send
Send




Od dávnych čias, labyrinty prinášali zmysel pre tajomstvo a tajomstvo. Herodotus opisuje jeden z prvých labyrintov známych ľudstvu - bol to egyptský labyrint, v ktorom bolo 5 000 miestností. V priebehu času labyrint stratil svoj náboženský a mystický význam a stal sa predmetom zábavy, premieňajúc sa na záhrady a parky vo forme zelených plotov zložitej konfigurácie.

Riešenie bludísk bolo vždy fascinujúcou činnosťou, ale ešte viac vzrušujúce je vytvorenie strojov, ktoré môžu prechádzať cez labyrint.

Jedným z najjednoduchších pravidiel prechodu bludiskom je pravidlo „jednoručné“: pri pohybe bludiskom by ste sa vždy mali dotýkať steny pravou alebo ľavou rukou. Tento algoritmus pravdepodobne poznali starí Gréci. Musíte prejsť dlhú cestu, ísť do všetkých slepých uličiek, ale nakoniec bude tento cieľ dosiahnutý. Aj keď má toto pravidlo jednu nevýhodu, budeme o ňom hovoriť neskôr.

Pokúsme sa opísať robota, ktorý koná v súlade s pravidlom „pravej ruky“.

Na začiatku svojej práce musí robot nájsť stenu, pozdĺž ktorej bude nasledovať. Za týmto účelom sa môže jednoducho pohnúť vpred, kým sa nestane prekážkou.

Keď robot narazil na prekážku, začne sa pohybovať v súlade s pravidlom „pravej ruky“.

Ak sa robot pohybuje po stene, monitoruje, či je napravo priechod. Ak existuje prechod, robot musí kráčať pozdĺž neho, aby sa neodtrhol od steny doprava.

Ak pred stenou nie je žiadny priechod, robot sa otočí doľava. Ak už nie je žiadny priechod, znova sa otočí doľava, teda otočí sa o 180 stupňov a ide opačným smerom.

Bloková schéma algoritmu pre robota pracujúceho podľa „pravého pravidla“ je na obrázku.


Skúsme skontrolovať fungovanie tohto algoritmu a napísať preň program. Z tohto dôvodu sa obraciame na programovacie prostredie GameLogo. Toto prostredie je vhodným nástrojom na modelovanie rôznych algoritmov týkajúcich sa riadenia robota. Má výkonnú korytnačku, ktorá v podstate nie je ničím iným ako skutočným robotom. Korytnačka má veľmi pohodlnú sadu príkazov - vpred, vpravo, vľavo, späť. V strede korytnačky je navyše snímač, ktorý má hodnotu od 0 do 100, v závislosti od tónu povrchu, na ktorom je umiestnený.

Jazykový dialekt loga, ktorý budeme používať, je veľmi jednoduchý a podobný základnému jazyku. Tu sa môžete zoznámiť s jazykovými príkazmi. Tu si môžete zadarmo stiahnuť programovacie prostredie GameLogo. Veľkosť distribúcie je malá - iba 1 Mb.

V archíve s GameLogo sú pozadie s labyrintmi, z ktorých jedno použijeme.

Na samom začiatku programu dáme korytnačke príkaz na zdvihnutie peria (štandardne korytnačka zanechá stopu).

Veľkosť poľa je 800 x 600 pixlov. Počiatočná poloha korytnačky je umiestnená na súradniciach 115, 545 (biely štvorec).

Farba dráh bludiska je svetlá, senzor na nich bude mať hodnoty väčšie ako 50. Farba stien bludiska je tmavá, hodnota senzora bude menšia ako 50. Výstup z bludiska je predstavovaný čiernym štvorcom, ktorého hodnota nad ním bude 0.

Vyhlásime variabilný príznak, ktorým budeme kontrolovať, či je dosiahnutý výstup z bludiska.

Program napíšeme a začneme s pomocou veľkého červeného tlačidla s nápisom „Run“.

Ak je známe, že labyrint nemá oddelené steny, to znamená, že neexistujú žiadne uzavreté trasy, po ktorých sa môžete vrátiť do východiskového bodu, potom sa takýto labyrint nazýva jednoducho spojený a dá sa vždy úplne obísť použitím pravidla „jednoruční“.

Ak labyrint obsahuje voľne stojace steny, potom platí pravidlo „jednoručné“, nie je vždy možné prejsť všetkými chodbami a slepými uličkami. Labyrinty so samostatnými stenami a uzavretými cestami sa nazývajú viacnásobne spojené. V tomto prípade sa môžu viacnásobne spojené labyrinty rozdeliť do dvoch skupín: bez „slučky“ okolo cieľa (uzavretá trasa neprejde okolo cieľa) a so uzavretou „slučkou“ okolo cieľa (cieľ sa dá obísť uzavretou cestou).

V mnohonásobne prepojených labyrintoch druhej skupiny pravidlo „jednej ruky“ nefunguje a jeho pomocou nie je možné dosiahnuť cieľ. Ale aj tieto labyrinty sa dajú prekonať spoľahnutím sa na presný algoritmus.

Riešenie problému týchto labyrintov patrí do pomerne neskorého obdobia a začiatok položil Leonard Euler. Euler, nie bez dôvodu, veril, že cestu z akéhokoľvek bludiska možno nájsť a navyše relatívne jednoduchým spôsobom.

Univerzálny algoritmus prechodu akýmikoľvek labyrintmi bol opísaný až o storočie neskôr v knihe francúzskeho matematika E. Lukea „Recreations matematiques“, uverejnenej v roku 1882. Je zaujímavé, že keď opisoval algoritmus, Luke poukázal na nadradenosť iného francúzskeho matematika M. Tremota. Algoritmus sa stal známym ako Luc-Tremo algoritmus.

Tremo ponúka nasledujúce pravidlá: opustiť ktorýkoľvek bod labyrintu, urobiť si značku na svojej stene (kríž) a pohybovať sa ľubovoľným smerom k slepej uličke alebo križovatke, v prvom prípade ísť späť, dať druhý kríž, čo naznačuje, že cesta prešla dvakrát - tam a späť , a choďte v smere, ktorý nebol nikdy prekonaný alebo raz, v druhom - choďte v ľubovoľnom smere, vyznačte každú križovatku pri vstupe a výstupe jedným krížom, ak už existuje jeden kríž, potom by ste mali ísť novou cestou, ak nie t - ktorá prešla dráhou a označila ju druhým krížom.

Po znalosti algoritmu Tremo môžete upraviť správanie legendárneho Theseusu. Inšpirovaný darom svojej milovanej Ariadne, s istotou prechádza bludiskom. Zrazu pred ním je pohyb, po ktorom už bola napnutá niť. Čo robiť V žiadnom prípade ho neprekrížite, ale vráťte sa po už známej ceste a zdvojnásobte niť, kým nenájdete ďalší nevyplnený ťah.

Použitím variantu algoritmu Tremo, otec informačnej teórie, Claude Elwood Shannon, postavil jedného z prvých robotov s vlastným učením. Shannon mu dal zvučný názov „Theseus“, ale v histórii „Theseus“ sa stal známym „myšou“ Shannona. „Myš“ najskôr preskúmala celé bludisko a potom (druhýkrát) išla oveľa rýchlejšie, vyhýbajúc sa tak prechodu dvakrát.

V súčasnosti sú roboty prechádzajúce labyrintom účastníkmi jednej z najzaujímavejších súťaží mysliacich strojov, ktorá sa koná v niekoľkých krajinách sveta. Tieto súťaže sa spoločne nazývajú súťažami Micromouse a patria medzi vedúcich robotických športov z hľadiska technických inovácií.

Preteky sa konali na prvej ruskej olympiáde robotov, ktorej cieľom bolo prejsť bludiskom: v čo najkratšom čase sa robot musel pohybovať cez „otvorené dvere“ v stenách a musel sa dostať z východiskového bodu do cieľového miesta. Robot mohol ovládať svoj pohyb pozdĺž čiernych čiar nakreslených na podlahe bludiska.

PRAVIDLO JEDNEJ RUKY

Existuje veľmi jednoduchý spôsob, ako vstúpiť do bludiska bez strachu, že sa v ňom stratíte. Pomocou tohto pravidla môžete vždy nájsť cestu z ľubovoľného labyrintu, bez ohľadu na to, aké zmätené sú jeho prechody. Toto je pravidlo bezpečného putovania v bludisku:

Je potrebné prejsť bludiskom a neustále sa dotýkať jeho steny rovnakou rukou.

To znamená, že pri vstupe do labyrintu sa musíte dotknúť jeho steny jednou rukou (rovnakou, pravou alebo ľavou) a počas chôdze v nej sa naďalej dotýkať tej istej ruky rovnakou rukou.

Pokúste sa vyskúšať túto metódu - na mentálnu prechádzku pozdĺž plánu Hampton Maze aplikujte „pravidlo jednou rukou“. Vyzbrojení zápasom si predstavte, že vstupujete do tohto záhradného labyrintu a vždy, keď sa jednou rukou dotknete jeho stien. Veľmi skoro sa dostanete z vonkajšieho vchodu do stredu bludiska. Nespúšťajte tu ruku, pokračujte v pohybe, dotýkajte sa jej steny a budete sa z jej zákutí opäť dostať až k vonkajšiemu vchodu.

Odkiaľ pochádza toto výhodné pravidlo? Pokúsime sa to pochopiť. Predstavte si, že ste so zaviazanými očami vchádzajúci do miestnosti iba s jedným vchodom. Čo by ste mali urobiť, aby ste to všetko obišli a dostali sa z toho znova? Najjednoduchší spôsob je chodiť po stenách bez toho, aby ste ruky zložili, potom sa určite dostanete späť ku dverám, cez ktoré ste vstúpili. Racionalita „pravidla jednej ruky“ je tu samozrejmá. Predstavte si teraz, že steny miestnosti majú výčnelky, ako je znázornené na obr. 4 a 5. Predtým, ako prestanete byť jednoduchými izbami, ale skutočnými labyrintmi. „Pravidlo jednej ruky“ by si však malo samozrejme zachovať svoju silu a v týchto prípadoch by vás malo spoľahlivo priviesť späť k východu z areálu.

„Pravidlo jednej ruky“ má svoje nepríjemnosti. Pomocou neho môžete zadať ľubovoľný labyrint a určite sa z toho dostať. To však neznamená, že budete obísť všetky rohy bludiska bez výnimky. Navštívite iba tie miesta, ktorých steny sú nejakým spôsobom spojené s vonkajšou stenou labyrintu - ako to bolo, jeho pokračovanie. Budete však míňať tie časti labyrintu, ktorých steny nie sú spojené s jeho vonkajšími stenami. V labyrinte v záhrade Hampton sa nachádza práve také miesto, a preto pomocou pravidla „jednoručné“ nemôžete prejsť všetkými cestami tohto labyrintu: jedna cesta zostáva nezmapovaná. Na obr. 6 prerušovanými čiarami je znázornená cesta pozdĺž stien živého plotu, ak použijete „pravidlo jednou rukou“ a hviezdičky označujú uličku, ktorá zároveň zostáva nezistená.

Pin
Send
Share
Send
Send