Алгори́тм волново́й трассиро́вки (волновой алгоритм, алгоритм Ли) — алгоритм поиска пути, алгоритм поиска кратчайшего пути на планарном графе. Принадлежит к алгоритмам, основанным на методах поиска в ширину.
В основном используется при компьютерной трассировке (разводке) печатных плат, соединительных проводников на поверхности микросхем. Другое применение волнового алгоритма — поиск кратчайшего расстояния на карте в компьютерных стратегических играх.
Волновой алгоритм в контексте поиска пути в лабиринте был предложен Э. Ф. Муром[2]. Ли независимо открыл этот же алгоритм при формализации алгоритмов трассировки печатных плат в 1961 году[3][4][5].
Описание алгоритма
Алгоритм работает на дискретном рабочем поле (ДРП), представляющем собой ограниченную замкнутой линией фигуру, не обязательно прямоугольную, разбитую на прямоугольные ячейки, в частном случае — квадратные. Множество всех ячеек ДРП разбивается на подмножества: «проходимые» (свободные), т. е при поиске пути их можно проходить, «непроходимые» (препятствия), путь через эту ячейку запрещён, стартовая ячейка (источник) и финишная (приемник). Назначение стартовой и финишной ячеек условно, достаточно — указание пары ячеек, между которыми нужно найти кратчайший путь.
Алгоритм предназначен для поиска кратчайшего пути от стартовой ячейки к конечной ячейке, если это возможно, либо, при отсутствии пути, выдать сообщение о непроходимости[6].
Работа алгоритма включает в себя три этапа: инициализацию, распространение волны и восстановление пути.
Во время инициализации строится образ множества ячеек обрабатываемого поля, каждой ячейке приписываются атрибуты проходимости/непроходимости, запоминаются стартовая и финишная ячейки.
Далее, от стартовой ячейки порождается шаг в соседнюю ячейку, при этом проверяется, проходима ли она, и не принадлежит ли ранее меченной в пути ячейке.
Соседние ячейки принято классифицировать двояко: в смысле окрестности Мура и окрестности фон Неймана, отличающийся тем, что в окрестности фон Неймана соседними ячейками считаются только 4 ячейки по вертикали и горизонтали, в окрестности Мура — все 8 ячеек, включая диагональные.
При выполнении условий проходимости и непринадлежности её к ранее помеченным в пути ячейкам, в атрибут ячейки записывается число, равное количеству шагов от стартовой ячейки, на первом шаге это будет 1. Каждая ячейка, меченная числом шагов от стартовой ячейки, становится стартовой и из неё порождаются очередные шаги в соседние ячейки. Очевидно, что при таком переборе будет найден путь от начальной ячейки к конечной, либо очередной шаг из любой порождённой в пути ячейки будет невозможен.
Восстановление кратчайшего пути происходит в обратном направлении: при выборе ячейки от финишной ячейки к стартовой на каждом шаге выбирается ячейка, имеющая атрибут расстояния от стартовой на единицу меньше текущей ячейки. Очевидно, что таким образом находится кратчайший путь между парой заданных ячеек[6]. Трасс с минимальной числовой длиной пути, как при поиске пути в окрестностях Мура, так и фон Неймана может существовать несколько. Выбор окончательного пути в приложениях диктуется другими соображениями, находящимися вне этого алгоритма. Например, при трассировке печатных плат — минимумом линейной длины проложенного проводника.
Псевдокод
Инициализация
Пометить стартовую ячейку d := 0
Распространение волны
ЦИКЛ
ДЛЯ каждой ячейки loc, помеченной числом d
пометить все соседние свободные непомеченные ячейки числом d + 1
КЦ
d := d + 1
ПОКА (финишная ячейка не помечена) И (есть возможность распространения волны)
Восстановление пути
ЕСЛИ финишная ячейка помечена
ТО
перейти в финишную ячейку
ЦИКЛ
выбрать среди соседних ячейку, помеченную числом на 1 меньше числа в текущей ячейке
перейти в выбранную ячейку и добавить её к пути
ПОКА текущая ячейка — не стартовая
ВОЗВРАТ путь найден
ИНАЧЕ
ВОЗВРАТ путь не найден
См. также
- Динамическое программирование
- Трассировка печатных плат
- Лабиринт
- Список алгоритмов
Примечания
- ↑ 1 2 Иллюстрация показывает работу алгоритма в том случае, если он не останавливается после достижения целевой ячейки. По окончании работы алгоритма в каждой ячейке оказывается записано кратчайшее расстояние от стартовой ячейки.
- ↑ Moore E. F. The shortest path through a maze (англ.) // Proceedings of an International Symposium on the Theory of Switching (Cambridge, Massachusetts, 2–5 April 1957) — Harvard University Press, 1959. — Vol. 2. — P. 285—292. — 345 p. — (Annals of the Computation Laboratory of Harvard University; Vol. 30) — ISSN 0073-0750
- ↑ Lee, C.Y., «An Algorithm for Path Connections and Its Applications», IRE Transactions on Electronic Computers, vol. EC-10, number 3, pp. 346—365, 1961
- ↑ Cormen et al, Introduction to Algorithms, 3rd edition, p. 623
- ↑ Mathematics Stack Exchange Origin of the Breadth-First Search algorithm
- ↑ 1 2 Волновой алгоритм поиска пути. Дата обращения: 7 августа 2013. Архивировано 11 декабря 2013 года.
Литература
- Максим Мозговой. Занимательное программирование: Самоучитель. — СПб.: Питер, 2004. — 208 с. — ISBN 5-94723-853-5.
- Steven M. Rubin. Computer Aids for VLSI Design. — 1994.
- Wai Kai Chen. The Circuits and Filters Handbook. — 2nd ed. — 2003. — С. 1372—1374. — 2961 с. — ISBN 0-8493-0912-3.
- Frank Rubin. The Lee path connection algorithm // IEEE Transactions on Computers. — 1974. (недоступная ссылка)
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to Algorithms. — 3rd edition. — The MIT Press, 2009. — ISBN 978-0-262-03384-8.
Ссылки
- Волновой алгоритм Ли (4 соседа)
- Волновой алгоритм Ли (8 соседей)
- Maze Router: Lee Algorithm (слайды)
Эта страница в последний раз была отредактирована 16 августа 2023 в 20:50.
Обычно почти сразу, изредка в течении часа.