Волновой алгоритм или кратчайший путь между двумя точками

Кратко о волновом алгоритмеВолновой алгоритм по шагамРезультат работыСкачать исходник
Приветствую Вас, дорогие читатели! Сегодня мы рассмотрим принцип работы и реализацию волнового алгоритма. Сначала я думаю, стоит сказать пару слов о сути волнового алгоритма (алгоритма ли) ну и о его применение.

кратчайший путь, трассировка пути

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

У нас имеется игровое поле(массив размерностью MxN). Каждая клетка нашего игрового поля может быть либо проходимой, либо непроходимой. Также имеется две точки A и B. А –стартовая точка, В – конечная точка. Необходимо попасть из точки A в точку B за наименьшее количество шагов, если это возможно. Условимся, что перемещаться можно только в 4 направлениях (вверх, вниз, влево, вправо).
Теперь перейдем к пошаговому алгоритму решения данного задания.

1. Нам нужно два массива одинаковой размерности MxN. Первый массив содержит игровое поле, в котором указаны свойства всех клеток поля (проходимы они или нет). Второй массив(рабочий), над которым будут производиться в дальнейшем различные манипуляции. В самом начале он содержит те же данные, что и массив с игровым полем. Давайте условимся, что: если точка является проходимой, то  элемент массива  будет содержать число равное MxN+1; если точка непроходима, то MxN+2; если это стартовая точка, то MxN; если конечная точка, то 0. Для наглядности того, что я здесь пишу к каждому шагу я буду прилагать код на с++:

2. Инициализируем переменную iter=0 отвечающую за количество итераций. Этот этап обычно называют этапом распространения волны. Здесь главное запомнить что этап распространения волны начинается с конечной точки.

3.Теперь определяем константную переменную iterk равную максимальному числу итераций. Эта переменная необходима, чтобы наша программа не зациклилась. Например, если между начальной и конечной точкой лежит препятствие, которое невозможно преодолеть. Также эта переменная не должна быть больше размера начальной точки(в нашем случае 49).

4.Тепрь мы должны создать цикл с предусловием (iter<iterk) Внутри него расположить два вложенных друг в друга цикла для построчного просмотра нашего массива. Внутри них определить условие, что если элемент рабочего массива равен количеству итераций, то просматриваются соседние элементы  RAB(i+1,j), RAB(i-1,j), RAB(i,j+1), RAB(i,j-1) по следующему правилу(рассмотрим данное правило на примере   RAB(i-1,j)): 1) Если RAB(i-1,j)==50 , то есть точка является проходимой то RAB(i-1,j)=iter+1 2)Если RAB(i-1,j)==49, то выходим из данного, так как мы дошли до начальной точки. Аналогично и с другими элемента то есть у вас должно получиться в общей сумме 8 условий. После того, как мы покидаем построчный просмотр массива мы должны увеличить количество итераций на 1

5. Если iter>iterk, то нахождений кратчайшего пути невозможно, следовательно, волновой алгоритм не выполняется для введенных точек и нужно покинуть программу, ну и в следующий раз указать уже другие точки. 6. Теперь мы переходим к построению пути перемещения. Инициализируем четыре переменные X и Y соответствующие координатам стартовой точки и X1 и Y1 координаты перемещения. Также определяем переменную min==51(дальше вы поймете для чего она).

7. Далее в цикле просматриваем окрестность(RAB[X+1][Y], RAB[X-1][Y], RAB[X][Y+1], RAB[X][Y-1]) стартовой точки RAB[X][Y] и ищем элемент с наименьшим значением. Как только мы его находим, то присваиваем его координаты переменным X1 и Y1. Условием выхода из цикла и следовательно завершением нахождения кратчайшего пути   является нахождение конечной точки (RAB[X1][Y1]==0).
волновой алгоритм, волновой алгоритм скачать, исходник волнового алгоритма
8. Ну а теперь давайте взглянем на кратчайший путь, который проложил нам волновой алгоритм:

В итоге мы получим следующее: трассировка ли, волновой алгоритм, алгоритм ли

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



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

Ваш e-mail не будет опубликован. Обязательные поля помечены *