Если вы заметили на сайте какие либо неточности (ошибки, неработающие ссылки), просьба сообщить об этом на E-mail:
max-programma@yandex.ru Этим вы поможете не только мне, но и тем, кто посетит сайт после вас.
По вопросам получения исходных кодов писать туда же,
на
max-programma@yandex.ru.
07.10.2012
Волновой алгоритм
Волновой алгоритм — алгоритм, позволяющий найти минимальный путь в графе с рёбрами единичной длины. Основан на алгоритме поиска в ширину. Применяется для нахождения кратчайшего пути в графе, в общем случае находит лишь его длину.
Волновой алгоритм — один из основных при автоматизированной трассировке (разводке) печатных плат. Также одно из характерных применений волнового алгоритма — поиск кратчайшего расстояния на карте в стратегических играх.
Суть алгоритма
На двумерной клетчатой карте (матрице), состоящей из «проходимых» и «непроходимых» клеток, обозначена клетка старта и клетка финиша. Цель алгоритма — проложить кратчайший путь от клетки старта к клетке финиша, если это, конечно, возможно. От старта во все направления распространяется волна, причем каждая пройденная волной клетка помечается как «пройденная». Волна, в свою очередь, не может проходить через клетки, помеченные как «пройденные» или «непроходимые». Волна движется, пока не достигнет точки финиша или пока не останется непройденных клеток. Если волна прошла все доступные клетки, но так и не достигла клетки финиша, значит, путь от старта до финиша проложить невозможно. После достижения волной финиша, от финиша прокладывается путь до старта и сохраняется в массиве.
Разновидности
Заполнение по матрице в 4 направления, он же алгоритм Ли — более точный, но менее быстрый метод.
Заполнение по матрице в 8 направлений — более быстрый, но менее точный метод. Путь по диагонали приблизительно в 1.4 раза больше, чем по горизонтали и вертикали, именно поэтому клетки, расположенные по диагонали, имеют коэффициент +3, а по горизонтали и вертикали - коэффициент +2.
Существует так же алгоритм A* (A-star) — направленный волновой алгоритм.
Реализация
Среда разработки: Borland C++ Builder
Интерфейс: графический
Разновидность: по матрице в 4 направления
Содержимое проекта:
Img\
Project_Trass.bpr
Project_Trass.cpp
Project_Trass.res
Unit_DataIn.cpp
Unit_DataIn.ddp
Unit_DataIn.dfm
Unit_DataIn.h
Unit_Trass.cpp
Unit_Trass.ddp
Unit_Trass.dfm
Unit_Trass.h
Демка:
Оплатить с помощью Яндекс-Денег:
