为什么带有可接受的非一致启发式的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.这与路径中的路径相同.一个例子在顶部.