18 января 2010 в 11:43
Волновой алгоритм поиска пути на c++
Идея волнового алгоритма поиска пути заключается в том, что мы будем пускать волну от стартовой точки. Для этого в каждой ячейке будем хранить число шагов, за которое в нее можно добраться. Изначально добраться можно только до стартовой за 0 шагов. Постепенно увеличивая некоторую переменную step, мы будем находить ячейки, расстояние (число шагов) до которых равно step. Такие ячейки являются соседями ячеек, найденных на предыдущем шаге, т.е. число шагов до которых равно step-1.
Замечание: в примере отсутствует код заполнения начальной матрицы - сами сделаете как вам надо, а так же при нахождении пути координаты не сохраняет - сами выбирайте как хранить - в векторе или еще как
Во-первых, в реализации мы начинали не от старта, а от финиша. Почему? Потому что если начинать от старта, то в конце мы получим массив, в котором все вершины идут в обратном порядке, и нам пришлось бы его разворачивать.
Во-вторых, в алгоритме в каждой ячейке хранится еще значения координат откуда шагнули в данную ячейку, что сильно упрощает построение конечного пути. Этого можно и не делать, достаточно идти с конца и выбирать соседа с наименьшим значением step, но учтите, что нужно будет у каждой вершины пробегать соседей. Явно будет затрачено больше времени и ресурсов для подсчета.
Есть более быстрые алгоритмы поиска пути. Хотя скорость зависит от размеров массива для поиска, а тажке от оптимизации данного кода.
комментарии отсутствуют
авторизуйтесь