Реализация волнового алгоритма

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

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

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

// 0 – конечная точка
 
// 51 – непроходимая точка
 
// 50 – проходимая точка
 
// 49 –начальная точка
 
// инициализируем массив с игровым полем
 
int M=7;
 
int N=7;
 
int POLE[M][N]={
 
       51, 51, 51, 51, 51, 51, 51,
 
       51, 49, 50, 50, 50, 51, 51,
 
       51, 50, 50, 51, 50, 50, 51,
 
       51, 51, 50, 50, 50, 0,  51,
 
       51, 50, 50, 50, 51, 50, 51,
 
       51, 50, 51, 50, 50, 50, 51,
 
       51, 51, 51, 51, 51, 51, 51,
 
       };
 
// инициализируем рабочий массив
 
int RAB[M][N]={
 
       51, 51, 51, 51, 51, 51, 51,
 
       51, 49, 50, 50, 50, 51, 51,
 
       51, 50, 50, 51, 50, 50, 51,
 
       51, 51, 50, 50, 50, 0,  51,
 
       51, 50, 50, 50, 51, 50, 51,
 
       51, 50, 51, 50, 50, 50, 51,
 
       51, 51, 51, 51, 51, 51, 51,
 
       };

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


1 int iter(0);

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


1 int 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(дальше вы поймете для чего она).


1 int X(1),Y(1),X1(0),Y1(0);
2
3 int min(51);
Волновой алгоритм пример c плюс

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. Ну а теперь давайте взглянем на кратчайший путь, который проложил нам волновой алгоритм:

for(int i=0;i<M;i++)
 
{
 
for(int j=0;j<N;j++)
 
{
 
switch(POLE[i][j]){
 
case 51:
 
{cout<<setw(3)<<'#';
 
break;}
 
case 50:
 
{cout<<setw(3)<<'.';
 
break;}
 
case 49:{cout<<setw(3)<<'A';
 
break;}
 
case 0:{cout<<setw(3)<<'B';
 
break;}
 
case -1:{cout<<setw(3)<<'>';
 
break;}
 
}
 
}
 
cout<<endl;
 
}

В итоге мы получим следующее: 

Результат работы программы

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


Помогая проекту BEST-EXAM, вы делаете образование более доступным для каждого человека, внесите и вы свой вклад -
поделитесь этой статьей в социальных сетях!

Читайте также:

Добавить комментарий

Ваш e-mail не будет опубликован.

стрелка вверх best-exam