Creierul incepe sa fiarba!

Una dintre regulile cele mai simple pentru trecerea labirint este regula de „o singură mână“: se deplasează prin labirint, aveți tot timpul pentru a atinge dreapta sau la stânga pereților săi. Acest algoritm a fost, probabil, cunoscut de grecii antici. Va trebui să mergem un drum lung, merge la toate capetele moarte, dar în cele din urmă este atins obiectivul. Cu toate că această regulă și există un dezavantaj, dar vom discuta mai târziu.
Dacă știți că există un labirint de ziduri distincte, adică nu există niciun traseu închis, prin care vă puteți întoarce la punctul de plecare, atunci acest labirint numit pur și simplu conectat și este întotdeauna posibil pentru a obține în jurul valorii de complet, aplicarea regulii de la „o mână“.

În cazul în care labirint conține perete de sine statatoare, apoi, aplicând regula de „o mână“ nu este întotdeauna posibil să se treacă prin toate coridoarele și fundături. Labirinturi cu pereți autosustinere și un traseu închis numit multiplice. În acest caz, labirinturi multiplica pot fi împărțite în două grupe: fără „bucle“ în jurul țintei (traseu închis trece în jurul țintei) și o „buclă“ închisă în jurul țintei (țintă pot fi ocolite pe ruta închisă).

În al doilea grup de labirinturi multiplica regula „o mână“ nu este de lucru și aplicarea acesteia, este imposibil de a atinge obiectivul. Dar aceste labirinturi pot merge, bazându-se pe algoritmul exact.

Soluția de rezolvare a acestor labirinturi aparține unei perioade relativ târziu, iar începutul ei ar trebui să Leonardom Eylerom. Euler nu credea fără motiv că producția de oricare din labirint poate fi găsit, și mai mult decât atât manieră relativ simplă.

Algoritmul universal pentru trecerea tuturor labirinturi a fost descris doar într-un secol în cartea matematicianului francez E. Lucas „agremente matematiques“, publicat în 1882. Este interesant faptul că Luca descrie algoritmul indicat superioritatea unui alt matematician francez M. trei. Astfel, algoritmul a devenit cunoscut ca un algoritm sau trei Luc.

Trei propus următoarele reguli: provenind din orice punct al labirint, este necesar să se facă un semn pe perete (cruce) și pentru a muta în orice direcție impasului sau intersecția; în primul caz să se întoarcă, pentru a pune de-al doilea cruce, indicând faptul că drumul traversat de două ori - acolo și înapoi, și du-te într-o direcție care nu este niciodată călătorit sau a călătorit o dată; în al doilea - pentru a merge într-o direcție arbitrară, marcând fiecare intersecție pe admisie și evacuare unul cruce; în cazul în care, la intersecția unei cruci este deja acolo, ar trebui să meargă într-un mod nou, în cazul în care nu - atunci a trecut prin al doilea observând crucea.

Cunoașterea algoritmului la trei, puteți ajusta comportamentul legendarului Tezeu. Cadouri Inspirate iubit Ariadne, el cu încredere în mișcare prin labirint. Dintr-o dată există o mișcare, care a întins deja firul în fața lui. Ce să fac? În nici un caz nu o cruce, și du-te înapoi pe fir căi deja cunoscute sdvaivaya până când există un alt curs de neîmplinită Promise.

Aplicarea algoritmului Tremaux de realizare, tatăl teoria informației Klod Shennon (Claude Elwood Shannon), construit de unul dintre primii roboți auto-învățare. Shannon ia dat un nume răsunător de „Tezeu“, dar în istoria „Tezeu“ a devenit mai bine cunoscut sub numele de „mouse-ul“ Shannon. „Mouse“ este inspectat mai întâi întregul labirint, și apoi (a doua oară) merge tot drumul este mult mai rapid, evitând în același teren traversat de două ori.