Алгоритм поиска. Реализация алгоритма поиска выхода из лабиринта и анализ существующих решений Введение
 Скачать 346.18 Kb.
|
|
«Реализация алгоритма поиска выхода из лабиринта и анализ существующих решений» Введение Алгоритм — одно из основных понятий в программировании и информатике. Это последовательность команд, предназначенная исполнителю, в результате выполнения которой он должен решить поставленную задачу. Алгоритм должен описываться на формальном языке, исключающем неоднозначность толкования. Исполнитель может быть человеком или машиной. Лабиринт представляет собой запутанная сеть дорожек, ходов, сообщающихся друг с другом помещений. Лабиринты часто упоминаются в древней мифологии. Минотавр, в древнегреческой мифологии, чудовище с телом человека и головой быка, жившее в лабиринте на острове Крит. Минос, царь Крита, спрятал сына в подземном лабиринте, сооруженном Дедалом. Лабиринт был настолько сложным, что ни один вошедший туда человек не смог бы найти выход. Лабиринты в целом можно разбить по семи различным классификациям: размерности, гиперразмерности,1 топологии, тесселяции2, маршрутизации, текстуре и приоритету. В примере реализации алгоритма используется планарный граф, который можно изобразить на плоскости без пересечений рёбер не по вершинам. (рис 1.1).  Рисунок 1.1 Для поиска кратчайшего пути из лабиринта существует множество алгоритмов. Наиболее популярны алгоритмы: Поиск в ширину Поиск в глубину Алгоритм Дейкстры Поиск A Волновой алгоритм или алгоритм Ли Алгоритмы поиска кратчайшего пути используются во множестве различных областей. Нахождение кратчайшего пути может использоваться для поиска путей между физическими объектами, например, Google Maps или Яндекс Карты. Поиск кратчайшего пути может понадобится для определения наименьшего расстояния в сети дорог. Определение пути может понадобится даже роботу пылесосу. Также поиск кратчайшего пути часто требуется в видеоиграх, чтобы помочь игроку быстрее добраться в нужную точку. Реализация волнового алгоритма на C# Алгоритм волновой трассировки (волновой алгоритм, алгоритм Ли) — алгоритм поиска кратчайшего пути на планарном графе3. Алгоритм работает на дискретном поле, состоящее из ячеек, преимущественно квадратные. Ячейки делятся на два типа – проходимые и непроходимые. Проходимые или свободные, т.е. поиск пути в них может происходить. Непроходимые или стены, через них поиск пути пройти не может. Работа алгоритма состоит из трех этапов: инициализации, распространение волны и восстановление пути. Для построения поля может использоваться множество алгоритмов, например, алгоритм двоичного дерева, Алгоритм «Sidewinder» или алгоритм Эйлера, но для простоты можно сгенерировать случайный массив с использование функции Random() из стандартной библиотеки, который будем вызывать через метод: static void GenerateMap(ref int[,] map) { Random rnd = new Random(); int random; for (int i = 0; i < map.GetLength(0); i++) { for (int j = 0; j < map.GetLength(1); j++) { random = rnd.Next(2); if (random == 0) { random = rnd.Next(2); } map[i, j] = random; } } } Проходимые обозначим 1, а непроходимые 0. За начало пути возьмем ячейку, находящуюся в середине, а за конец первую ячейку лабиринта. После нужно вывести массив в консоль. В итоге получится следующее:  Рисунок 2.1 При выполнении условий проходимости и непринадлежности её к ранее помеченным в пути ячейкам, в каждую ячейку записывается, равное количеству шагов от начального положения, при условии, что ячейка является проходимой. Реализовать это можно так: do { k++; for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) { if (mapN[i, j] == (k - 1)) { if ((j < size - 1) && (mapN[i, j + 1] == 0) && (map[i, j + 1] == 1)) { mapN[i, j + 1] = k; } if ((j > 0) && (mapN[i, j - 1] == 0) && (map[i, j - 1] == 1)) { mapN[i, j - 1] = k; } if ((i < size - 1) && (mapN[i + 1, j] == 0) && (map[i + 1, j] == 1)) { mapN[i + 1, j] = k; } if ((i > 0) && (mapN[i - 1, j] == 0) && (map[i - 1, j] == 1)) { mapN[i - 1, j] = k; } } } } if (k > 50) { Console.WriteLine("Путь не найден!"); f = 1; break; } } while (mapN[xv, yv] == 0); После этого нужно восстановить путь в обратном порядке. Для этого нужно перейти в ячейку с координатами финиша, а дальше через цикл выбрать среди соседних ячейку, помеченную числом на 1 меньше числа в текущей ячейке и добавить ее к пути. Повторять цикл нужно до тех пор, пока координаты пути не окажутся равными координатам выхода. Реализация: static void Move(ref int x, ref int y, int[,] mapN, ref int[,] map) { if ((x < mapN.GetLength(0)) && (mapN[x, y] - mapN[x + 1, y] == 1)) { ++x; map[x, y] = -1; } if ((x > 0) && (mapN[x, y] - mapN[x - 1, y] == 1)) { --x; map[x, y] = -1; } if ((y < mapN.GetLength(0)) && (mapN[x, y] - mapN[x, y + 1] == 1)) { ++y; map[x, y] = -1; } if ((y > 0) && (mapN[x, y] - mapN[x, y - 1] == 1)) { --x; map[x, y] = -1; } } if ((xm != 0) && (ym != 0) && (f == 0)) { do { k++; Move(ref x, ref y, mapN, ref map); if (k > 50) { check = false; break; } } while (xm != x || ym != y); } В результате работы алгоритма должно получиться следующее:  Рисунок 2.2 Сравнение алгоритмов Алгоритм Дейкстры. Самый простой и самый известный алгоритм поиска кратчайшего пути. Был разработан голландским ученым Эдскером Дейкстрой. В простейшем случае, когда для поиска вершины просматривается всё множество вершин, время работы алгоритма есть O4(n2). Для разреженных графов O(n*log*n + m*log*m). Если для хранения вершин использовать фибоначчиеву кучу, то время работы алгоритма составит O(n*log*n + m). Алгоритм A*. A* — это модификация алгоритма Дейкстры, оптимизированная для единственной конечной точки. Алгоритм Дейкстры может находить пути ко всем точкам, A* находит путь к одной точке. Он отдаёт приоритет путям, которые ведут ближе к цели. Вычислительная сложность алгоритма составляет – O(log(h(x)). Алогитм Ли. Алгоритм для поиска кратчайшего пути в графе от стартовой точки к конечной, если это возможно. Вычислительная сложность алгоритма составляет O(n2). Поиск в ширину. Алгоритм поиска в ширину позволяет найти кратчайшие пути из одной вершины невзвешенного (ориентированного или неориентированного) графа до всех остальных вершин. В худшем случае алгоритм посещает все узлы графа, при хранении графа в виде списков смежности, временная сложность алгоритма составляет O(|V| + | E|). Поиск в глубину. Стратегия поиска в глубину, как и следует из названия, состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Временная сложность алгоритма составляет O(|V| + | E|). Примеры использование алгоритма Ли. Часто в компьютерных игра требуется найти оптимальный путь на карте, чтобы игрок смог добраться из одной точки в другую за минимальной время. Для этого применяют алгоритмы поиска пути в графе, например, волновой алгоритм. В серии игр Гта5 игроку нужно проложить маршрут от точки, в которой он находится, до точки, в которую он выбирает на карте. На карте присутствую проходимые участи, они обозначены на карте в виде дорог, а непроходимые помечены темно серым и черным цветом, чаще всего там расположены дома и зоны, в которые игрок не может попасть.  Рисунок 3.1 Алгоритм Ли позволяет определять путь на огромных картах, что необходимо как для компьютерных игр, так и для автоматизации, например в движении автомобиля или самолета по дорогам и авиационным линиям, которые работают по схожим принципам. Это позволяет значительно сэкономить время или помочь человеку, который оказался в неизвестной местности найти путь.  Рисунок 3.2 Волновой алгоритм часто используют при трассировки печатных плат для разных САПР6. Ячейки монтажного поля печатных плат разделяют на свободные и занятые, в которых расположены проводники. Ячейку, с которой начинает распространяться волна, называется источником, а вторую приемником волны. Фронт распространяется только на соседние ячейки, которые имеют с ячейками предыдущего фронта либо общую сторону, либо общую точку. Если волна достигает пути, то осуществляется проведение пути. Источники Список литературы1 Гиперразменость — многообразие размерности n, которое вложено в евклидово пространство на единицу большей размерности n+1. 2 Тесселяция — детализация. 3 Планарный граф — граф, который можно изобразить на плоскости без пересечений рёбер не по вершинам. 4 О большое описывает сложность кода с использованием алгебраических терминов. 5 Grand Theft Auto — серия мультиплатформенных компьютерных игр в жанре action-adventure, созданных и разрабатываемых главным образом британской компанией-разработчиком Rockstar North и выпускаемых компанией Rockstar Games. 6 САПР - система автоматизированного проектирования |