Описание алгоритма

Алгоритм Ли

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

Волновой алгоритм в контексте поиска пути в лабиринте был формально предложен Э. Ф. Муром. Ли независимо открыл тот же алгоритм в контексте трассировки печатных плат в 1961 году.

Описание алгоритма

Алгоритм волновой трассировки работает на дискретном рабочем поле (ДРП), представляющем собой прямоугольник, разбитый на квадратные ячейки одинакового размера. Ячейки ДРП подразделяются на «проходимые» (свободные), «непроходимые» (препятствия), стартовые (источники) и финишные (приемники). Цель алгоритма — проложить кратчайший путь от старта к финишу, если это возможно, либо сообщить об отсутствии пути.

Алгоритм включает в себя три этапа: инициализацию, распространение волны и восстановление пути.

Во время инициализации волна пополняется всеми стартовыми ячейками рабочего поля.

При распространении волна, идущая от источника к приемнику, на каждом шаге пополняется свободными ячейками ДРП, которые, во-первых, еще не принадлежат волне, и, во-вторых, являются соседями ячеек, попавших в волну на предыдущем шаге.

Восстановление пути происходит в обратном направлении: при движении от финишной к стартовой ячейке каждый раз выбирается ячейка, помеченная числом на единицу меньше.