Реферат: Волновой алгоритм (Алгоритм Ли)

Волновой алгоритм (Алгоритм Ли)

Волновой алгоритм является одним из самых уникальных алгоритмов трассировки. Он позволяет построить трассу (путь) между двумя элементами в любом лабиринте .

Р

ис 1.

Из начального элемента распространяется в 4-х направлениях волна (рис 1.). Элемент, в который пришла волна, образует фронт волны. На рисунках цифрами обозначены номера фронтов волны.

Рис 2.

Каждый элемент первого фронта волны является источником вторичной волны (рис 2.). Элементы второго фронта волны генерируют волну третьего фронта и т.д. Процесс продолжается до тех пор, пока не будет достигнут конечный элемент.

На втором этапе строится сама трасса. Её построение осуществляется в соответствии со следующими правилами:

Движение при построении трассы осуществляется в соответствии с выбранными приоритетами.

При движении от конечного элемента к начальному, номер фронта волны (путевые координаты) должны уменьшатся.

Приоритеты направления движения выбираются на стадии разработки. В зависимости от того какими задаются эти приоритеты получаются разные трассы, НО длина трассы в любом случае остается одной и той же.

Преимущества волнового алгоритма в том, что с его помощью можно найти трассу в любом лабиринте и с любым количеством запретных элементов (стен). Единственным недостатком этого алгоритма является, то, что при построении трассы требуется большой объем памяти.



^ Пример использования ВОЛНОВОГО АЛГОРИТМА :



Красным цветом отмечены запрещенные элементы. Серым цветом трасса после действия алгоритма.
А - начальная точка, В - конечная.
Приоритеты движения ВЛЕВО, ВПРАВО, ВВЕРХ, ВНИЗ.

Построение трассы ведется от начальной точки к конечной. Приоритетные направления показаны зелеными стрелками.
Реализация на Паскале Program Voln; Uses Crt; Var XS, YS, XE, YE : Byte; X, Y, I,n,m : Byte; Map : array [1..10, 1..10] of Byte; {Исходная матрица} MapM : array [1..10, 1..10] of Byte; {Матрица покрытий} Moves : Byte; Procedure Next(Var X, Y : Byte); Begin If (X 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 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; writeln('n, m'); readln(n,m); For Y := 1 to n do Begin For X := 1 to m do read(Map[X, Y]); End; WriteLn('Please enter X and Y of the start: '); ReadLn(XS, YS); WriteLn('Please enter X and Y of the end: '); ReadLn(XE, YE); If (Map[XS, YS] = 1) or (Map[XE, YE] = 1) then Begin WriteLn('Error!!!'); ReadLn; Halt; End; MapM[XS, YS] := 1; I := 1; Repeat I := I + 1; For Y := 1 to n do For X := 1 to m do If MapM[X, Y] = I - 1 then Begin If (Y 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 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 = n*m then Begin WriteLn('You can''t go there!!!'); ReadLn; Halt; End; Until MapM[XE, YE] >0; Moves := I - 1; X := XE; Y := YE; I := Moves; Repeat Next(X, Y); I := I - 1; Until (X = XS) and (Y = YS); writeln ('Количество шагов',moves); for y:=1 to n do begin for x:=1 to m do write(MapM[x,y],' '); writeln; end; End.