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

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

---

Чтобы увидеть работу алгоритма - кликните левой кнопкой мышки в клетку, куда вы хотите проложить кратчайший путь. Меняйте размеры поля, включите показ волны. Жмите кнопку "Заново", чтобы сформировать новый лабиринт.

Поле: x волна

обновите браузер
обновите браузер

Статистика поиска: