Поиск Best-First в библиотеке Boost Graph

Question

Я начинаю работать с библиотекой графов наддува.Мне нужен лучший поиск, который я мог бы реализовать, используя astar_search, имея нулевые затраты.(Пожалуйста, поправьте меня, если я ошибаюсь.)

Однако мне интересно, есть ли другая возможность сделать это?Если затраты не учитываются, алгоритм должен быть несколько более эффективным.

РЕДАКТИРОВАТЬ: Извините за неясное описание.Я на самом деле реализую поиск потенциального поля, поэтому у меня нет каких-либо затрат / весов, связанных с ребрами, а скорее мне нужно выполнить поиск по крутому спуску (который может преодолеть локальные минимумы).

Спасибо залюбые намеки!

Answer 1

Если вы знакомы с C ++, я бы предложил попробовать YAGSBPL .

Answer 2

Вы можете определенно использовать A * для решения этой проблемы;вам нужно, чтобы h (x) было равно 0, а не g (x) .A * оценивает узлы на основе F, который определяется как

F(n) = g(n) + h(n).

TotalCost = PathCost + Heuristic.

g (n) = Стоимость пути, расстояние от начального до текущего состояния

h (n)= Эвристический, оценка стоимости от текущего состояния до конечного состояния.

Из Википедия :

Алгоритм Дейкстры, как еще один пример алгоритма поиска с наилучшим первым поиском, можно рассматривать как частный случай* где h (x) = 0 для всех x.

Answer 3

Как следует из ответа Aphex, вы можете использовать алгоритм Дейкстры; Один из способов установки веса ребер - установить w(u, v) в potential(v) - potential(u), предполагая, что это неотрицательно. Алгоритм Дейкстры предполагает, что веса ребер положительны и поэтому расстояния увеличиваются при удалении от исходного узла. Если вы ищете наименьший потенциал, переверните стороны вычитания; если у вас есть потенциалы, которые растут как вверх, так и вниз, вам может понадобиться что-то вроде Беллмана-Форда, которое не является лучшим в первую очередь.