为什么带有可接受的非一致启发式的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 *的工作方式非常有用的观点如下：

使用启发式函数h（v）在边缘具有成本c（u，v）的图形上运行A *，相当于在边缘（u，v）的成本为c（u）的图形上运行Dijkstra算法，v）+ h（v） - h（u）。

换句话说，您可以考虑A *正在做什么，就像您运行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.这与路径中的路径相同。一个例子在顶部。