维基百科A*算法的错误

发表于 | 阅读次数

先放中文wiki的代码，时间为2017年11月18日16:08:08。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
function A*(start,goal)
     closedset := the empty set                 //已经被估算的节点集合
     openset := set containing the initial node //将要被估算的节点集合，初始只包含start
     came_from := empty map
     g_score[start] := 0                        //g(n)
     h_score[start] := heuristic_estimate_of_distance(start, goal)    //通过估计函数 估计h(start)
     f_score[start] := h_score[start]            //f(n)=h(n)+g(n)，由于g(n)=0，所以省略
     while openset is not empty                 //当将被估算的节点存在时，执行循环
         x := the node in openset having the lowest f_score[] value   //在将被估计的集合中找到f(x)最小的节点
         if x = goal            //若x为终点，执行
             return reconstruct_path(came_from,goal)   //返回到x的最佳路径
         remove x from openset      //将x节点从将被估算的节点中删除
         add x to closedset      //将x节点插入已经被估算的节点
         for each y in neighbor_nodes(x)  //循环遍历与x相邻节点
             if y in closedset           //若y已被估值，跳过
                 continue
             tentative_g_score := g_score[x] + dist_between(x,y)    //从起点到节点y的距离
 
             if y not in openset          //若y不是将被估算的节点
                 add y to openset         //将y插入将被估算的节点中
                 tentative_is_better := true     //暂时判断为更好
             elseif tentative_g_score < g_score[y]         //如果起点到y的距离小于y的实际距离
                 tentative_is_better := true         //暂时判断为更好
             else
                 tentative_is_better := false           //否则判断为更差
             if tentative_is_better = true            //如果判断为更好
                 came_from[y] := x                  //将y设为x的子节点
                 g_score[y] := tentative_g_score    //更新y到原点的距离
                 h_score[y] := heuristic_estimate_of_distance(y, goal) //估计y到终点的距离
                 f_score[y] := g_score[y] + h_score[y]
     return failure
 
 function reconstruct_path(came_from,current_node)
     if came_from[current_node] is set
         p = reconstruct_path(came_from,came_from[current_node])
         return (p + current_node)
     else
         return current_node

基友猴哥告诉我，wiki上拓展子节点的时候，如果子节点出现在Close表中话，不做任何处理。而教材人工智能及其应用、算法艺术与信息学竞赛 中均对子节点的F值进行了计算，如果小于表中已有的，则必须更新(加入)到Open表中。而wiki上不论中英文版本均不做处理。那么有什么影响？

抽象的想，从起点S开始有p1、p2两条路径均可到达中间某节点A。假设从p1到达A之后，拓展A的子节点，此时A已加入到S表中，且A的子节点是在A的基础上计算的G值。那么如果路径p2到达A的代价值(G)比p1小，按照wiki的流程图，最终结果还是采用p1这条代价更大的走法，从而无法收敛到最优解(从p2到A)。

多说无益，下面我构造了个例子：

graph LR; S{S 20}--12-->A{A 13}; S--10-->B{B 16}; B--1-->A; A--15-->D{D 10};

起点是S，目标是X(未画出，在D之后)。节点内部的数字表示H估值，变上面的数字代表G代价。以下是按照wiki的流程：

格式为：A(G,H) 粗体表示最小F值节点。 斜体表示新加入节点。

Step Open Close
1 A(12,13) B(10,16) null
2 B(10,18) D(12+15,10) A(12,13)
3 D(12+15,10) A(12,13)

到这里，拓展B的时候发现A已经在Close表中，就不采取任何操作，而D(F=37)和D之后节点的G值都是在A 12的基础上计算，明显比S→B→A(只需要11)大，故在这种情况下得到的不是最优解。

而采用更像放回Open表中的情况呢?

Step Open Close
1 A(12,13) B(10,16) null
2 B(10,18) D(12+15,10) A(12,13)
3 D(12+5,10) A(10+1,13) B(10,18)
4 D(10+1+15,10) B(10,18) A(10+1,13)

此时D的F值为26+10=36，路径是S→B→A→D，是最优路径。