A-star

Posted on Edited on In Views: Word count in article: 2k Reading time ≈ 2 mins.

A*算法


更新后继

open-set是当前已经发现的、还没有搜索的点，即从起点有一条有限长的路径到这些点，
close-set是已经搜索更新后继完毕的点。
更新后继时：

  • 后继不在任意一个set中，说明这个点第一次被发现，加入open-set即可。
  • 后继在open-set中，说明发现了一个从起点出发到这个点的新的道路，需要与历史记录相比选更短的。
  • 后继在close-set中，与上一种情况类似。注意此时若新发现的道路更短，意味着之前的搜索是不准确的，需要将其加入open-set再次搜索。

正确性

A*算法的关键是估计函数h，h值的估计要放宽条件，从而从n点到终点的估计代价要小于实际代价。

考虑终点是open-set中f值最小的点，这个f值便是当前找到的最短路径。
先考虑已经找到从起点开始的最短路径的那些点，从起点经过这些点到达终点的路径长度一定大于这些点的f值（A*算法的条件），因而大于当前已经找到的最短路径。
在考虑那些尚未找到最短路径的点，向上追溯祖先会找到一个已经确定最短路径的点，由上一条得知这也不会是起点到终点的最短路径。

一些结论

  1. 在算法过程中，任意一个节点的f值会不严格地递减。
  2. OPEN表上任一具有f(n) < f*(s)的节点定会被A*扩展。只要某一时刻的f值小于f*(s)都成立。换言之，整个过程中不被扩展的节点，其f值一定恒大于等于f*(s)
  3. A*扩展的任一节点，定有f(n) ≤ f*(s)。整个过程中，open表里的最小f值会上下波动，但是一定小于等于f*(s)（除了最后一步）。
  4. 当h(n)恒等于0时，h为单调的。
  5. 对两种不同的h估计方法，如果 (目标节点除外)，则A1扩展的节点数 A2扩展的节点数，即A2的效果更好。

对5的证明

注意评判标准是扩展的节点数，不是扩展节点的次数。
只需证明被A2扩展的点一定被A1扩展即可，使用反证法：
假设某一个点被A2扩展但没有被A1扩展。
由条件123，可以大略画出A1过程中f值的变化： line-chart 则在A1过程中，的线会向上移，而红线虽然不确定变化方向，但是恒小等f*(s)，这个值是不变的，所以依然不会被A2扩展，假设不成立，证毕。

如果条件是，则结论不一定成立。
考虑f值等于f*(s)的点，其在A1不一定被扩展，但在A2中，可能被扩展，因为黑线不一定上移。

策略优化

单调性

多次对同一个点搜索会降低效率，问题在于第一次找到某个点的路径不一定是最短路径。考虑改进h(n)。 对h(n)增加条件：若是的父节点，则。
增加条件后，若在起点到的最短路径上，则一定先于被搜索。
假如先被搜索，则此时，但同时有和，矛盾。

单调性无法满足时

思考的出发点来源于结论34。对于那些f(n) ≤ f*(s)的点。将其放入一个集合名为NEST中，则它们一定被扩展，那么在扩展这些集合时可以将h定为0，这样满足单调性，提高效率。但是问题是不能知道f*(s)的值，所以用当前扩展的点中最大的点的f值估计。

优化后算法（抄PPT）：

Modified-A-algorithm(s)   //s为初始节点
OPEN=(s), CLOSED=(), f(s)=g(s)+h(s), fm=0;
while OPEN不空 do：
    begin
        NEST={ni|f(ni)<fm,ni∈OPEN}
        if NEST ≠ ( ) 
            n=NEST中g最小的节点
        else 
            n=FIRST(OPEN), fm=f(n);
        if GOAL(n) 
            return n;
        REMOVE(n, OPEN), ADD(n, CLOSED);
        EXPAND(n) →{mi}, 
        计算f(n, mi)=g(n, mi)+h(mi);
        ADD(mj, OPEN), 标记mj到n的指针；
        if f(n, mk)<f(mk)  
            f(mk)=f(n, mk), 标记mk到n的指针；
        if f(n, ml)<f(ml,)
            f(ml)=f(n, ml),标记ml到n的指针, 
            ADD(ml, OPEN);
        OPEN中的节点按f值从小到大排序；
    end while
return FAIL;