A_搜索(A Star)算法

A*搜索(A Star)

不同于盲目搜索，A算法是一种启发式算法(Heuristic Algorithm)。
上文提到，盲目搜索对于所有要搜索的状态结点都是一视同仁的，因此在每次搜索一个状态时，盲目搜索并不会考虑这个状态到底是有利于趋向目标的，还是偏离目标的。
而启发式搜索的启发二字，看起来是不是感觉这个算法就变得聪明一点了呢？正是这样，启发式搜索对于待搜索的状态会进行不同的优劣判断，这个判断的结果将会对算法搜索顺序起到一种启发作用，越优秀的状态将会得到越高的搜索优先级。
我们把对于状态优劣判断的方法称为启发函数*，通过给它评定一个搜索代价来量化启发值。
启发函数应针对不同的使用场景来设计，那么在拼图的游戏中，如何评定某个状态的优劣性呢？粗略的评估方法有两种：

1. 可以想到，某个状态它的方块位置放对的越多，说明它能复原目标的希望就越大，这个状态就越优秀，优先选择它就能减少无效的搜索，经过它而推演到目标的代价就会小。所以可求出某个状态所有方块的错位数量来作为评估值，错位越少，状态越优秀。
2. 假如让拼图上的每个方块都可以穿过邻近方块，无阻碍地移动到目标位置，那么每个不在正确位置上的方块它距离正确位置都会存在一个移动距离，这个非直线的距离即为曼哈顿距离(Manhattan Distance)，我们把每个方块距离其正确位置的曼哈顿距离相加起来，所求的和可以作为搜索代价的值，值越小则可认为状态越优秀。

其实上述两种评定方法都只是对当前状态距离目标状态的代价评估，我们还忽略了一点，就是这个状态距离搜索开始的状态是否已经非常远了，亦即状态结点的深度值。
在拼图游戏中，我们进行的是路径搜索，假如搜索出来的一条移动路径其需要的步数非常多，即使最终能够把拼图复原，那也不是我们希望的路径。所以，路径搜索存在一个最优解的问题，搜索出来的路径所需要移动的步数越少，就越优。
A*算法对某个状态结点的评估，应综合考虑这个结点距离开始结点的代价与距离目标结点的代价。总估价公式可以表示为：

f(n) = g(n) + h(n)
1

n 表示某个结点，f(n) 表示对某个结点进行评价，值等于这个结点距离开始结点的已知价 g(n) 加上距离目标结点的估算价 h(n)。
为什么说 g(n) 的值是确定已知的呢？在每次生成子状态结点时，子状态的 g 值应在它父状态的基础上 +1，以此表示距离开始状态增加了一步，即深度加深了。所以每一个状态的 g 值并不需要估算，是实实在在确定的值。
影响算法效率的关键点在于 h(n) 的计算，采用不同的方法来计算 h 值将会让算法产生巨大的差异。

• 当增大 h 值的权重，即让 h 值远超 g 值时，算法偏向于快速寻找到目标状态，而忽略路径长度，这样搜索出来的结果就很难保证是最优解了，意味着可能会多绕一些弯路，通往目标状态的步数会比较多。
• 当减小 h 值的权重，降低启发信息量，算法将偏向于注重已搜深度，当 h(n) 恒为 0 时，A*算法其实已退化为广度优先搜索了。(这是为照应上文的方便说法。严谨的说法应是退化为 Dijkstra 算法，在本游戏中，广搜可等同为 Dijkstra 算法，关于 Dijkstra 这里不作深入展开。)

以下是拼图状态结点 PuzzleStatus 的估价方法，在实际测试中，使用方块错位数量来作估价的效果不太明显，所以这里只使用曼哈顿距离来作为 **h(n)** 估价，已能达到不错的算法效率。

/// 估算从当前状态到目标状态的代价
- (NSInteger)estimateToTargetStatus:(id<JXPathSearcherStatus>)targetStatus {
    PuzzleStatus *target = (PuzzleStatus *)targetStatus;
    
    // 计算每一个方块距离它正确位置的距离
    // 曼哈顿距离
    NSInteger manhattanDistance = 0;
    for (NSInteger index = 0; index < self.pieceArray.count; ++ index) {
        // 略过空格
        if (index == self.emptyIndex) {
            continue;
        }
        
        PuzzlePiece *currentPiece = self.pieceArray[index];
        PuzzlePiece *targetPiece = target.pieceArray[index];
        
        manhattanDistance +=
        ABS([self rowOfIndex:currentPiece.ID] - [target rowOfIndex:targetPiece.ID]) +
        ABS([self colOfIndex:currentPiece.ID] - [target colOfIndex:targetPiece.ID]);
    }
    
    // 增大权重
    return 5 * manhattanDistance;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

状态估价由状态类自己负责，A算法只询问状态的估价结果，并进行 f(n) = g(n) + h(b) 操作，确保每一次搜索，都是待搜空间里代价最小的状态，即 f 值最小的状态。
那么问题来了，在给每个状态都计算并赋予上 **f** 值后，如何做到每一次只取 **f** 值最小的那个？
前文已讲到，所有扩展出来的新状态都会放入开放队列中的，如果 A算法也像广搜那样只放在队列尾，然后每次只取队首元素来搜索的话，那么 f 值完全没有起到作用。
事实上，因为每个状态都有 f 值的存在，它们已经有了优劣高下之分，队列在存取它们的时候，应当按其 f 值而有选择地进行入列出列，这时候需要用到优先队列(Priority Queue)，它能够每次出列优先级最高的元素。
以下是 A*搜索算法的代码实现：

- (NSMutableArray *)search {
    if (!self.startStatus || !self.targetStatus || !self.equalComparator) {
        return nil;
    }
    NSMutableArray *path = [NSMutableArray array];
    [(id<JXAStarSearcherStatus>)[self startStatus] setGValue:0];
    
    // 关闭堆，存放已搜索过的状态
    NSMutableDictionary *close = [NSMutableDictionary dictionary];
    // 开放队列，存放由已搜索过的状态所扩展出来的未搜索状态
    // 使用优先队列
    JXPriorityQueue *open = [JXPriorityQueue queueWithComparator:^NSComparisonResult(id<JXAStarSearcherStatus> obj1, id<JXAStarSearcherStatus> obj2) {
        if ([obj1 fValue] == [obj2 fValue]) {
            return NSOrderedSame;
        }
        // f值越小，优先级越高
        return [obj1 fValue] < [obj2 fValue] ? NSOrderedDescending : NSOrderedAscending;
    }];
    
    [open enQueue:self.startStatus];
    
    while (open.count > 0) {
        // 出列
        id status = [open deQueue];
        
        // 排除已经搜索过的状态
        NSString *statusIdentifier = [status statusIdentifier];
        if (close[statusIdentifier]) {
            continue;
        }
        close[statusIdentifier] = status;
        
        // 如果找到目标状态
        if (self.equalComparator(self.targetStatus, status)) {
            path = [self constructPathWithStatus:status isLast:YES];
            break;
        }
        
        // 否则，扩展出子状态
        NSMutableArray *childStatus = [status childStatus];
        // 对各个子状进行代价估算
        [childStatus enumerateObjectsUsingBlock:^(id<JXAStarSearcherStatus>  _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
            // 子状态的实际代价比本状态大1
            [obj setGValue:[status gValue] + 1];
            // 估算到目标状态的代价
            [obj setHValue:[obj estimateToTargetStatus:self.targetStatus]];
            // 总价=已知代价+未知估算代价
            [obj setFValue:[obj gValue] + [obj hValue]];
            
            // 入列
            [open enQueue:obj];
        }];
    }
    NSLog(@"总共搜索: %@", @(close.count));
    return path;
}
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

可以看到，代码基本是以广搜为模块，加入了 f(n) = g(n) + h(b) 的操作，并且使用了优先队列作为开放表，这样改进后，算法的效率是不可同日而语。