Могу ли я реализовать метод потенциального поля / глубины для предотвращения препятствий, используя график усиления?

Question

Я реализовал алгоритм обхода препятствий в Matlab, который присваивает каждому узлу графа потенциал и пытается уменьшить этот потенциал (цель планирования пути находится в глобальном минимуме). Теперь могут появиться локальные минимумы, поэтому (глобальному) планированию нужен способ их преодоления. Я использовал стратегию, чтобы получить список открытых узлов, которые доступны из уже посещенных узлов. Я посещаю открытый узел, который имеет наименьший потенциал рядом.

Я хочу реализовать это в C ++, и мне интересно, есть ли в Boost Graph такие алгоритмы. Если нет - есть ли польза от использования этой библиотеки, если мне придется самому написать алгоритм, и мне также придется создать собственный класс графа, потому что граф слишком велик, чтобы хранить его в памяти как список смежности / список ребер.

Любой совет приветствуется!

Answer 1

boost::graph предоставляет список алгоритмов кратчайших путей / минимизации затрат. Вас могут заинтересовать следующие элементы: Кратчайший путь Дейкстры , A *.
Алгоритмы могут быть легко настроены. Если это не совсем соответствует вашим потребностям, взгляните на концепцию посетителя . Это позволяет вам настроить свой алгоритм в некоторой предопределенной точке события.

Наконец, Распределенный BGL обрабатывает огромный граф (потенциально миллионы узлов). Это будет работать для вас, если ваш график не помещается в памяти.

Хороший обзор библиотеки графов ускорения можно найти здесь . И, конечно же, не стесняйтесь задавать более конкретный вопрос о BGL на stackoverflow.

Answer 2

На мой взгляд, boost::graph действительно великолепен для реализации новых алгоритмов, потому что он предоставляет различные держатели данных, адаптеры и часто используемые вещи (которые, очевидно, могут использоваться как части недавно построенных алгоритмов).

Последние также настраиваются из-за использования посетителей и других умных шаблонов.

На самом деле, boost::graph может потребоваться некоторое время, чтобы привыкнуть, но, на мой взгляд, оно действительно того стоит.