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

Вид материала

Документы

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

Подобный материал:

• Тезисы к докладу «Вейвлетное (wavelet) сжатие. Jpeg2000», 11.1kb.
• Тест Томаса Килмана, матрица стратегий поведения в конфликте, алгоритм, 116.81kb.
• Алгоритм и программа. Алгоритм и программа. Что такое программа? Что такое алгоритм?, 314.91kb.
• Комплекс алгоритмов Алгоритм главного модуля Алгоритм прорисовки объекта, 102.47kb.
• Вопросы к экзамену Задача линейного программирования и её графическое решение, 9.5kb.
• Алгоритм и его свойства, 410.3kb.
• Словник термінів з інформатики Алгоритм, 72.66kb.
• Урок Тема "Алгоритмы ветвления", 17.24kb.
• Комплекс алгоритмов Алгоритм главного модуля Алгоритм прорисовки объекта, 93.42kb.
• Алгоритм, 6483.28kb.

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

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

Р ис 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.