c++ - Boost Graph Library 中的最佳优先搜索

Question

我开始使用 boost 图形库。我需要一个最佳优先搜索，我可以通过零成本使用 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) = 启发式，从当前状态到最终状态的成本估计。

来自维基百科：

作为最佳优先搜索算法的另一个示例，Dijkstra 算法可以被视为 A* 的一个特例，其中对于所有 x，h(x) = 0。

Answer 3

正如 Aphex 的回答所建议的，您可能想使用 Dijkstra 的算法；设置边缘权重的一种方法是设置w(u, v)为potential(v) - potential(u)，假设它是非负的。Dijkstra 的算法假设边权重为正，因此距离会随着您远离源节点而增加。如果您正在寻找最小的潜力，请翻转减法的两侧；如果你有上下波动的潜力，你可能需要使用像贝尔曼福特这样的东西，这不是最好的。