Алгоритм Ли

Алгоритм Ли

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

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

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

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

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

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

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

Содержание

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

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

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

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

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

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

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

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

Когда f = 0, строится прямолинейная трасса; когда f = const, строится параболическая трасса. Ордината следующего элемента трассы рассчитывается по рекуррентной формуле, а абсцисса рассчитывается по формуле: C = An = An-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.

Ссылки


Wikimedia Foundation. 2010.

Нужно сочинение?

Полезное


Смотреть что такое "Алгоритм Ли" в других словарях:

  • АЛГОРИТМ —         [от algorithm!; algorismus, первоначально лат. транслитерация имени ср. азиат. учёного 9 в. Хорезми (Мухаммед бен Муса аль Хорезми)], программа, определяющая способ поведения (вычисления); система правил (предписаний) для эффективного… …   Философская энциклопедия

  • алгоритм — Конечный набор предписаний для получения решения задачи посредством конечного количества операций. [ГОСТ 34.003 90] алгоритм Конечное упорядоченное множество точно определенных правил для решения конкретной задачи. [ИСО/МЭК 2382 1] [ГОСТ Р 52292… …   Справочник технического переводчика

  • алгоритм — предписание, задающее на базе системы правил последовательность операций, точное выполнение коих позволяет решать задачи определенного класса. Понятие, ключевое для математики и логики математической. В психологии применяется не в строгом… …   Большая психологическая энциклопедия

  • АЛГОРИТМ — [лат. algorithmus < арабск. Algorithmi имя собств.] 1) мат. однозначно определенная процедура для схематического решения класса задач; 2) инф. понятное и точное предписание исполнителю совершить последовательность действий, направленных на… …   Словарь иностранных слов русского языка

  • алгоритм — алгорифм Словарь русских синонимов. алгоритм сущ., кол во синонимов: 3 • алгорифм (1) • …   Словарь синонимов

  • алгоритм — а, м. algorithme m. 1230 algorisme. Лексис.1. В математике общепонятное предписание, определяющее детерминированный вычислительный процесс, ведущий от исходных данных к искомому результату. БАС 2. Алгебра логика математики; алгоритм ее… …   Исторический словарь галлицизмов русского языка

  • Алгоритм — (algorithm) Последовательность четко определенных действий для решения проблемы, выраженная в конечном числе шагов. Алгоритмы широко применяются в компьютерной области. Шаги алгоритма переводятся в последовательность команд, понимаемых… …   Словарь бизнес-терминов

  • АЛГОРИТМ — (алгорифм) (от algorithmi, algorismus, первоначально латинская транслитерация имени математика аль Хорезми), способ (программа) решения вычислительных и других задач, точно предписывающий, как и в какой последовательности получить результат,… …   Современная энциклопедия

  • АЛГОРИТМ — (алгорифм) (от algorithmi algorismus, первоначально лат. транслитерация имени математика аль Хорезми), способ (программа) решения вычислительных и др. задач, точно предписывающий, как и в какой последовательности получить результат, однозначно… …   Большой Энциклопедический словарь

  • АЛГОРИТМ — (от лат. формы имени среднеазиатского математика аль Хорезми) правило действий, последовательность проведения вычислительных операций, способ нахождения искомого результата. В экономических задачах, решаемых с использованием математических… …   Экономический словарь

Книги

Другие книги по запросу «Алгоритм Ли» >>


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»