为什么具有可接受的不一致启发式的 A* 会找到非最优解？

Question

我知道具有可接受的非一致启发式的 A* 不会找到最佳解决方案，但我正在努力寻找它何时会发生的示例。

由于这种想法，我找不到示例 - 在将我们的目标节点（具有非最优 f(n)）插入优先级队列后，优先级队列还必须包含节点，例如node_1在最优路径上。优先级队列中 node_1 的 f(n) 必须小于目标节点的 f(n)，因为我们使用的是可接受的启发式算法。这就是为什么 node_1 会在 A* 的一些迭代之后更早地出队（使用相同的想法） goal_node找到最优路径后会出队

我哪里想错了？当具有可接受的非一致启发式的 A* 将找到非最佳路径时，有人可以给我简单图的简明示例吗？

谢谢。

Answer 1

这是一个图表示例，其中我们使用不一致的启发式方法得到了错误的答案。在这里，启发式显示在每个节点附近的括号中，边缘成本写在边缘旁边：

     (8)
      A
     / \
+1  /   \ +3
   /     \   
  B ----- C ----- D
(7)  +1  (0)  +6  (0)

在这里，从 A 到 D 的最佳路径是 A - B - C - D，总成本为 8。但让我们看看 A* 会做什么：

从 A 开始，选项是从 A 到 B 的成本加启发式 8，或者从 A 到 C 的成本加启发式 3。所以我们选择 A - C.
现在，我们的选择是扩展 A - B 以获得 8 的成本加启发式，或扩展 C - D 以获得 9 的成本加启发式。所以我们选择 A - B。
我们已经通过前面的路径关闭了C，所以我们不考虑边B - C。相反，我们选择C - D，成本为9。
总的来说，我们找到了路径A - C - D。糟糕。

下一个问题是您究竟如何找到这样的示例，为此，我认为以下观点对于思考 A* 的工作原理非常有用：

Running A* on a graph whose edges have costs c(u, v), using a heuristic function h(v), is equivalent to running Dijkstra's algorithm on a graph where the cost of an edge (u, v) is c(u, v) + h(v) - h(u).

换句话说，您可以将 A* 的作用想象成运行ning Dijkstra 算法，通过添加跨每条边的启发式值的变化来调整每条边的成本。

之所以有用，是因为著名的 Dijkstra 算法会在图形中存在负边的情况下返回错误答案。所以我们可以问 - 当我们将边成本更改为 c(u, v) + h(v) - h(u) 时，我们是否会以负成本结束？换句话说，要确保

c(u, v) + h(v) - h(u) ≥ 0?

通过快速重新排列，您可能会注意到如果

c(u, v) + h(v) ≥ h(u)

或者，等价地，uf

h(u) ≤ c(u, v) + h(v).

嘿！这就是一致启发式的定义。

这意味着使用具有不一致启发式的 A* 可能会出错，其方式与使用负边权重的 Dijkstra 算法可能出错的方式完全相同。您（很可能）会运行遇到一个问题，您会发现通往目标路径上某个中间节点的次优路径，并从那里得到错误的答案。

我最终制作了上面的图表，其中 A* 失败了，从这张 Dijkstra 得到错误答案的图表开始，然后逆向工程一个启发式算法，使边缘成本全部为正：

    A
+0 / \ -5
  /   \
 B --- C --- D
    -6    +6

在这里，Dijkstra 找到的从 A 到 D 的路径是路径 A - C - D，成本为 1，而不是路径 A - B - C - D，成本为 0。这是一样的上面 A* 示例中的错误路径。

为什么具有可接受的不一致启发式的 A* 会找到非最优解？

Why does A* with admissible non consistent heuristic find non optimal solution?

algorithm

search

heuristics

graph-theory

a-star