Našli ste se u ćorsokaku i ne vidite izlaz? NE OČAJAVAJTE! Evo kako JEDNIM POTEZOM možete izaći iz lavirinta!
Lavirint je građevina u Knososu, na ostrvu Kritu.
Po legendi to je bio dvorac kralja Minosa. Po legendi u lavirintu je bio zatvoren Minotaur. Lavirint je bio srušen oko 1700. godine p. n. e.
Međutim, pitanje koje mnogi postavljaju jeste da li postoji metod za izlaženje iz lavirinta?
MOZGALICA KOJA JE ZALUDELA SVET: Možete li da nađete izlaz iz lavirinta? (FOTO)
Milan iz Beograda odveo dete kod lekara zbog krpelja: Nakon intervencije dobio je OGROMAN RAČUN (FOTO)
Dete u pregrejanom autu, a posebno ako je ove boje, može doživeti toplotni udar za samo sat vremena!
Algoritam praćenja zida, predstavlja jedan od najpoznatijih algoritama za pronalaženje izlaza iz lavirinta, a takođe je poznat i pod nazivima "pravilo leve ruke" i "pravilo desne ruke".
Ukoliko je lavirint povezan, odnosno ako su svi njegovi zidovi međusobno spojeni ili ako su spojeni sa spoljašnjom granicom lavirinta, tada ako osoba unutar lavirinta drži ruku u kontaktu sa zidom tokom celog prolaska kroz lavirint garantovano dolazi do izlaza iz lavirinta ako izlaz uopšte i postoji, u suprotnom osoba bi se vratila na ulaz u lavirint i pritom bi obišla svaku putanju u lavirintu barem jedanput.
Ako ovaj problem pogledamo s druge, topološke, strane primećuje se zašto je algoritam praćenja zida u mogućnosti da uvek pronađe pravo rešenje.
Ako su zidovi povezani, to znači da se mogu raširiti u kružnicu. Tako se algoritam praćenja zida redukuje na prolazak ivicama te kružnice od ulaza do izlaza.
PUTIN NAM VRAĆA DRAGOCENOST: Stranica Jevanđelja stiže 20. oktobra, a evo šta će Srbija pokloniti njima kao znak zahvalnosti
OVAJ APARAT JE NAJOPASNIJI KAD GRMI, A NIJE MOBILNI TELEFON: Kada je nevreme, MOŽE VAS UBITI!
RODITELJI, BUDITE OPREZNI Ovo je jedna potencijalno SMRTONOSNA GREŠKA kada su u pitanju vaša DECA!
Ukoliko lavirint nije povezan (npr. ako su ulaz u lavirint ili izlazi iz njega u centru samog lavirinta ili putanje prelaze jedna preko druge ili jedna ispod druge), nije garantovano da će ovaj algoritam zaista u takvim slučajevima pronaći izlaz iz lavirinta.
Algoritam praćenja zidova može se koristiti i u trodimenzionalnim i višedimenzionalnim okruženjima ukoliko te višedimenzione putanje mogu biti projektovane u dvodimenzionalnoj ravni na deterministički način.
Na primer, ukoliko u trodimenѕionalnom algoritmu putanje na "gore" smatramo putanjama ka severo-zapadu, a putanje na „dole“ smatramo putanjama ka jugo-istoku, tada možemo upotrebiti standardna pravila algoritma praćenja zida. Međutim, za razliku od dvodimenzionalnog prostora, ovde je potrebno u svakom momentu znati i trenutnu orijentaciju, da bi se znalo koji smer je prvi nalevo ili nadesno..
Međutim, ukoliko se ulaz nalazi u unautrašnjosti lavirinta, može se naći na zidu koji nije spojan sa zidom na kome se nalazi izlaz, pa bi se korišćenjem algoritma praćenja zidova osoba vrtela u krug i vraćala na početak ne pronalazeći izlaz. Algoritam Džona Pledža može da reši ovaj problem.
Pledžov algoritam, dizajniran da zaobiđe prepreke, zahteva kretanje u napred određenom smeru.
Kada se naiđe na prepreku, jedna ruka (npr. desna) nastavlja da prati prepreku a takođe prati se i broj okreta na levu i desnu stranu korišćenjem brojača okreta. Okretanje na desnu stranu povećava vrednost brojača, a okret na levu stranu smanjuje njegovu trenutnu vrednost. Kada se osoba ponovo okrene ka originalnom unapred određenom smeru, tada je brojač okreta ponovo vraćen na vrednost 0 i prepreka je uspešno savladana, osoba nastavlja sa kretanjem u početnom originalnom smeru ka svom cilju pa ako se ponovo naiđe na prepreku prethodni postupak se ponavlja. Ruka više ne prati zid samo kada je brojač okreta ponovo postavljen na 0. Ovakav pristup omogućava algoritmu da izbegne zamke koje su na primer oblika velikog latiničnog slova G - ("G").
U suštini algoritam je vrlo jednostavan i sastoji se od provere nekoliko pravila koja se proveravaju tokom prolaska kroz lavirint:
(algoritam zasnovan na pravilu desne ruke)
1. Osoba se kreće unapred određenim smerom.
2. Kada se naiđe na prepreku prvi put osoba se okreće na levu stranu. Brojač okreta se tada umanjuje za 1.
3. Vrši se provera postojanja prepreka. Osoba proverava da li postoji prepreka ispred, desno ili levo.
Ukoliko nema prepreke na desnoj strani osoba se okreće na desnu stranu. Brojač okreta se uvećava za 1.
Ukoliko postoji prepreka na desnoj strani, a ne postoji prepreka ispred, osoba se pomera unapred za jedan korak. Brojač okreta ne menja svoju trenutnu vrednost.
Ukoliko postoji prepreka na desnoj strani i postoji prepreka ispred, osoba se okreće na levu stranu. Brojač okreta se tada umanjuje za 1.
Prethodni podkoraci koraka 3 se navedenim redosledom proveravaju sve dok se brojač okreta ponovo ne vrati na vrednost 0 i tada smatramo da je prepreka uspešno savladana.
4. Osoba nastavlja da se kreće početnim smerom, sve dok se ponovo ne naiđe na prepreku ili se stigne do izlaza.
Algoritam zasnovan na pravilu leve ruke može se analogno izvesti iz prethodnog.
Na ovaj način algoritam omogućava osobi koja ume da proverava postojanje prepreka ispred, levo i desno, uspešno pronalaženje izlaza na spoljašnjem zidu iz bilo kog dvodimenzionalnog lavirinta, nezavisno od početne pozicije osobe u lavirintu. Međutim ovaj algoritam ne pruža mogućnost rešavanja suprotnog problema prethodnom problemu. Algoritam neće raditi ako se ulaz nalazi na spoljašnjem zidu lavirinta, a neki cilj u unutrašnjosti lavirinta.
