Алгоритм Ли

Материал из свободной русской энциклопедии «Традиция»
Перейти к: навигация, поиск

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

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

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

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

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

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

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

Маршрутный алгоритм[править]

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

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

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

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

Работа этого алгоритма начинается с начального элемента. Возле него рассматривается окрестность с восемью элементами. От каждого из них до конечного элемента оценивается длина пути. Расстояние между точками можно вычислить по следующей формуле: 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>
  • Frank Rubin «The Lee path connection algorithm» // IEEE Transactions on Computers. — 1974.

Ссылки[править]