Алгоритмы решения задачи быстрого поиска
пути на географических картах
3
мости и увеличение (в среднем) найденного пути по сравнению
с оптимальным.
Формы ячейки сетки проходимости
Форма ячейки
Число соседних ячеек Увеличение длины пути, %
Треугольник
3
100
6
15
Квадрат
4
41
8
8
Шестиугольник
6
15
12
4
Исходя из данных, представленных в [2], наиболее выгодным
является использование квадратных ячеек с рассмотрением 8 бли-
жайших соседей (в случае шестиугольника и 12 соседей результат
получился несколько лучше, однако такая реализация обычно оказы-
вается на порядок сложнее).
Учитывая сказанное, при решении поставленной задачи мы в
большинстве случаев будем интерпретировать карту набором квад-
ратных ячеек, составляя из них сетку. Квадраты сетки будут марки-
роваться числами 0 или 1 (проходим или не проходим), т. е. для каж-
дого типа объекта и типа местности, по которому он движется,
определяется собственно факт проходимости. В перспективе задача
может быть усложнена введением некоторого штрафа, отражающего
различный характер проходимости ячейки.
Алгоритмы поиска оптимального пути.
Алгоритмы этой
группы позволяют найти оптимальный путь, но требуют большого
ресурса памяти для хранения информации о том, какой удельный вес
имеет каждая ячейка на карте, если она является частью
оптимального пути. К тому же, время выполнения подобных
алгоритмов также очень велико, поскольку требуется рассмотреть
всю область, где потенциально может быть проложен маршрут. В
основном подобного рода алгоритмы применяются либо на картах
небольшого размера, где точность найденного пути играет большую
роль, либо на этапе подготовки, когда требуется проложить
некоторые не меняющиеся со временем магистрали.
Рассмотрим наиболее известные алгоритмы поиска оптимального
пути [1].
Алгоритм поиска в ширину.
При работе алгоритма поиска в ши-
рину (Breadh-first search, BFS) сетка представляется в виде взвешен-
ного графа, где из каждой вершины возможен переход в одну из
8 соседних вершин (кроме граничных). Веса вершин — 0 либо
∞
(для случая полной непроходимости). Для работы алгоритма требу-
ется организовать очередь, в которую будут последовательно добав-
