Алгоритмы решения задачи быстрого поиска
пути на географических картах
5
Одним из главных достоинств алгоритма
BFS является то, что
он гарантированно находит кратчайший путь из начальной вершины
в конечную. Однако недостатком является необходимость исследо-
вания большого числа сторонних точек, что требует излишних за-
трат памяти для хранения информации, а также дополнительного
времени.
Алгоритм поиска в глубину.
Поиск в глубину (Depth-first search,
DFS) проверяет каждый возможный путь целиком, прежде чем пе-
рейти к другому возможному маршруту. При обходе дерева маршру-
тов каждый раз выбирается левая ветвь, пока не будет достигнут ко-
нечный узел или найдена цель. Если текущий узел — конечный,
совершается подъем на один уровень вверх и выбирается правая
ветвь дерева, а из нее продолжается движение по левым ветвям до
тех пор, пока не встретится цель или конечный узел. Эта процедура
повторяется, пока не будет обнаружена цель или пройден последний
узел пространства.
Одной из возможных оптимизаций алгоритма DFS является алго-
ритм последовательных приближений при поиске в глубину (Iterative
deeping depth-first search, IDDFS). В действительности в алгоритме
поиска в глубину существует еще одна проблема — выбор правиль-
ной глубины остановки. Если она будет слишком маленькой, то путь
не будет найден, если слишком большой, то можно потратить много
времени и денег впустую. Эти проблемы решаются итеративным
углублением — приемом, при котором выполняется DFS с увеличе-
нием глубины до тех пор, пока путь не будет найден. При поиске пу-
ти можно не начинать с глубины, равной единице, а сразу начать
с глубины, равной расстоянию по прямой от старта до цели. Этот по-
иск является асимптотически оптимальным среди всех переборных
алгоритмов по времени и памяти.
Алгоритм Дейкстры.
Введем массив
d
[ ], в котором для каждой
вершины
v
будем хранить текущую длину
d
[
v
] кратчайшего пути из
начальной вершины
s
в конечную вершину
v
. Для
s
эта длина равна 0,
а для всех остальных — бесконечности (в качестве бесконечности
обычно выбирают достаточно большое число, заведомо большее
возможной длины пути):
d
[
v
] = ∞,
v
≠
s
. Кроме того, для каждой вер-
шины
v
будем хранить информацию о том, помечена она или нет,
т. е. заведем булевский массив
u
[ ]. Изначально все вершины не по-
мечены
u
[
v
] = false.
Сам алгоритм Дейкстры состоит из
n
итераций. На очередной
итерации выбирается вершина
v
с наименьшей длиной
d
[
v
] среди еще
не помеченных (на первой итерации будет выбрана стартовая верши-
на
s
). Выбранная таким образом вершина
v
считается «помеченной».
Далее, на текущей итерации, из вершины
v
производятся релаксации:
