AStar с вложенной структурой графика

У меня есть график (текущий направленный ациклический график), реализованный с использованием boost a *. Сам график несколько пространственно несогласован, поскольку граф состоит из нескольких зон, которые внутри каждой зоны, координаты имеют смысл пространственно, но между координатами зон неточно отражают пространственное расстояние. Таким образом, в зонах, эвклидовое расстояние работает как метрика расстояния, но при рассмотрении узлов в двух отдельных зонах эвклидово расстояние отсутствует. Это также невозможно исправить, так как график предназначен для MUD, который не имеет жесткой координатной структуры.

Одно из решений заключается в моделировании пути из a-> b в виде серии движений по зонам, поиска самого быстрого маршрута в каждой соответствующей зоне и последующего объединения этих путей в конечную.

Итак, мой вопрос: есть ли способ иметь такую структуру "вложенного графа", или мне придется вручную решить проблему?

1 ответ

Вероятно, вы можете взглянуть на концепцию подграфа в библиотеке Boost.Graph. В реальных примерах используется boost :: adjacency_list.

Я предполагаю, что вашей отправной точкой было бы создание суперграфа; затем создайте подграф для каждой зоны, заполните их вершинами. Самая сложная часть - это, вероятно, добавить все ребра такого графа.

Что касается отображения расстояния для графика, вам не нужно хранить его на графике; он может быть внешним свойством property_map или даже функтором, который вычисляет расстояние динамически.

licensed under cc by-sa 3.0 with attribution.