Алгоритм Ли

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

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

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

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

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

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

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

Маршрутный алгоритм

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

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

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

Маршрутный алгоритм, основанный на вычислении расстояния между точками

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

Маршрутный алгоритм, основанный на рекуррентном соотношении

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

Когда f = 0, строится прямолинейная трасса; когда f = const, строится параболическая трасса. Ордината следующего элемента трассы рассчитывается по рекуррентной формуле, а абсцисса рассчитывается по формуле: C = A_n = A_n-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
• Frank Rubin The Lee path connection algorithm // IEEE Transactions on Computers. — 1974.

Ссылки

• Поиск пути на карте (Алгоритм Ли), delphisite.ru  (Проверено 14 октября 2009)
• http://www.ece.northwestern.edu/~haizhou/357/lec6.pdf
• http://www.firststeps.ru/theory/karta.html