М.А. Басараб, А.Б. Домрачева, В.М. Купляков
2
В первой группе для нахождения решения требуется полностью
исследовать некоторую область. Самым простым способом поиска
оптимального пути является полный перебор всех возможных марш-
рутов. В этом случае найденный путь будет кратчайшим. Однако
такой способ неприменим в большинстве случаев из-за чрезмерных
накладных расходов, так как требуется полное исследование всей
карты и хранение ее в памяти.
В связи с этим на первый план выходит разработка алгоритмов
поиска субоптимальных путей. Примером являются эвристические
алгоритмы, которые на каждом шаге приближаются к конечной точ-
ке. Однако при поиске одного из близких к оптимальному пути сле-
дует учитывать, что изначально трудно точно предсказать, какой
именно вариант будет выбран. К тому же, одним из требований
к маршруту является его реалистичный внешний вид. В этом случае
можно использовать различные алгоритмы при выборе направления
на каждом шаге либо различные алгоритмы постобработки маршру-
тов.
Наряду с алгоритмами, позволяющими непосредственно опре-
делить путь, следует учитывать разнообразные алгоритмы посто-
бработки полученного маршрута. Они позволяют разбить исходную
задачу на несколько подзадач, например:
•
определение возможного направления движения;
•
определение ключевых точек маршрута и удаление точек,
лежащих на одной прямой;
•
спрямление отдельных участков пути;
•
«огрубление» предварительного представления пути.
В данной работе на основе тестового анализа было предложено
включить в библиотеку такие алгоритмы поиска пути:
•
алгоритм Дейкстры;
•
алгоритм A*;
•
алгоритм Theta*.
В качестве алгоритмов постобработки выбраны следующие:
•
удаление точек, лежащих на одной прямой;
•
применение функции Line of Sight, используемой в алгоритме
Theta*.
На примерах решения тестовых задач показана эффективность
реализованной библиотеки.
Представление ландшафта.
Большое влияние на качество на-
хождения пути оказывает способ представления ландшафта. В основ-
ном для этого используется представление карты в виде матрицы
проходимостей. Выбор формы ячейки играет большую роль при
реализации алгоритма — влияет на длину полученного пути.
В таблице приведены основные используемые формы ячеек проходи-
