преминаване на лабиринта

Един от най-простите правила за преминаване на лабиринта е правилото на "една ръка": движещ се през лабиринта, ще трябва през цялото време да се докоснат до дясната или лявата страна на стените му. Този алгоритъм вероятно е била известна на древните гърци. Ние ще трябва да извърви дълъг път, ще всички безизходиците, но в крайна сметка целта е постигната. Въпреки, че това правило и има един недостатък, но ние ще обсъдим по-късно.

Опитайте се да опишете на робота, като действа в съответствие с принципите на "дясната ръка".

В началото на своята работа на робота трябва да намери стената, на която ще последва. За да направите това, той може просто да се движи напред и докрай срещу бариерата.

След като роботът блъсна в пречка, тя започва да се движи в съответствие с принципите на "дясната ръка".

Движейки се по поречието на стената, на робота следи дали има пасаж в дясно. Ако преминаването е, роботът трябва да мине през него, така че да не се откъсне от стената в дясно.

Ако преминаването не е - в предната част на стената - робот се обръща наляво. Ако не пасаж отново, тя се включва отново наляво, като с това включва на 180 градуса, и отива в обратната посока.

Схемата за робот, работещи в съответствие с "дясната ръка", показана на фиг.

Опитайте се да проверите работата на алгоритъма и напишете програма за него. За тази цел се обърнат към среда за програмиране GameLogo. Тази среда е удобен начин да се симулира различни алгоритми, свързани с контрола на роботи. Той има костенурка изпълнител, който по същество не е нищо като истински робот. Костенурка е с много лесен за употреба набор инструкции - напред, надясно, наляво, обратно. Освен това, в центъра има костенурки сонда, получаване на стойност от 0 до 100, в зависимост от сигнала на повърхността, върху която се намира.

Диалектът език лого, което ще използваме една много проста и подобно на Basic. Запознайте се с най-езикови команди тук. Безплатно изтегляне сряда GameLogo програмиране - тук. Разпределението на размера е малък - само 1 Mb.

Архивът с GameLogo имат образование и опит, лабиринт, един от които ще използваме.

В самото начало на програмата ще даде екипа на костенурка, така че тя взе писалката (по подразбиране, костенурката оставя следа).

Размерът на поле - 800 до 600 точки. Изходното положение за костенурката е координира 115, 545 (бяло квадратче).

Цвят лабиринта пътища - светлина, те ще вземат сензора 50. Цветните стойности са по-големи от стените на лабиринта - стойност тъмно сензор е по-малко от 50. От лабиринта е представен от черен квадрат, върху което стойността на сензора е равна на 0.

Декларирам променлива флаг, с което ние контролираме, изход от лабиринта достигната.

Напишете програма, и да го стартирате с големия червен бутон с надпис "Run".

Ако знаете, че там е лабиринт от отделни стени, която е не затворени пътища, чрез които можете да се върнете към началната точка, а след това този лабиринт, наречен просто да се свърже и винаги е възможно да се получи около напълно, прилагането на правилото за "една ръка".

Ако лабиринта съдържа свободностоящ стена, а след това, прилагането на правилото за "една ръка" не винаги е възможно да се мине през всички коридори и безизходиците. Лабиринти с свободно стоящи стени и затворен маршрут, наречен размножава. В този случай, умножение лабиринти могат да бъдат разделени на две групи: без "линии" около целта (затворен маршрут преминава около целта) и затворено "линия" около целта (мишена може да бъде прескочена за затворен път).

Робот за преминаване на лабиринта на базата на ATmega8
(Micromouse състезания конкуренция).

Във втората група от лабиринти, умножете правило "една ръка" не работи и да се прилага, не е възможно да се постигне целта. Но тези лабиринти могат да отидат, позовавайки се на точното алгоритъм.

Решение на тези лабиринти принадлежи на сравнително късен период и началото на това се предполага, че Leonardom Eylerom. Ойлер не вярваше, без причина, че на изхода на всеки от лабиринта може да се намери, а освен това сравнително прост начин.

Универсален алгоритъм за преминаване на всички лабиринти е описан само в един век в книгата на френския математик Е. Лукас "пресъздаване matematiques", публикуван през 1882. Интересно е, че Лука при описване на алгоритъма е посочено превъзходството на друг френски математик М. три. По този начин, алгоритъмът е станал известен като един алгоритъм или три Люк.

Три предложения на следните правила: идващи от всяка точка на лабиринта, е необходимо да се направи маркировка на стената му (кръст) и да се премести във всяка посока към безизходица или кръстовище; в първия случай да се върна, за да постави втори кръста, което показва, че пътят пресича два пъти - там и обратно, и отиде в посока, която не е никога пътува или пътувал веднъж; във втория - да отиде в произволна посока, маркиране всеки пресичане на входа и изхода на един напречен; ако на кръстовището на кръст е вече там, трябва да се ходи по нов начин, ако не - след това се пропуска, като се отбележи втория си кръст.

Клод Shennon (Claude Елууд Shannon)

Познаването на алгоритъм за три, можете да коригирате поведението на легендарния Тезей. Вдъхновени Подаръци любимия Ариадна, той уверено се движат през лабиринта. Изведнъж има ход, който вече е опъната нишката пред него. Какво да се прави? В никакъв случай не го премине, и да се върнете на вече познатите пътеки sdvaivaya нишка, докато има още един курс на неизпълнено обещание.

Прилагане на алгоритъм Tremaux изпълнение, баща информация теория Клод Shennon (Клод Елууд Шанън), изграден от един от първите самостоятелно учене роботи. Шанън му даде гръмко име на "Тезей", но в историята на "Тезей" стана по-известен като "мишка" Шанън. "Мишка" е първият проверен целият лабиринт, а след това (за втори път) отива по целия път е много по-бързо, като се избягват земя преминават два пъти.

Лабиринт състезания Micromouse конкуренцията.

Днес, роботи, минавайки през лабиринта, са участници в един от най-вълнуващите състезания от мислещи машини, който се провежда в няколко държави. Тези събития се наричат ​​с общото наименование Micromouse конкуренция и нейните технически иновации са лидерите на роботизирани спортове.

На бяха проведени първите български олимпийски роботи състезания, целта на която е преминаването на един вид лабиринт: в най-кратки срокове, движещи се през "отворените врати" в стените, роботът трябваше да се стигне от началната точка до мястото на финала. Контролират движенията си на робота биха могли черни линии, отбелязани на пода на лабиринта.