Art*_* B. 9 algorithm graph-theory
这似乎是正确的,但我在网上找不到任何人说这是,所以我想确定.如果您同意,请告诉我,如果是,为什么.理想情况下是指向纸张的链接,或者,如果您不同意,则为反例.
我们G是一个有向图有一些负面的边缘.我们想要运行A*G.
首先,如果G从源头到达并且达到目标的负周期,则没有可接受的启发式,因为不可能低估达到目标的成本,因为它是-?.
但是,如果没有这样的循环,可能会有一些可接受的启发式.特别是,所有负边缘的总和将始终低估达到目标的成本.
我的印象是,在这种情况下,A*可以正常工作.
PS我可以在图上运行Bellman-Ford,检测负循环,如果没有,重新加权以消除负边缘.但是,如果我知道没有负循环,我可以跳过它并运行A*.
这是非常错误的.顶点的成本是启发式和到目前为止构建的路径的总和......而启发式低估了达到目标的成本,启发式和到目前为止所采用的路径的总和可能不是.千里马culpa.
似乎用一个低估了达到目标的成本的函数对开放集进行排序,而通过一个给定的顶点可能会工作......如果一个人使用<sum of negative edges in the graph>这样的函数,它看起来像退化为图遍历.
考虑具有 3 个节点和 3 个权重的示例：
1 2 -10
1 3 -3
3 2 -8
从 1 到 2 存在权重为 -10 的路径。所以你首先得到这个并将其建立为到 2 的最小路径。但是有一条路径 (1-3-2) 比第一个路径更小。
在评分最高的答案给出的示例中：（2，-10）进入优先级队列。同意。(3,x) 也是如此，其中 x<=-11 作为启发式是可接受的。现在，当 x<-10 时，(3,x) 被弹出，我们得到了正确的解决方案。
我不能将此作为评论，因为我没有足够的声誉。