Кодинг
★ Рубрика: Кодинг

Волновой алгоритм Ли на JavaScript

Алгори́тм волново́й трассиро́вки (волновой алгоритм, алгоритм Ли) — алгоритм поиска пути, алгоритм поиска кратчайшего пути на планарном графе. Принадлежит к алгоритмам, основанным на методах поиска в ширину. В основном используется при компьютерной трассировке (разводке) печатных плат, соединительных проводников на поверхности микросхем. Другое применение волнового алгоритма — поиск кратчайшего расстояния на карте в компьютерных стратегических играх. Волновой алгоритм в контексте поиска пути в лабиринте был предложен Э. Ф. Муром. Ли независимо открыл этот же алгоритм при формализации алгоритмов трассировки печатных плат в 1961 году.
Чтобы увидеть работу алгоритма - кликните левой кнопкой мышки в клетку, куда вы хотите проложить кратчайший путь. Меняйте размеры поля, включите показ волны. Жмите кнопку "Заново", чтобы сформировать новый лабиринт.

Поле: x волна
обновите браузер
обновите браузер
Статистика поиска:

 Похожие публикации: Алгоритмы, Javascript

Войдите, чтобы добавить Ваш ответ. [ Регистрация | Вход ]