trecerea labirint

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.

Încercați să descrie robotul, acționând în conformitate cu regula de „mâna dreaptă“.

La începutul activității sale robotul trebuie să găsească peretele pe care îl va urma. Pentru a face acest lucru, el poate pur și simplu merge mai departe până când se oprește împotriva barierei.

După ce robotul lovit într-un obstacol, ea începe să se deplaseze, în conformitate cu regula de „mâna dreaptă“.

Mutarea de-a lungul peretelui, robotul monitorizează dacă există un pasaj pe dreapta. În cazul în care trecerea este, robotul trebuie să treacă prin ea, astfel încât să nu se rupă de peretele din dreapta.

În cazul în care pasajul nu este - în fața peretelui - un robot se întoarce spre stânga. Dacă nici un pasaj din nou, se întoarce din nou spre stânga, întorcându-se astfel la 180 de grade, și merge în direcția opusă.

Schema logică pentru un robot care funcționează în conformitate cu „mâna dreaptă“, prezentată în fig.

Încercați să verifice funcționarea algoritmului și a scrie un program pentru el. În acest scop, la rândul său de programare GameLogo mediu. Acest mediu este un mod convenabil de a simula algoritmi diferite legate de controlul de roboți. Are un interpret broască țestoasă, care, în esență, nu este nimic ca un robot adevărat. Turtle are un set de instrucțiuni foarte user-friendly - înainte, dreapta, stânga, înapoi. Mai mult, în centru există o sondă țestoasă, primind o valoare de la 0 la 100, în funcție de tonul suprafeței pe care este amplasata.

Limba Logo Dialect, pe care le vom folosi un foarte simplu și similar de bază. Faceți cunoștință cu comenzile de limbă aici. O descărcare gratuită de programare miercuri GameLogo - aici. Distribuția dimensiunii este mic - doar 1 Mb.

Arhiva cu GameLogo provin din medii cu un labirint, una dintre care o vom folosi.

Chiar la începutul programului va da echipa broasca testoasa, asa ca a luat pen-ul (implicit, broasca țestoasă lasă o urmă).

Dimensiunea câmpului - 800 la 600 de puncte. Poziția de pornire pentru broasca testoasa este la coordonatele 115, 545 (pătrat alb).

căi labirint de culoare - lumina, ei vor lua senzorul 50. Valorile de culoare sunt mai mari decât pereții labirint - valoarea senzorului de culoare închisă este mai mică decât 50. Din labirintul este prezentat de un pătrat negru, peste care valoarea senzorului este egal cu 0.

Declarați un steag variabil, prin care controlăm, o cale de ieșire din labirint a ajuns.

Scrieți un program și rulați-l cu butonul mare și roșu etichetat „Run“.

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ă).

Robot pentru trecerea labirint bazat pe ATmega8
(concursuri de concurență Micromouse).

Î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.

Klod Shennon (Claude Elwood Shannon)

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.

Labirintul concursuri Micromouse concurență.

Astăzi, roboți, care trece prin labirint, sunt participanți la una dintre cele mai interesante curse de mașini de gândire, care are loc în mai multe țări. Aceste evenimente sunt denumite în mod colectiv Micromouse concurența și inovațiile sale tehnice sunt liderii de sport robotice.

Pe au avut loc primele concursuri pentru Olimpiada din România robot, scopul care a fost trecerea de un fel de labirint: in cel mai scurt timp, se deplasează prin „ușile deschise“ în pereți, robotul a trebuit pentru a obține de la punctul de plecare la locul de sosire. Controlați mișcarea lor pe robotul ar putea linii negre marcate pe podeaua din labirint.