Волновой алгоритм
Скачать 26.04 Kb.
|
|
Волновой алгоритм. Нахождение пути в лабиринте Роман Иванов @ 13:05 06.12.2009 Волновой алгоритм — это алгоритм, который позволяет найти минимальный путь в графе. Алгоритм поиска в ширину лежит в основе этого метода. В основном волновой алгоритм применяется для нахождения самого кратчайшего пути в графе, в общем случае находит лишь его длину. Волновой алгоритм можно назвать одним из самых уникальных алгоритмов трассировки. Волновой алгоритм позволяет сформировать путь (трассу) между двумя ключевыми точками (элементами) в любом лабиринте, здесь необходимо отметить тот факт, что задача является разрешимой. Исходные данные, цели и задачи, которые требуются для работы волнового алгоритма можно кратко сформулировать следующим образом: Волновой алгоритм решает задачу нахождения (поиска) пути на плоской двумерной клетчатой карте. Каждой клетке карты присваивается одно из двух состояний "пустая" и "препятствие", также выбираются клетки "начала" и "конца" пути. Цель волнового алгоритма (как и большинства других алгоритмов) - это задача прокладывания или нахождения пути на карте между начальной, конечной точкой (клеткой). Волновой алгоритм работает с конца, т.е. из конечной клетки во все направления распространяется волна шагом в одну клетку по радиусу. Далее волна распространяется из соседних клеток и т.д., словно цепная реакция. Этот процесс длится, пока не будет достигнута клетка начала пути или не будут заполнены все поля, т.е. задача не разрешима. Волна движется только по пустым клеткам. Как работает волновой алгоритм? Основная идея волнового алгоритма описывается следующими этапами: 1. Из начального положения (элемента) волна распространяется в 4-х направлениях (рис. 1). Элемент, в который пришла волна, создает новый фронт волны. На рисунках цифрами обозначены номера фронтов волны. 
Рис. 1 Первый шаг Каждый из элементов первого фронта волны будет является источником вторичной волны (рис 2.). Элементы второго фронта волны будут генерировать волну третьего фронта и т.д. Процесс формирования волн продолжается, пока не буде достигнут конечный элемент. 
Рис. 2 Последующее распространение волны 2. На втором этапе волнового алгоритма строится сама трасса. Ее построение необходимо осуществлять в соответствии со следующими правилами: a) Движение при построении трассы необходимо осуществлять в соответствии с выбранными приоритетами. b) При движении от конечного элемента к начальному номер фронта волны (путевые координаты) должны уменьшатся. 
Рис. 3 Результат действия Приоритеты направления движения при использовании волнового алгоритма нахождения пути выбираются на стадии разработки. Если изменять эти приоритеты, то можно получить разные трассы, НО длина трассы в любом случае остается одной и той же. Преимущества волнового алгоритма в том, что с его помощью можно найти трассу в любом лабиринте и с любым количеством запретных элементов (стен). Единственным недостатком волнового алгоритма является, то, что при построении трассы требуется большой объем памяти. Кратко суть алгоритма На двумерной клетчатой карте (матрице), состоящей из «проходимых» и «непроходимых» клеток, обозначена клетка старта и клетка финиша. Цель алгоритма — проложить кратчайший путь от клетки старта к клетке финиша, если это, конечно, возможно. От старта во все направления распространяется волна, причем каждая пройденная волной клетка помечается как «пройденная». Волна, в свою очередь, не может проходить через клетки, помеченные как «пройденные» или «непроходимые». Волна движется, пока не достигнет точки финиша или пока не останется непройденных клеток. Если волна прошла все доступные клетки, но так и не достигла клетки финиша, значит, путь от старта до финиша проложить невозможно. После достижения волной финиша, от финиша прокладывается путь до старта и сохраняется в массиве. Скачать 26.04 Kb. Поделитесь с Вашими друзьями:
|