Волновой алгоритм
Волновой алгоритм, как и предыдущие, ищет путь между двумя заданными точками. Сначала, в стороны от исходной точки распространяется волна.
Начальное значение волны - ноль.
На первой итерации, начальное значение волны – 0. Граничащие с волной точки(в начале – одна начальная точка), получают значение волны + некоторый модификатор проходимости этой точки. Чем он больше - тем медленнее преодоление данного участка. Значение волны увеличивается на 1.
Далее на каждой итерации значение волны увеличивается на 1 и схожим образом обрабатываются все узлы графа, в которые можно перейти из уже обработанных, и которые ещё не затронуты волной. Цикл останавливается, когда будет обработан узел конца пути.
Наконец, по результатам обработки выводится кратчайший путь. Восстановить его можно следующим образом: среди связей конечной вершины найдем любую вершину с волновой меткой на 1 ниже метки конечной вершины, среди вершин, соседствующих с последней - веpшину с меткой на 2 ниже начальной, и т.д., пока не достигнем начальной вершины. Найденная последовательность вершин определяет один из кратчайших путей между двумя вершинами. Некоторые модификации волнового алгоритма предполагают сохранение информации о том, из какой вершины волна перешла в данную, что ускоряет генерацию пути, но занимает больше памяти.
Практика
Алгоритм реализован на языке Паскаль для двумерного массива, представляющего область поиска. Ниже следует общий вид алгоритма:
Program wave;
Uses Crt;
Const
Map : array [1..10, 1..10] of Byte =
(
(1, 1, 1, 1, 1, 1, 1, 1, 1, 1),
(1, 0, 0, 0, 0, 1, 0, 0, 1, 1),
(1, 0, 0, 1, 1, 1, 0, 0, 1, 1),
(1, 1, 0, 0, 0, 1, 0, 0, 1, 1),
(1, 0, 0, 0, 1, 1, 1, 0, 1, 1),
(1, 0, 1, 1, 1, 0, 0, 0, 0, 1),
(1, 0, 0, 1, 0, 0, 1, 0, 0, 1),
(1, 1, 0, 1, 0, 0, 1, 1, 0, 1),
(1, 1, 0, 0, 0, 0, 0, 0, 0, 1),
(1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
);
var
XS, YS, XE, YE : Byte;
X, Y, I : Byte;
MapM : array [1..10, 1..10] of Byte;
Moves : Byte;
MovesX : array [1..100] of Byte;
MovesY : array [1..100] of Byte;
Procedure Next(Var X, Y : Byte);
Begin
If (X <10) and (MapM[X, Y] - MapM[X + 1, Y] = 1) then
Begin
X := X + 1;
Exit;
End;
If (X >1) and (MapM[X, Y] - MapM[X - 1, Y] = 1) then
Begin
X := X - 1;
Exit;
End;
If (Y <10) and (MapM[X, Y] - MapM[X, Y + 1] = 1) then
Begin
Y := Y + 1;
Exit;
End;
If (Y >1) and (MapM[X, Y] - MapM[X, Y - 1] = 1) then
Begin
Y := Y - 1;
Exit;
End;
End;
Begin
ClrScr;
For Y := 1 to 10 do
Begin
For X := 1 to 10 do Write(Map[X, Y], ' ');
WriteLn;
End;
WriteLn('Vvedite X i Y nachala');
ReadLn(XS, YS);
WriteLn('Vvedite X i Y konsa puti: ');
ReadLn(XE, YE);
If (Map[XS, YS] = 1) or (Map[XE, YE] = 1) then
Begin
WriteLn('Koordinati vvedeni neverno');
ReadLn;
Halt;
End;
MapM[XS, YS] := 1;
I := 1;
Repeat
I := I + 1;
For Y := 1 to 10 do
For X := 1 to 10 do
If MapM[X, Y] = I - 1 then
Begin
If (Y <10) and (MapM[X, Y + 1] = 0)
and (Map[X, Y+1] = 0) Then MapM[X, Y+1] := I;
If (Y >1)
and (MapM[X, Y-1] = 0) and (Map[X, Y-1] = 0) Then MapM[X, Y-1] := I;
If (X <10)
and (MapM[X+1, Y] = 0) and (Map[X+1, Y] = 0) Then MapM[X+1, Y] := I;
If (X >1)
and (MapM[X-1, Y] = 0) and (Map[X-1, Y] = 0) Then MapM[X-1, Y] := I;
End;
If I = 100 then
Begin
WriteLn('Nevozmozhno dostich kontsa puti');
ReadLn;
Halt;
End;
Until MapM[XE, YE] >0;
Moves := I - 1;
X := XE;
Y := YE;
I := Moves;
Map[XE, YE] := 4;
Repeat
MovesX[I] := X;
MovesY[I] := Y;
Next(X, Y);
Map[X, Y] := 3;
I := I - 1;
Until (X = XS) and (Y = YS);
Map[XS, YS] := 2;
For I := 1 to Moves do
begin
WriteLn('(', MovesX[I],';', MovesY[I],')');
Map[MovesX[I],MovesY[I]]:=2
end;
WriteLn('Vsego: ', Moves, 'shagov');
WriteLn;
WriteLn('Grafik:');
For Y := 1 to 10 do
Begin
For X := 1 to 10 do Write(Map[X, Y], ' ');
WriteLn;
End;
WriteLn('2 - elementi puti.');
ReadLn;
End.
Теперь рассмотрим его поэтапно:
Program wave;
Uses Crt;
Const
Map : array [1..10, 1..10] of Byte =
(
(1, 1, 1, 1, 1, 1, 1, 1, 1, 1),
(1, 0, 0, 0, 0, 1, 0, 0, 1, 1),
(1, 0, 0, 1, 1, 1, 0, 0, 1, 1),
(1, 1, 0, 0, 0, 1, 0, 0, 1, 1),
(1, 0, 0, 0, 1, 1, 1, 0, 1, 1),
(1, 0, 1, 1, 1, 0, 0, 0, 0, 1),
(1, 0, 0, 1, 0, 0, 1, 0, 0, 1),
(1, 1, 0, 1, 0, 0, 1, 1, 0, 1),
(1, 1, 0, 0, 0, 0, 0, 0, 0, 1),
(1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
);
Таким образом будет выглядеть область поиска. Нули – проходимые элементы, единицы – непроходимые, реализация разных коэффициентов проходимости не вносит принципиальные различия в алгоритм, поэтому она не будет представлена на данном примере.
var
XS, YS, XE, YE : Byte;
X, Y, I : Byte;
MapM : array [1..10, 1..10] of Byte;
Moves : Byte;
MovesX : array [1..100] of Byte;
MovesY : array [1..100] of Byte;
Инициируем необходимые переменные. Весьма непривычный процесс после изящества Python2.7
Procedure Next(Var X, Y : Byte);
Begin
If (X <10) and (MapM[X, Y] - MapM[X + 1, Y] = 1) then
Begin
X := X + 1;
Exit;
End;
If (X >1) and (MapM[X, Y] - MapM[X - 1, Y] = 1) then
Begin
X := X - 1;
Exit;
End;
If (Y <10) and (MapM[X, Y] - MapM[X, Y + 1] = 1) then
Begin
Y := Y + 1;
Exit;
End;
If (Y >1) and (MapM[X, Y] - MapM[X, Y - 1] = 1) then
Begin
Y := Y - 1;
Exit;
End;
End;
Создаём функцию, которая будет регламентировать распространение «волны».
Begin
ClrScr;
For Y := 1 to 10 do
Begin
For X := 1 to 10 do Write(Map[X, Y], ' ');
WriteLn;
End;
Изобразим перед пользователем исходное состояние лабиринта.
WriteLn('Vvedite X i Y nachala');
ReadLn(XS, YS);
WriteLn('Vvedite X i Y konsa puti: ');
ReadLn(XE, YE);
If (Map[XS, YS] = 1) or (Map[XE, YE] = 1) then
Begin
WriteLn('Koordinati vvedeni neverno');
ReadLn;
Halt;
End;
Попросим пользователя ввести координаты начала и конца пути, проверим их допустимость.
MapM[XS, YS] := 1;
I := 1;
Repeat
I := I + 1;
For Y := 1 to 10 do
For X := 1 to 10 do
If MapM[X, Y] = I - 1 then
Begin
If (Y <10) and (MapM[X, Y + 1] = 0)
and (Map[X, Y+1] = 0) Then MapM[X, Y+1] := I;
If (Y >1)
and (MapM[X, Y-1] = 0) and (Map[X, Y-1] = 0) Then MapM[X, Y-1] := I;
If (X <10)
and (MapM[X+1, Y] = 0) and (Map[X+1, Y] = 0) Then MapM[X+1, Y] := I;
If (X >1)
and (MapM[X-1, Y] = 0) and (Map[X-1, Y] = 0) Then MapM[X-1, Y] := I;
End;
Распространяем «волну» по области поиска согласно концепции алгоритма. На каждом шаге цикла увеличиваем значение волны на 1.
If I = 100 then
Begin
WriteLn('Nevozmozhno dostich kontsa puti');
ReadLn;
Halt;
End;
Поскольку лабиринт имеет размеры 10*10, достижение волной значения 100 до нахождения точки конца пути можно считать признаком неудачи поиска. В этом случае выводим пользователю информацию о том, что путь найден не был.
Until MapM[XE, YE] >0;
Moves := I - 1;
X := XE;
Y := YE;
I := Moves;
Map[XE, YE] := 4;
Repeat
MovesX[I] := X;
MovesY[I] := Y;
Next(X, Y);
Map[X, Y] := 3;
I := I - 1;
Until (X = XS) and (Y = YS);
Map[XS, YS] := 2;
В противном случае алгоритм достигнет точки конца пути, а значит, путь существует. Генерируем искомый путь по обработанным точкам.
For I := 1 to Moves do
begin
WriteLn('(', MovesX[I],';', MovesY[I],')');
Map[MovesX[I],MovesY[I]]:=2
end;
WriteLn('Vsego: ', Moves, 'shagov');
WriteLn;
Выводим пользователю полученную информацию в виде последовательности координат точек в составе искомого пути и общего числа шагов в его составе. Отмечаем точки пути на области поиска.
WriteLn('Grafik:');
For Y := 1 to 10 do
Begin
For X := 1 to 10 do Write(Map[X, Y], ' ');
WriteLn;
End;
WriteLn('2 - elementi puti.');
ReadLn;
End.
Для наглядности выводим результат графически – в виде цифр «2» от точки начала пути до его окончания. Конец алгоритма.
Использование алгоритма:
