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

Волново́й алгори́тм — алгоритм, позволяющий найти минимальный путь в графе с рёбрами единичной длины. Основан на алгоритме поиска в ширину. Применяется для нахождения кратчайшего пути в графе, в общем случае находит лишь его длину.

Суть алгоритма

На двумерной клетчатой карте (матрице), состоящей из «проходимых» и «непроходимых» клеток, обозначена клетка старта и клетка финиша. Цель алгоритма — проложить кратчайший путь от клетки старта к клетке финиша, если это, конечно, возможно. От старта во все направления распространяется волна, причем каждая пройденная волной клетка помечается как «пройденная». Волна, в свою очередь, не может проходить через клетки, помеченные как «пройденные» или «непроходимые». Волна движется, пока не достигнет точки финиша или пока не останется непройденных клеток. Если волна прошла все доступные клетки, но так и не достигла клетки финиша, значит, путь от старта до финиша проложить невозможно. После достижения волной финиша, от финиша прокладывается путь до старта и сохраняется в массиве.

Разновидности

Заполнение по матрице в 4 направления, он же алгоритм Ли — более точный, но менее быстрый метод.

    i+1
i+1  i  i+1
    i+1

Заполнение по матрице в 8 направлений — более быстрый, но менее точный метод. Путь по диагонали приблизительно в 1.4 раза больше, чем по горизонтали и вертикали, именно поэтому клетки, расположенные по диагонали, имеют коэффициент +3, а по горизонтали и вертикали - коэффициент +2.

i+3 i+2 i+3
i+2  i  i+2
i+3 i+2 i+3

Существует так же алгоритм A* (A-star) — направленный волновой алгоритм.

Практическое применение

Волновой алгоритм — один из основных при автоматизированной трассировке (разводке) печатных плат. Также одно из характерных применений волнового алгоритма — поиск кратчайшего расстояния на карте в стратегических играх.

Ссылки

• Описание алгоритма