Алгоритм Ли, волновой алгоритм поиска пути на карте, алгоритм трассировки. С его помощью можно построить путь, или трассу, между двумя любыми элементами в лабиринте. Из начального элемента распространяется в четырёх направлениях волна. Тот элемент, в который она пришла, образует фронт волны.

Элементы первого фронта волны являются источниками вторичных волн.

Элементы второго фронта генерируют волну третьего фронта и так далее. Процесс заканчивается тогда, когда достигается конечный элемент. На втором этапе строится трасса. Построение производится в соответствии с некоторыми правилами:

• при построении трассы движение проходит в зависимости от выбранных приоритетов,

• путевые координаты уменьшаются при переходе от начального элемента к конечному.

Эти приоритеты выбираются в процессе разработки. В зависимости от выбора тех или иных приоритетов получаются различные трассы. Но в любом случае длина трассы остается одной и той же.

Используя волновой алгоритм, можно найти трассу в лабиринте с любым количеством стен. В этом и заключается преимущество его использования.

Недостаток А.Л. заключается в том, что при построении трассы требуется большой объем памяти.

Маршрутный алгоритм подразделяется на следующие алгоритмы:

• основанные на вычислении расстояния между точками;

• основанные на рекуррентном соотношении.

Данный алгоритм осуществляет формирование фронта и прокладывание трассы одновременно. Источником волны на каждом шаге является конечный элемент участка трассы, проложенной ранее.

Работа этого алгоритма начинается с начального элемента. Возле него рассматривается окрестность с восемью элементами. От каждого из них до конечного элемента оценивается длина пути. Расстояние между точками можно вычислить по следующей формуле: C=|Ai-AD|+|Bi-BD|, где (Ai, Bi) — координаты точки окрестности, (AD, BD)- координаты последнего элемента. Из всех найденных значений выбирается наименьшее. В качестве элемента трассы здесь выбирается элемент, расстояние от которого оказалось минимальным. Вокруг этого элемента опять рассматривается окрестность с восемью элементами. Процесс заканчивается, если пришли к конечному элементу. При условии возникновения на пути препятствия в виде запрещенного элемента, обход препятствия производится по усмотрению создателя. При этом задаются направления обхода препятствия.

Маршрутный алгоритм можно также построить на основе следующего рекуррентного соотношения: у(х) = 2у(х + g) + у(х + 2g) + f, где х, у(х) — абсцисса и ордината элемента занимаемого трассой на данном шаге, (х + g) — ордината элемента занимаемого трассой на предыдущем шаге, (х + 2g) — ордината элемента отстоящего от вычисляемого на 2 шага, g — величина изменения абсциссы на каждом шаге, f — это функция определяющая вид трассы.

Когда f=0, строится прямолинейная трасса; когда f=const, строится параболическая трасса. Ордината следующего элемента трассы рассчитывается по рекуррентной формуле, а абсцисса рассчитывается по формуле: C=Aп=Aп-1+g. Знак «+» или «-» в рекуррентной формуле выбирается в зависимости от того, от какого элемента начинается построение трассы (от начального или от конечного). Например, для того чтобы найти 3-й элемент трассы по этой формуле, необходимо указать два предыдущих. Первым является элемент X(AX,BX). Ордината второго вычисляется по формуле: B(A)=B(AX)+ ((B(AX)-B(AY))/(AX-AY))*g. Если на пути встречается запрещенный элемент, то его обход так же, как и в алгоритме, основанном на вычислении расстояния между точками, осуществляется по усмотрению разработчика.

Главное достоинство данного алгоритма — простота, а также возможность движения по диагонали.

Лит.: Lee, C.Y., «An Algorithm for Path Connections and Its Applications», IRE Transactions on Electronic Computers, vol. EC-10, number 2, pp. 364—365, 1961 Wai-Kai Chen The circuits and filters handbook — 2. — 2003. — 2961 с. — ISBN 0849309123.