Алгори́тм волново́й трассиро́вки (волновой алгоритм, алгоритм Ли) — алгоритм поиска пути, алгоритм поиска кратчайшего пути на планарном графе. Принадлежит к алгоритмам, основанным на методах поиска в ширину.
В основном используется при компьютерной трассировке (разводке) печатных плат, соединительных проводников на поверхности микросхем. Другое применение волнового алгоритма — поиск кратчайшего расстояния на карте в компьютерных стратегических играх.
Волновой алгоритм в контексте поиска пути в лабиринте был предложен Э. Ф. Муром [2] . Ли независимо открыл этот же алгоритм при формализации алгоритмов трассировки печатных плат в 1961 году [3] [4] [5] .
Содержание
Описание алгоритма [ править | править код ]
Алгоритм работает на дискретном рабочем поле (ДРП), представляющем собой ограниченную замкнутой линией фигуру, не обязательно прямоугольную, разбитую на прямоугольные ячейки, в частном случае — квадратные. Множество всех ячеек ДРП разбивается на подмножества: «проходимые» (свободные), т. е при поиске пути их можно проходить, «непроходимые» (препятствия), путь через эту ячейку запрещён, стартовая ячейка (источник) и финишная (приемник). Назначение стартовой и финишной ячеек условно, достаточно — указание пары ячеек, между которыми нужно найти кратчайший путь.
Алгоритм предназначен для поиска кратчайшего пути от стартовой ячейки к конечной ячейке, если это возможно, либо, при отсутствии пути, выдать сообщение о непроходимости [6] .
Работа алгоритма включает в себя три этапа: инициализацию, распространение волны и восстановление пути.
Во время инициализации строится образ множества ячеек обрабатываемого поля, каждой ячейке приписываются атрибуты проходимости/непроходимости, запоминаются стартовая и финишная ячейки.
Далее, от стартовой ячейки порождается шаг в соседнюю ячейку, при этом проверяется, проходима ли она, и не принадлежит ли ранее меченной в пути ячейке.
Соседние ячейки принято классифицировать двояко: в смысле окрестности Мура и окрестности фон Неймана, отличающийся тем, что в окрестности фон Неймана соседними ячейками считаются только 4 ячейки по вертикали и горизонтали, в окрестности Мура — все 8 ячеек, включая диагональные.
При выполнении условий проходимости и непринадлежности её к ранее помеченным в пути ячейкам, в атрибут ячейки записывается число, равное количеству шагов от стартовой ячейки, от стартовой ячейки на первом шаге это будет 1. Каждая ячейка, меченная числом шагов от стартовой ячейки, становится стартовой и из неё порождаются очередные шаги в соседние ячейки. Очевидно, что при таком переборе будет найден путь от начальной ячейки к конечной, либо очередной шаг из любой порождённой в пути ячейки будет невозможен.
Восстановление кратчайшего пути происходит в обратном направлении: при выборе ячейки от финишной ячейки к стартовой на каждом шаге выбирается ячейка, имеющая атрибут расстояния от стартовой на единицу меньше текущей ячейки. Очевидно, что таким образом находится кратчайший путь между парой заданных ячеек [6] . Трасс с минимальной числовой длиной пути, как при поиске пути в окрестностях Мура, так и фон Неймана может существовать несколько. Выбор окончательного пути в приложениях диктуется другими соображениями, находящимися вне этого алгоритма. Например, при трассировке печатных плат — минимумом линейной длины проложенного проводника.
Идея этого метода весьма проста: в стороны от исходной точки распростроняется волна.
Начальное значение волны — ноль.
То есть ближайшие точки, в которые можно пойти, например, верх, низ, левая и правая, и которые еще не затронуты волной, получают значение волны+некоторый модификатор проходимости этой точки. Чем он больше — тем медленнее преодоление данного участка. Значение волны увеличивается на 1.
Обрабатываем аналогично клетки, отходя от тех, на которой значение волны — 2. При этом на клетках с худшей проходимостью волна задержится.
И так дальше все обрабатывается, пока не достигнута конечная точка маршрута.
Сам путь в получившемся массиве значений волны вычисляется по наименьшим клеткам. В примере на Си все очень хорошо продемонстрировано.
В разделе графы есть более формальное описание алгоритма применительно к графам и доказательство корректности
Чтобы найти кратчайший путь в лабиринте использую волновой алгоритм, его сделал, но вот кратчайший путь не получается восстановить.
В конечной ячейке:
map[finishX][finishY] = 19;
После прохода волнового алгоритма лабиринт выглядит так:
0 0 0 0 0 0 0 0 0 0 0 0 0
0 7 8 9 10 11 12 13 14 15 16 17 0
0 6 7 8 9 10 11 12 13 14 15 16 0
0 5 6 7 8 9 10 11 12 13 14 15 0
0 4 5 6 7 8 9 10 11 12 13 14 0
2 3 4 5 6 7 8 9 10 11 12 0 15
1 0 4 5 6 7 8 9 10 11 0 13 14
2 0 5 5 6 7 8 9 10 11 0 14 14
0 0 6 6 6 7 8 9 10 11 0 15 0
0 0 7 7 7 7 8 9 10 11 0 15 0
0 0 8 8 8 8 8 9 10 11 0 14 0
0 0 9 9 9 9 9 9 10 11 12 13 0
0 0 0 0 0 0 0 0 0 0 0 0 0