只要启发式函数是可行的，A*算法是否能处理负权重？

Question

这个观点看起来是正确的，但我在互联网上找不到任何人说它是正确的，所以我想确保一下。如果您同意，请告诉我原因，最好附上一篇论文链接；如果您不同意，请提供反例。

假设有一个带有负边的有向图G，我们想在G上运行A*算法。

首先，如果从源节点到目标节点存在可达的负环，则不存在合适的启发式函数，因为无法低估到达目标节点的代价，因为它是-∞。

然而，如果没有这样的环，可能存在一些合适的启发式函数。特别地，所有负边的和将始终低估到达目标节点的代价。

我认为在这种情况下，A*算法可能会正常工作。

P.S. 我可以在图上运行Bellman-Ford算法，检测负环，并且如果没有负环，重新赋权值以消除负边。但是，如果我知道没有负环，我可以跳过这一步直接运行A*算法。

---

这是显然错误的。一个顶点的代价是启发式函数和到目前为止所经过的路径的总和...虽然启发式函数低估了到达目标节点的代价，但启发式函数和到目前为止所经过的路径的总和可能不会低估。我犯了大错。

看起来，如果使用一个低估到达目标节点代价的函数对开放集进行排序，并在通过给定顶点时使用该函数，那么这个算法可能会工作...如果将<图中所有负边的和>作为这样的函数，它看起来会退化成一个图遍历算法。

- Arthur B.

---

也许在cstheory.stackexchange.com上询问会更好。 - Jakub Hampl

Answer 1

在最佳答案中给出的示例中： (2,-10)进入优先级队列，同意。 当启发式是可接受的时，(3,x)，其中x<=-11也会进入队列。 现在，由于x<-10，(3,x)被弹出，我们得到了正确的解决方案。

我无法作为评论发布此内容，因为我没有足够的声望。

- Nitesh Bharadwaj Gundavarapu

Answer 2

考虑有3个节点和3个权重的示例：

1 2 -10
1 3 -3
3 2 -8

从1到2有一条权重为-10的路径。所以你首先得到了它，并将其建立为到2的最小路径。然而，存在一条路径（1-3-2），比第一条路径更短。

- Mariy

---

啊，是的，如果我的启发式函数是一个常数，那么我基本上又回到了Dijkstra算法...应该早点看出来。我正在处理一种特定类别的图形，其中使用不同的启发式函数可以工作，而我一直认为它更通用。 - Arthur B.

这里没有项目经理，但我希望你能给出意见。如果使用Heuristic [source，a] + Heuristic [source，goal]而不是Path_Cost_top [a] + Heuristic [a，goal]，您将得到一个图遍历，扩展节点的可能性较小，以后发现其具有较低的成本。 - Arthur B.

我认为这是错误的，就像Nitesh在下面所描述的那样。 - nivekgnay

@Ant，我指的是负启发式。在这种情况下，由于我们有负边权，因此在某些地方，可接受的启发式必须为负数。此外，我们需要使用树搜索范例来实现它，而不是图搜索。https://dev59.com/wGgv5IYBdhLWcg3wVPTU - Nitesh Bharadwaj Gundavarapu

@h4nek，那个结果为什么会是错误的呢？如果你有负权重，这意味着你有奖励而不是成本，所以你确实想要走经过更长路径给你-11的路线，对吧？ - jbx

Answer 3

这是微不足道的错误。一个顶点的成本是启发式和至今建立的路径之和……虽然启发式低估了到达目标的成本，但启发式和迄今为止所走过的路径之和可能不是如此。

A*算法永远不会扩展一个节点，使得启发式和到目前为止所走过的路径（f值）大于最优路径长度。这是因为在最优路径上，总会有一个节点的f值小于或等于最优成本。

因此，即使存在负权重边，只要有限数量的具有小于最优成本的f值的边，A*算法将找到最优路径，如果存在这样的路径。

- nivekgnay

---

要补充引用的文本（换句话说）：如果启发式低估了到达目标的成本，那么迄今为止所采取的路径加上启发式肯定会低估使用当前节点的最小路径的成本。 - h4nek