Boost Graph Library 中的最佳优先搜索
我开始使用 boost 图形库。我需要一个最佳优先的搜索，我可以使用 astar_search 实现零成本。 （如果我错了，请纠正我。）
但是，我想知道是否还有另一种可能性这样做？如果不考虑成本，算法的效率应该会稍微高一些。
编辑：抱歉描述不清楚。我实际上正在实施潜在的现场搜索，因此我没有与边缘相关的任何成本/权重，而是需要进行最速下降搜索（这可以克服局部最小值）。
感谢您的任何提示！
I am starting to work with boost graph library. I need a best-first search, which I could implement using astar_search by having zero costs. (Please correct me if I'm wrong.)
However, I wonder if there is another possibility of doing this? If the costs are not considered, the algorithm should be slightly more efficient.
EDIT: Sorry for the unclear description. I am actually implementing a potential field search, so I don't have any costs/weights associated with the edges but rather need to do a steepest-descent-search (which can overcome local minima).
Thanks for any hints!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
你绝对可以使用 A* 来解决这个问题；你需要h(x)为0，而不是g(x)。 A* 基于 F 对节点进行评级，F 定义为
来自维基百科：
You could definitely use A* to tackle this; you'd need h(x) to be 0 though, not g(x). A* rates nodes based on F which is defined by
From Wikipedia:
如果您熟悉 C++，我建议尝试 YAGSBPL。
If you are comfortable with C++, I would suggest trying out YAGSBPL.
正如 Aphex 的答案所建议的，您可能想要使用 Dijkstra 的算法；设置边权重的一种方法是将
w(u, v)设置为pottial(v) - Potential(u)，假设该值是非负的。 Dijkstra 算法假设边权重为正，因此距离会随着远离源节点而增加。如果您正在寻找最小的势，请翻转减法的两侧；如果你的潜力既上升又下降，你可能需要使用贝尔曼福特之类的东西，这不是最好的第一。As suggested by Aphex's answer, you might want to use Dijkstra's algorithm; one way to set the edge weights is to set
w(u, v)topotential(v) - potential(u), assuming that is nonnegative. Dijkstra's algorithm assumes that edge weights are positive and so that distances increase as you move away from the source node. If you are searching for the smallest potential, flip the sides of the subtraction; if you have potentials that go both up and down you might need to use something like Bellman-Ford which is not best-first.