Перейти к содержанию

Реализации алгоритмов/Алгоритм Ли

Материал из Викиучебника — открытых книг для открытого мира

Алгори́тм волново́й трассиро́вки (волновой алгоритм, алгоритм Ли) — алгоритм поиска пути, алгоритм поиска кратчайшего пути на планарном графе. Принадлежит к алгоритмам, основанным на методах поиска в ширину.

В приведённом примере производится поиск ортогонального пути (считаются 4 соседа клетки). Перед вызовом функции lee() массив grid должен быть заполнен значениями WALL (непроходимая ячейка) и BLANK (проходимая непомеченная ячейка). Если функция lee() возвращает результат true, то в массивах px и py остаются координаты ячеек пути в порядке от стартовой (px[0], py[0]) до финишной (px[len], py[len]).

const int W      = 12;         // ширина рабочего поля
const int H      =  8;         // высота рабочего поля
const int WALL   = -1;         // непроходимая ячейка
const int BLANK  = -2;         // свободная непомеченная ячейка

int px[W * H], py[W * H];      // координаты ячеек, входящих  путь
int len;                       // длина пути
int grid[H][W];                // рабочее поле

// Перед вызовом lee() массив grid заполнен значениями WALL и BLANK

bool lee(int ax, int ay, int bx, int by)   // поиск пути из ячейки (ax, ay) в ячейку (bx, by)
{
  int dx[4] = {1, 0, -1, 0};   // смещения, соответствующие соседям ячейки
  int dy[4] = {0, 1, 0, -1};   // справа, снизу, слева и сверху
  int d, x, y, k;
  bool stop;

  if (grid[ay][ax] == WALL || grid[by][bx] == WALL) return false;  // ячейка (ax, ay) или (bx, by) - стена

  // распространение волны
  d = 0;
  grid[ay][ax] = 0;            // стартовая ячейка помечена 0
  do {
    stop = true;               // предполагаем, что все свободные клетки уже помечены
    for ( y = 0; y < H; ++y )
      for ( x = 0; x < W; ++x )
        if ( grid[y][x] == d )                         // ячейка (x, y) помечена числом d
        {
          for ( k = 0; k < 4; ++k )                    // проходим по всем непомеченным соседям
          {
             int iy=y + dy[k], ix = x + dx[k];
             if ( iy >= 0 && iy < H && ix >= 0 && ix < W &&
                  grid[iy][ix] == BLANK )
             {
                stop = false;              // найдены непомеченные клетки
                grid[iy][ix] = d + 1;      // распространяем волну
             }
          }
        }
    d++;
  } while ( !stop && grid[by][bx] == BLANK );

  if (grid[by][bx] == BLANK) return false;  // путь не найден

  // восстановление пути
  len = grid[by][bx];            // длина кратчайшего пути из (ax, ay) в (bx, by)
  x = bx;
  y = by;
  d = len;
  while ( d > 0 )
  {
    px[d] = x;
    py[d] = y;                   // записываем ячейку (x, y) в путь
    d--;
    for (k = 0; k < 4; ++k)
    {
       int iy=y + dy[k], ix = x + dx[k];
       if ( iy >= 0 && iy < H && ix >= 0 && ix < W &&
            grid[iy][ix] == d)
      {
          x = x + dx[k];
          y = y + dy[k];           // переходим в ячейку, которая на 1 ближе к старту
          break;
      }
    }
  }
  px[0] = ax;
  py[0] = ay;                    // теперь px[0..len] и py[0..len] - координаты ячеек пути
  return true;
}



lee(3, 6, 3, 0);                 // поиск пути из ячейки (3,6) в ячейку (3, 0) (см. рис.)

Данные приводятся в виде (c новой строки)
Размера массива «n m»
Двумерного массива из «@» и " "
Стартовой ячейки «x y»
Финальной ячейки «x y»
На выходе мы получим последовательные координаты в виде «{x, y} {x, y} {x, y} .. {x, y}»

type o=record
      dx,dy:integer; {Для лучшего хранения нужны ячеек}
     end;
var a:array[1..128,1..128] of integer; {Основной массив (можно заменять на нужный размер}
    b,c:array[0..1000] of o; {Массив для ячеек, которые нужно будет пометь как d+1 и потом заменить эти ячейки на ячейки d+1}
    n,m,l,t,u,d,s:integer;
    finalx,finaly,startx,starty:integer; {стартовая и финальная}
    k:char;
procedure read; {Чтения из файла. Стена тут должна быть '@', а пустое место, соответственно, ' '}
 var i,j:integer;
 begin
 readln(n,m);
 for i:=1 to n do 
   begin  
   for j:=1 to m do    
     begin     
     read(k);    
     if k='@' then a[i,j]:=-1 else a[i,j]:=0;   {В массиве это будет -1 и 0 (стена и пустое место)}
     end;  
     readln; 
   end;
 readln(startx,starty); readln(finalx,finaly);
 end;
procedure check(i,j:integer);  {проверка на соседние ячейки, которые можно пометить, как d+1 для каждой ячейки из массива b}
 begin
  if (i>1) and (a[i-1,j]=0) then 
    begin
    a[i-1,j]:=d;
    inc(l);
    c[l].dx:=i-1;
    c[l].dy:=j;
    end;
  if (j>1) and (a[i,j-1]=0) then 
    begin
    a[i,j-1]:=d;
    inc(l);
    c[l].dx:=i;
    c[l].dy:=j-1;
    end;
    if (i<n) and (a[i+1,j]=0) then 
    begin
    a[i+1,j]:=d;
    inc(l);
    c[l].dx:=i+1;
    c[l].dy:=j;
    end;
     if (j<m) and (a[i,j+1]=0) then 
    begin
    a[i,j+1]:=d;
    inc(l);
    c[l].dx:=i;
    c[l].dy:=j+1;
    end;
  end;
procedure findway(i,j:integer);  {Поиск финального пути. Идет назад по массиву к стартовой ячейке и записывает ячейку в массив b (уже финальный путь)}
 begin
 s:=0;
 a[startx,starty]:=0;
  repeat
   dec(d);
   if (i>1) and (a[i-1,j]=d) then begin dec(i); inc(s); b[s].dx:=i; b[s].dy:=j; end
   else
   if (i<n) and (a[i+1,j]=d) then begin inc(i); inc(s); b[s].dx:=i; b[s].dy:=j; end
   else
   if (j>1) and (a[i,j-1]=d) then begin dec(j); inc(s); b[s].dx:=i; b[s].dy:=j; end
   else
   if (j<m) and (a[i,j+1]=d) then begin inc(j); inc(s); b[s].dx:=i; b[s].dy:=j; end
   else break;
  until (i=startx) and (j=starty);
end;
BEGIN
  assign(input, 'input.txt'); reset(input); 
  assign(output, 'output.txt'); rewrite(output); 
{---------} read;
b[1].dx:=startx; b[1].dy:=starty;
a[startx,starty]:=-2;
u:=1; d:=0;
repeat
 inc(d);
 l:=0;
 for t:=1 to u do
  begin
  check(b[t].dx,b[t].dy);
  end;
  if l=0 then begin write('NO EXIT'); exit; end; {В массив b не добавилась ни одна новая ячейка - путь не найден}
  for s:=1 to l do b[s]:=c[s]; {перевод из вспомогательного массива в основной для начала цикла по новому}
  u:=l;
until a[finalx,finaly]<>0;
{----------} findway(finalx,finaly);
for d:=s downto 1 do write( '{ ',b[d].dx, ',',b[d].dy,' }  ');
end.

Ссылки

[править]