29 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Программируем… выход из лабиринта

Программируем… выход из лабиринта

Наверное, некоторые из вас смотрели фильм «Бегущий в лабиринте», где группа подростков живет в ущелье в центре лабиринта, населенного чудовищами? Они находят выход, умело используя подсказки. Но существуют алгоритмы и даже программы, способные на поиск выхода из лабиринта. О них мы и поговорим.

Как пройти лабиринт?

Зачем нам какой-то лабиринт лабиринт, спросит читатель? И как мы можем его найти с помощью программы? Ведь она ходов-выходов не видит? И, потом, есть ведь правило «левой» и «правой» руки, которое, наверное, дает возможность отыскать выход в любом лабиринте.

Действительно, программа выхода не видит. А вот правило «левой или правой» руки запросто может не сработать, если лабиринт имеет независимые элементы, несвязанные непрерывными стенами с остальной частью системы ходов. Тогда остается лишь… общий для всего лабиринта пол, который никак не поможет нам определить верное направление.

Кроме того, существуют крайне запутанные лабиринты чрезвычайной сложности, проследить которые непросто, а для нахождения пути через них может потребоваться длительное время. Есть извилистые тропы со множеством ответвлений, которые можно преодолеть по кратчайшему пути, сэкономив припасы, силы или горючее для автомобиля (смотря что вам подскажет воображение). И они же окажутся очень длинными, если двигаться по случайному пути.

Лабиринт может быть и не лабиринтом, а картой метро или схемой дорог, которую нужно проскочить с наименьшими затратами либо серпантином горных ущелий, среди крутых склонов которых надо выбрать наиболее доступные. Словом, вариантов много. Так как же нам поступить?

Вездесущая матрица

Мы, конечно, люди современные и понимаем, что для составления маршрута нам необходима карта местности, хотя бы приблизительная. А если её нет — придется её составить. Включим воображение и представим, что мы у порога лабиринта, а в руке у нас пульт от квадрокоптера с видеокамерой. Раз, два, три — дрон уже в воздухе и снимает наш лабиринт сверху. Возможны варианты. Если это пещера — мы отправляем туда самодвижущийся механизм на гусеницах, если подводный «Аравийский тоннель», как в книге про капитана Немо (там предполагалось, что на месте нынешнего Суэцкого канала существует сквозная пещера, соединяющая Средиземное и Красное моря) — то подлодку-дрон. Их нестрашно потерять и карту своего пути они передадут нам с помощью современных технических средств.

Но путь — это только полдела. В современной реальности важнее всего иметь под рукой самый короткий, удобный и дешевый путь, чтобы ускорить перевозку и обойти конкурентов. А составление кратчайшего пути — это уже задача, вполне решаемая для компьютера.

Весь пройденный одной или другой (в зависимости от условий задания) машиной маршрут представляем себе в виде двумерной (в некоторых, особо сложных случаях — трехмерной матрицы. Помните фантастический фильм «Матрица»? Там фигурировала плоская конструкция из множества сот, заполненных человеческими телами. Наша матрица будет содержать ячейки с данными, расположенные на одинаковом удалении друг от друга — по примеру обычной географической карты в Google или Yandex.

В простейшем варианте матрица будет горизонтальным полем. Представьте себе шахматную доску. Каждый квадрат получит аналогичные шахматным координаты. Допустим, третья ячейка сверху будет четвертой по счету в своем ряду. Если это ущелье, то значением самой ячейки может быть высота или крутизна склона. Если вокруг дороги отвесные стены, то ячейка либо проходима либо нет.

Конечно, если наш лабиринт имеет несколько уровней, да ещё и с пересечением высот, потребуется трехмерная матрица, но её мы рассматривать не будем. Если вы заметили, даже в современных играх уровни выполнены независимыми, то есть, их тоже можно представить как двумерные матрицы с дополнительными параметрами.

Проходим лабиринт «волной»

К сожалению, компьютер сам по себе путей не увидит, даже если у него будет под рукой цифровая карта. Ему нужно предложить алгоритм, который обеспечит эффективный поиск пути в матрице, заполненной условными цифровыми обозначениями. Итак, используем для прохождения лабиринта самый простой алгоритм — волновой. И двигаться будем только вправо, влево, вверх и вниз (можно ходить ещё и по диагонали но мы пока этот рассматривать не будем).

Движение «волны» напоминает расходящиеся круги на воде или обвал, когда вниз с горы падает множество камешков. Вокруг стартовой точки, если она расположена не на краю матрицы-карты, всегда находятся ещё четыре точки. Нам необходимо проверить, свободны ли они для прохождения? Инструкция компьютеру будет звучать так: «пройди прямо и проверь, свободна ли клетка впереди? Если да, то перейди туда и измени её единичкой. Если нет, то пройди назад и проверь, свободна ли клетка позади? Если да — перейди туда и пометь её единичкой. Если нет, проверь, свободна ли клетка справа? Если да, то перейди туда и пометь её единичкой. Если нет, проверь клетку слева.

Если вокруг точки или, в данном случае, старта нашего путешествия есть свободные клетки, они будут помечены «единичкой». В следующем шаге мы должны будем пометить «двойкой» все свободные клетки, вокруг клеток с «единичкой», разумеется, кроме уже помеченных. Клетки с «двойкой» обретут собственную задачу — пометят свободное пространство «тройкой» и т.д. Таким образом, волна «разбегается» от центра, огибая препятствия и мгновенно достигает финиша — выхода из лабиринта.

Ну а как же нам найти кратчайший путь? Очень просто. Нужно на каждом шаге, начав отсчет от финиша, искать клетки, помеченные все меньшим и меньшим числом. От «девятки» ищем «восьмерку», от неё — «семерку» и т.д. В 95% случаев таким образом находится кратчайший путь. Но, к сожалению, не всегда. Если набор препятствий имеет сложную форму, то «волна» может «зациклиться». Поэтому, программе нужно установить какой-то эмпирический предел для количества итераций. Чтобы она могла вам сообщить, к примеру: «всё, хозяин, пути нет».

«Реализация волны»

На программном уровне волновой алгоритм строится достаточно просто. Лабиринт мы, или сканируем или, соответствующим образом обрабатываем, получая матрицу, значения ячеек которой отражают проходимость или непроходимость её узлов. Затем эту матрицу мы вносим в программу или подаем на вход в виде файла.

Далее мы создаем три цикла (обязательно три), которые обходят всю матрицу, генерируя волну. Внешний цикл должен иметь границу, не меньшую чем размер длинной стороны матрицы. Внутренние циклы строятся как обычно: один — по количеству строк, а второй — по числу столбцов. В принципе, можно и наоборот.

Затем нам понадобится несколько условий. Точнее, много условий, каждое из которых программа должна проверить. Необходимо уточнить, что представляет из себя каждая из клеток, расположенных вокруг точки старта — это тупик или это свободная клетка? А может быть это клетка — финишная. А может быть стартовая? Для простоты «волной» мы будем помечать только свободные клетки. Конечно, необходимо проверять, не является ли клетка финишной. Ну и, конечно, стоит завершить работу всех трех циклов при прохождении финиша.

Есть ещё один немаловажный момент — для того, чтобы каждая волна была помечена числами по возрастанию, нам потребуется коэффициент, который надо увеличивать перед завершением внешнего цикла, который и является «генератором» волны. Этот коэффициент мы назовем Ni. Определителем максимального количества итераций будет коэфициент Nk. Матрицу мы смделали квадратной и количество ячеек в ней обозначим переменной n. Массив наш назовем lab — от слова «лабиринт». Переменными, работающими во внутренних циклах будут обычные i, j, во внешнем — l. Переменные z и k получат значения точки выхода из лабиринта, когда цикл закончится.

Читать еще:  Ошибка 633 модем используется или не настроен

Завершим работу циклов с помощью оператора break и метки label. Как мы знаем, break останавливает только свой цикл. Поэтому метку вынесем за внешний.

Для прокладки пути у нас есть массив, аналогичный первому. Для удобства он заполнен однородными цифрами. Соответственно, после окончания той части программы, которая прокладывает волну, сработает вторая — помечающая кратчайший маршрут. Циклов нам здесь понадобится всего два, так как вокруг любой точки, в нашем случае, будет только одна точка, ближайшая ко входу и все проверять уже не потребуется. Как только мы найдем эту точку, мы присвоим её координаты нашим переменным z и k, тем самым, продвинувшись к выходу на один шаг. Саму клетку мы будем обозначать коэффициентом Ni, снижая его на одну единицу за каждую итерацию внешнего цикла.

Очень важное добавление: нам потребуется начинать просмотр матрицы не с первого элемента, а со второго. И заканчивать мы будем предпоследним элементом последней строки. Иначе первые числа первой строки и столбца и последняя цифра массива обязательно сделают запрос к несуществующим точкам по адресам 0, 0-1 и 0-1, 0. Так мы выйдем за границы цикла и будет ошибка.

Вот как выглядит эта программка на языке Java в максимально упрощенном для восприятия виде, без функций и методов. Добавлю, что для удобства и понимания я свел её в один листинг, а вывод маршрута сделал в отдельном массиве, заполненном однородными числами.

Код работает на любом компиляторе Java. Его можно скопировать и запустить. Можно исследовать волновой алгоритм на предмет прохождения различных препятствий сложной формы. При необходимости его можно переписать на языке C, использовать в лабораторной работе, создать соответствующий метод или функцию или даже написать небольшую игру. Код снабжен краткими пояснениями на английском языке.

Курсы по программированию

Формула программиста

Работая с этим сайтом, Вы даете согласие на использование файлов Cookie.

19391

— Dmitry-BY

Закрыть

Комбинаторика / Динамика. Выход из Лабиринта

  • Мы рассмотрим наиболее популярный, интересный и полезный алгоритм теории графов:
    Поиск кратчайшего пути в графе. В основе идеи лежит принцип динамического программирования.

В качестве графа у нас будет Лабиринт, мы будем в нём искать кратчайший путь из одной клетки в другую.

Прошу перед уроком ознакомиться со следующими материалами:
1. msdn.microsoft.com/ru-ru/library/system.collections.queue’>Очередь в C#.
2. ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%B2_%D1%88%D0%B8%D1%80%D0%B8%D0%BD%D1%83’>Поиск в ширину в графе.

  • Дата отправки отчёта: 13 сентября 2019 г.
  • Задание выполнено: за 1 день 20 час. 2 мин.
  • Чему научился: познакомился ближе с динамическим программированием. Узнал как можно использовать очереди для обхода лабиринта
  • Что было сложным: не совсем понял где здесь динамическое программирование. Суть его заключается в том что мы используем уже готовое решение. Здесь я этого не заметил. Возможно ошибаюсь
  • Оценка видео-уроку:

    Оцени работу

    Начинаем практику по языку C#

    Чтобы стать хорошим программистом — нужно писать программы. На нашем сайте очень много практических упражнений.

    После заполнения формы ты будешь подписан на рассылку «C# Вебинары и Видеоуроки», у тебя появится доступ к видеоурокам и консольным задачам.

    Несколько раз в неделю тебе будут приходить письма — приглашения на вебинары, информация об акциях и скидках, полезная информация по C#.

    Ты в любой момент сможешь отписаться от рассылки.

    Научился: Написал программу поиска выхода из лабиринта. Клёвая программа получилась хочется на ней попробовать поиск в глубь.

    Программируем… выход из лабиринта

    Поиск в лабиринте

    Будем считать, что закрашенные ячейки заполнены, т.е. их посещение невозможно, а незакрашенные ячейки свободные, т.е. по ним можно передвигаться. На каждом шаге можно перейти к одной из свободных соседних ячеек, расположенных ниже, выше, левее или правее данной ячейки. Так, например от ячейки (4,2) (4-я строка, 2-й столбец) возможен переход вверх и вниз, а вправо или влево перейти нельзя. Будем также считать, что входные данные алгоритма будут включать координаты начальной и конечной ячеек (например N (1, 3) и K (4,5)). Корректный алгоритм должен срабатывать на всех входных данных.

    Задача поиска в лабиринте может быть поставлена в 4-х вариациях.

    A) Определить, существует ли путь от начальной ячейки до конечной.

    B) Вычислить один из путей, если таковые существует. Под путем понимается последовательность свободных ячеек. (при этом каждая ячейка посещается не более одного раза).

    Примеры путей из N в K для лабиринта на рис. 1.

    I) (1,3) (2,3), (2,2) (3,2) (4,2) (4,3) (4,4) (4,5)

    II ) (1,3) (2,3), (2,2) (3,2) (4,2) (4,3) (4,4) (5,4) (5,5) (4,5)

    III ) (1,3) (2,3) (2,4) (2,5) (3,5) (4,5)

    C) Вычислить все пути из начальной ячейки в конечную.

    D) Вычислить оптимальный путь из начальной ячейки в конечную. При этом под оптимальным путем понимается наикратчайший из всех путей по числу ячеек.

    Замеч. На самом деле задача D может быть поставлена и в более сложном варианте, а именно каждой свободной ячейке может быть поставлен в соответствие вес, а длина пути может определяться по сумме этих весов. Алгоритм, впрочем, усложняется незначительно.

    Идея алгоритма, основанная на использовании поиска с возвратом ( backtracking )

    Рассмотрим алгоритм решения данной задачи с помощью поиска с возвратом ( backtracking ).

    Замеч. Под backtracking (поиск с возвратом) понимается класс рекурсивных алгоритмов для решения определенного класса задач. Идеи таких алгоритмов основаны на том, что в каждый момент времени алгоритм делает пробный шаг, затем еще одни пробный шаг и т.д, если в какой-то момент времени мы заходим в «тупик», то возвращаемся на щаг назад. И так продолжаем перебор до тех пор, пока не придем к решению или не будут исчерпаны все варианты.

    Применим эту идею к нашей задаче. Находясь в ячейке ( i , j ) мы можем пробовать «двигаться» вниз, вверх, влево, вправо, т.е. пытаться перейти к ячейкам соответственно ( i +1, j ), ( i -1, j ), ( i , j -1), ( i , j +1). После успешного выполнения перехода необходимо продолжить этот процесс. На структурном языке эта идея легко реализуется с помощью рекурсии.

    Замеч. Рекурсия – это процесс самовызова процедуры или функции из самой себя.

    Обратим внимание, что перед тем, как сделать шаг (произвести рекурсивный вызов) нам следует проверить не нарушаем ли мы условия задачи, т.е.

    1) мы не переходим к заполненной ячейке

    2) мы не выходим за пределы лабиринта.

    Для того, чтобы отдельно не рассматривать 2-й случай используется окаймление лабиринта заполненными ячейками по периметру. Лабиринт из нашего примера после окаймления будет иметь вид:

    На языке паскаль данный лабиринт можно описать в виде бинарного двумерного массива, где 0 соответствует заполненной ячейкой, а 1 – свободной.

    данный лабиринт можно описать в разделе CONST (описания констант) следующим образом:

    lab: array[0..6,0..6] of byte =

    Путь можно хранить в двумерном массиве, например way : array [1..200,1..2] of integer ;

    Рассмотрим подробнее алгоритмы для решения каждой из частных задач.

    Рекурсивная процедура для решения задачи A выглядит следующим образом:

    1 procedure find(x,y: integer);

    3 if (x=xk)and(y=yk) then begin

    5 writeln(‘there is a way’);

    10 if lab[x+1,y]=1 then find(x+1,y);

    11 if lab[x-1,y]=1 then find(x-1,y);

    12 if lab[x,y-1]=1 then find(x,y-1);

    13 if lab[x,y+1]=1 then find(x,y+1);

    И так параметры процедуры x и y – суть координаты ячейки, к которой мы перешли за счет данного вызова. В 3-й строке происходит проверка не является ли данная ячейка конечной, в этом случае на экран выдается сообщение « there is a way » (пусть существует) и с помощью вызова стандартной функции halt происходит завершение выполнения программы (если же выполнение процедуры завершится стандартным образом, то это будет означать, что пути не существует, о чем легко выдать сообщение в основной программе). В 9-й строке прописываем в элемент массива, соответствующей текущей ячейки 2 , что помечает ее, как уже посещенную и препятствует ее повторному посещению при поиске пути. В 10-й строке с помощью рекурсивного вызова моделируется шаг вниз в том случае, если он возможен (ячейка «под данной» свободна и не является посещенной). В 11-й, 12-й и 13-й строках моделируется шаги соответственно вверх, вправо и влево. Очевидно, что каждый вызов будет произведен только в том случае, если предыдущие попытки перемещений не привели к успеху. В 14-й строке текущая ячейка, вновь отмечается, как непосещенная, что фактически моделирует возвращение на шаг назад после завершения работы данного вызова процедуры.

    Читать еще:  Имя события проблемы startuprepairoffline что делать?

    Данная задача отличается от предыдущей тем, что по ходу посещения ячеек данную информацию следует сохранять в массиве way (строки 6 и 7 ), а псоле достижения цели информация о найденном пути выводится на экран (строка 11). Фунция find приведена ниже :

    procedure find(x,y: integer);

    if (x=xk)and(y=yk) then begin

    writeln(‘there is a way’);

    11 for i:=1 to c do writeln(way[i,1],’ ‘, way[i,2]);

    if lab[x+1,y]=1 then find(x+1,y);

    if lab[x-1,y]=1 then find(x-1,y);

    if lab[x,y-1]=1 then find(x,y-1);

    if lab[x,y+1]=1 then find(x,y+1);

    Задача C отличается от задачи B тем, что требуется найти не один путь, а все. Этого можно достичь в том случае, если не прекращать сразу перебор в случае успеха (команда halt ), а проложать процесс, и при нахождении новых путей выводить их на экран и так до тех пор пока процесс не завершится. Следует заметить, что в этом случае необходимо отдельно запоминать информацию о том найден ли вообще хоть один путь, ибо процедура find теперь всегда будет завершаться обычным образом. Данная информация запоминается с помощью логической (тип Boolean ) переменной wayexist . Листинг процедуры find ниже .

    procedure find(x,y: integer);

    if (x=xk)and(y=yk) then begin

    writeln(‘there is a way’);

    for i:=1 to c do writeln(way[i,1],’ ‘, way[i,2])

    if lab[x+1,y]=1 then find(x+1,y);

    if lab[x-1,y]=1 then find(x-1,y);

    if lab[x,y-1]=1 then find(x,y-1);

    if lab[x,y+1]=1 then find(x,y+1);

    Особенностью данной задачи является необходимость выявить из найденных путей – кратчайший. На первый взгляд, очевидное решение здесь запоминать каждый найденный пут, а потом среди них выбрать кратчайший. Но математически легко доказывается, что число путей вообще говоря имеет экспоненциальный порядок, и мало то, что алгоритм из-за этого может достигать экспоненциальной временной сложности, так и затраты памяти в этом случае будут экспоненциальные. К счастью, последнего можно избежать. Идея состоит в том, чтобы дополнительно запоминать не каждый найденный путь, а только тот, который окажется короче кратчайшего из уже найденных (действительно, запоминать остальные пути смысла нет). В этом случае понадобится всего один дополнительный массив для хранения оптимального пути wayopt (формат этого массива аналогичен формату массива way ).

    procedure find(x,y: integer);

    if (x=xk)and(y=yk) then begin

    for i:=1 to c do begin

    if lab[x+1,y]=1 then find(x+1,y);

    if lab[x-1,y]=1 then find(x-1,y);

    if lab[x,y-1]=1 then find(x,y-1);

    if lab[x,y+1]=1 then find(x,y+1);

    В строке 11 данного алгоритма проверяется является ли вновь найденный путь короче предыдущего. И если является то корректируются данные о длине оптимального пути (переменная copt ) и о самом пути (массив wayopt ).

    К сожалению, данный алгоритм имеет экспоненциальную временную сложность, что легко доказать с помощью первой теоремы о трудоемкости (см. курс «теория алгоритмов»).

    Для лучшего усвоения темы предлагается:

    1. доказать таки факт экспоненциальности данного алгоритма по времени.

    2. модифицировать алгоритм D на случай взвешенной задачи (см. выше). То есть написать программу высиляющий кратчийший путь не просто по количеству ячеек, а по сумме их весов (считаем, что веса ячеек заданы в отдельной матрице).

    Замеч. Более эффективный (полиномиальный) алгоритм решения данной задачи существует. в рамках изучения элементов теории графов.

    Выход из лабиринта 5 класс информатика

    Выбранный для просмотра документ 1_?нф_5 . +??сс_Р??з??е?+ 3 А?+??орит?+ы ?? н??ше?? жизни_Н. ти ??ыхо?? из ?+. иринт. docx

    Раздел долгосрочного плана:

    Найти выход из лабиринта

    Цели обучения, которые достигаются на данном уроке (ссылка на учебную программу)

    Приводить примеры исполнителей и их системы команд;

    Представлять алгоритм в словесной форме

    представлять алгоритм в словесной форме

    построение маршрута для прохождения лабиринта

    формулировать определение алгоритма

    представлять алгоритм в словесной форме

    приводить примеры исполнителей и их системы команд

    нахождение оптимального маршрута

    Учащиеся умеют описывать алгоритм прохождения алгоритма

    Полезные выражения для диалогов и письма:

    Для решения данной проблемы я …

    Для демонстрации идеи я выбрал следующие …

    Моя программа включает в себя следующие команды

    Академическая честность, обучение на протяжении всей жизни

    Что учащиеся уже знают или что им нужно знать перед этим уроком? (основные понятия, факты, формулы, теории)

    Как Вы можете активизировать уже имеющиеся знания?

    Запланированные этапы урока

    Запланированная деятельность на уроке

    Приветствие учащихся, проверка присутствующих

    Постановка темы и целей урока

    Попросите учащихся привести примеры, где они встречали лабиринты. В дополнение к ответам учащихся демонстрация слайдов с различными примерами строительства и использования лабиринтов.

    Совместно с учащимися определить цели урока/Цели обучения

    Вспомнить с учащимися исполнителя Робот.

    ( Г ) Предложите учащимся разобрать таблицу и запомнить, какие команды составляют систему команд исполнителя Робот.

    Ознакомление учащихся с методами поиска оптимального пути для прохождения лабиринта. Предложить ученикам найти несколько возможных ходов и выбрать наиболее приемлемый. Лучшим в данном случае считается путь, имеющий наименьшую длину.

    Раздать изображения лабиринтов учащимся.

    Предложите учащимся в парах выполнить задания по написанию алгоритма для прохождения лабиринта роботом.

    Предложите учащимся для проверки обменяться друг с другом своими алгоритмами для прохождения лабиринта.

    Определение понятий «маршрут» и «выбор».

    (К.И) Предложите учащимся карточки с изображением лабиринта из учебника. Им необходимо найти три различных маршрута для прохождения лабиринта и обозначить их различным цветом.

    Объясните учащимся необходимость тестирования алгоритма при его написании.

    Учитель наблюдает за работой.

    После выполнения задания для проверки правильности написания алгоритма попросить учащихся произвести обмен по часовой стрелке. При нахождении ошибки попросите исправить ее совместно.

    Обсуждение результатов с классом

    (К) Попросите учащихся составить алгоритм для прохождения лабиринта с условием сбора всех находящихся в нем предметов.

    Предложите учащимся вспомнить, что было выполнено на уроке. Примерные ответы:

    Узнали новые слова «маршрут», «выбор», команды исполнителя

    Научились создавать словесные алгоритмы для прохождения алгоритма

    Обсудите, что показалось наиболее сложным и чему надо уделить больше времени на следующие занятии.

    Дифференциация – каким образом Вы планируете оказать больше поддержки? Какие задачи Вы планируете поставить перед более способными учащимися?

    Оценивание – как Вы планируете проверить уровень усвоения материала учащимися?

    Здоровье и соблюдение техники безопасности

    Составление маршрута прохождения лабиринта с условием сбора всех находящихся в нем предметов

    Представляет алгоритм в словесной форме

    Будут использовать команды исполнителя Робот

    Познакомятся с возможностью выбора оптимального маршрута

    Используемые физминутки и активные виды деятельности.

    Пункты, применяемые из Правил техники безопасности на данном уроке.

    Были ли цели урока/цели обучения реалистичными?

    Все ли учащиеся достигли ЦО?

    Если нет, то почему?

    Правильно ли проведена дифференциация на уроке?

    Выдержаны ли были временные этапы урока?

    Какие отступления были от плана урока и почему?

    Используйте данный раздел для размышлений об уроке. Ответьте на самые важные вопросы о Вашем уроке из левой колонки.

    Читать еще:  Как узнать тактовую частоту оперативной памяти?

    Какие два аспекта урока прошли хорошо (подумайте как о преподавании, так и об обучении)?

    Что могло бы способствовать улучшению урока (подумайте как о преподавании, так и об обучении)?

    Что я выявил(а) за время урока о классе или достижениях/трудностях отдельных учеников, на что необходимо обратить внимание на последующих уроках?

    Выбранный для просмотра документ 2_?нф_5 . +??сс_Р??з??е?+ 3 А?+??орит?+ы ?? н??ше?? жизни_Н. ти ??ыхо?? из ?+. иринт. pptx

    Описание презентации по отдельным слайдам:

    Найти выход из лабиринта Тема урока

    Цели обучения: Приводить примеры исполнителей и их системы команд; Представлять алгоритм в словесной форме Ключевые слова Маршрут Выбор

    • Карапова Адеми Кабдыгаликызы
    • Написать
    • 637
    • 20.01.2019

    Номер материала: ДБ-381586

    Добавляйте авторские материалы и получите призы от Инфоурок

    Еженедельный призовой фонд 100 000 Р

    • 24.11.2018
    • 99
    • 09.11.2018
    • 236
    • 27.05.2018
    • 179
    • 27.05.2018
    • 140
    • 26.05.2018
    • 104
    • 26.05.2018
    • 130
    • 26.05.2018
    • 180
    • 19.05.2018
    • 263

    Не нашли то что искали?

    Вам будут интересны эти курсы:

    Оставьте свой комментарий

    Все материалы, размещенные на сайте, созданы авторами сайта либо размещены пользователями сайта и представлены на сайте исключительно для ознакомления. Авторские права на материалы принадлежат их законным авторам. Частичное или полное копирование материалов сайта без письменного разрешения администрации сайта запрещено! Мнение редакции может не совпадать с точкой зрения авторов.

    Ответственность за разрешение любых спорных моментов, касающихся самих материалов и их содержания, берут на себя пользователи, разместившие материал на сайте. Однако редакция сайта готова оказать всяческую поддержку в решении любых вопросов связанных с работой и содержанием сайта. Если Вы заметили, что на данном сайте незаконно используются материалы, сообщите об этом администрации сайта через форму обратной связи.

    Компьютерная программа прохождения лабиринта

    Задача прохождения лабиринта описывалась неоднократно и пересказывать сказанное мы не будем. Разновидности лабиринтов и методы их прохождения подробно описаны на различных сайтах Интернета.

    Кратко остановимся только на следующем правиле прохождения лабиринта.

    Правило «одной руки»

    Правило «одной руки» является одним из самых простых для прохождения лабиринта, суть которого сводится к алгоритму: двигаясь по лабиринту, надо все время касаться правой (или левой) рукой его стены. Придется пройти не самый короткий путь, заходя во все тупики, но в итоге цель будет достигнута.

    Последовательность действий робота при проходе лабиринта такова:

    В начале робот должен найти стену, по которой он будет следовать. Для этого он может просто двигаться вперед, пока не упрется в преграду. После того как робот наткнулся на препятствие, он начинает передвигаться в соответствии с правилом «правой руки». Двигаясь вдоль стены, робот следит, есть ли проход справа. Если проход есть, робот должен идти по нему, чтобы не оторваться от стены справа. Если прохода нет — впереди стена — робот поворачивает налево. Если прохода снова нет, он еще раз поворачивает налево, таким образом разворачиваясь на 180 градусов, и идет в обратном направлении.

    Если у лабиринта нет замкнутых маршрутов, по которым можно возвращаться в исходную точку, то такой лабиринт называют односвязным и его всегда можно обойти полностью, применив правило «одной руки».

    Блок-схема алгоритма для робота, работающего по правилу «правой руки», представлена и подробно описана на сайтах Интернета.

    Ниже представлены три программы прохождения лабиринта по указанному методу, написанные на языках C, Pascal и Delphi.

    Программа прохождения лабиринта на языке C

    Программа прохождения лабиринта на языке Pascal

    Программа прохождения лабиринта на языке Delphi

    Заказать исходный текст программы прохождения лабиринта на Delphi: azov192@gmail.com

    Александр Малыгин

    Объект обсуждения — программное обеспечение для выполнения автоматизированного конструкторского и технологического проектирования, разработки управляющих программ, вопросы, связанные с разработкой прикладных САПР.

    Проекты Altera Quartus II для платы Марсоход

    Сделаем машинку-робота, который выбирается из лабиринта.

    Мы уже писали, как сделать машинку-робота, двигающегося по полосе вот здесь projects/plata1/28-run-over. Теперь, с этими знаниями мы двигаемся вперед.

    Из предыдущего проекта у нас есть все: машинка с двумя двигателями, плата Марсоход, свето-чувствительные датчики.

    Мы изменим мозги нашего робота, чтобы он мог выполнять новую задачу — поиск выхода из лабиринта.

    Для начала займемся «рисованием». Дело это творческое. Нужно придумать рисунок лабиринта и нарисовать его на большом листе бумаги. Следует сразу учесть, что тупики в лабиринтах должны быть такой ширины, чтобы наш робот мог спокойно там развернуться и ехать назад. Таким образом, от размера робота зависит размер лабиринта.

    Когда эскиз лабиринта готов — приступаем к его «рисованию» в натуральную величину. Нам понадобятся большие листы белой бумаги, например ватман или что-то такое. Склеиваем их в одно большое полотно и рисуем:

    Лучше всего рисовать гуашью. Сохнет быстро и достаточно черная.

    Чем больше «рисовальщиков», тем быстрее идут дела.

    Вот что получается в результате нашей работы:

    Алгоритм выхода из лабиринта выбираем самый простой: если идти вдоль стены и держаться за нее всегда только одной рукой, то ВСЕГДА выйдешь к выходу. Не важно какой стены придерживаться правой или левой все равно выйдешь. Мы будем делать леворукого робота.

    Прикрепляем имеющиеся у нас два свето-чувствительных датчика к машинке с левой стороны:

    Вид на машинку с двумя датчиками сверху:

    Теперь продумываем алгоритм. Он будет примерно такой:

    Если под левым датчиком черно, а под правым бело,

    то едем прямо. //значит слева от нас — стена, черная полоса и мы держимся за нее

    Иначе, если под левым датчиком бело и под правым датчиком бело,

    то поворачиваем налево. //стена закончилась и есть проход налево.

    Иначе, если под левым датчиком черно и под правым датчиком темно

    то поворачиваем направо. //уперлись в стену, возможен только поворот направо.

    Справедливости ради нужно заметить, что есть еще один вариант, когда под левым датчиками бело, а под правым черно. Это возможно, если мы «переехали» стенку. В этом случае, лучше попытаться ее снова нащупать слева от нас — тоесть нужно повернуть вправо.

    Теперь, когда с алгоритмом разобрались, напишем то же самое на языке аппаратуры, на Verilog.

    module ctrl(
    input wire right_eye, //правый глаз
    input wire left_eye, //левый глаз
    output reg right_motor1,
    output reg right_motor2,
    output reg left_motor1,
    output reg left_motor2
    );

    always @*
    begin
    case ( )
    2’b00:
    begin
    //уперлись в стенку, делаем энергичный разворот вправо
    left_motor1 = 1’b1; //включить левый мотор
    left_motor2 = 1’b0;
    right_motor1 = 1’b0; //включить правый мотор в обратную сторону
    right_motor2 = 1’b1;
    end
    2’b01:
    begin
    //слева черная полоса, справа бело, едем прямо
    left_motor1 = 1’b1; //включить левый мотор
    left_motor2 = 1’b0;
    right_motor1 = 1’b1; //включить правый мотор
    right_motor2 = 1’b0;
    end
    2’b10:
    begin
    //слева бело, а справа черная полоса.
    //такое вообще-то не должно случаться, если не отрывать руку от стены
    left_motor1 = 1’b1; //включить левый мотор
    left_motor2 = 1’b0;
    right_motor1 = 1’b0; //выключить двигатель
    right_motor2 = 1’b0;
    end
    2’b11:
    begin
    //под обоими датчиками бело. Стена слева закончилась, нужно повернуть налево.
    left_motor1 = 1’b0; //выключить двигатель
    left_motor2 = 1’b0;
    right_motor1 = 1’b1; //включить правый мотор
    right_motor2 = 1’b0;
    end
    endcase
    end

    Обратите внимание, что поворот можно осуществлять разными способами. Самый простой способ — выключить один двигатель, а второй включить. Тогда машинка поворачивается в сторону выключенного двигателя. Второй способ более энергичный — включить один двигатель вперед, а второй назад, в противоположную сторону. Направление вращения двигателя определается полярностью питания. Поэтому мы программируем к каждому двигателю два сигнала.

    Полный исходный текст проекта можно скачать на нашем сайте здесь:

    Ну чтож.. Если не придираться, что кое-где машинка наезжает на стены, то вполне так прилично .

    Надеюсь у Вас тоже получится, и даже еще лучше!

  • Ссылка на основную публикацию
    Статьи c упоминанием слов:
    Adblock
    detector