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