广度优先搜索(Breadth First Search, BFS)算法

广度优先搜索(Breadth First Search, BFS)

广度优先搜索是一种盲目搜索算法，它认为所有状态(或者说结点)都是等价的，不存在优劣之分。

假如我们把所有需要搜索的状态组成一棵树来看，广搜就是一层搜完再搜下一层，直到找出目标结点，或搜完整棵树为止。

1. 我们可以使用一个先进先出(First Input First Output, FIFO)的队列来存放待搜索的状态，这个队列可以给它一个名称叫开放队列，也有人把它叫做开放列表(Open List)。
2. 然后还需要把所有已搜索过的状态记录下来，以确保不会对已搜索过的状态作重复扩展，注意这里的扩展即为衍生出子状态，对应于拼图游戏来说就是空格移动了一格。
   由于每搜到一个状态，都需要拿着这个状态去已搜记录中查询是否有这个状态存在，那么已搜记录要使用怎样的存储方式才能适应这种高频率查找需求呢？
   假如我们使用数组来存储所有已搜记录，那么每一次查找都需要遍历整个数组。当已搜记录表的数据有 10 万条时，再去搜一个新状态，就需要做 10 万次循环来确定新状态是从来没有被搜索过的。显然这样做的效率是非常低的。
   一种高效的方法是哈希策略，**哈希表(Hash Table)**能通过键值映射直接查找到目标对象，免去遍历整个存储空间。在 Cocoa 框架中，已经有能满足这种键值映射的数据结构–字典。这里我没有再去实现一个哈希表，而是使用 NSMutableDictionary 来存放已搜记录。我们可以给这个存储空间起个名字叫关闭堆，也有人把它叫做关闭列表(Close List)。
3. 搜索开始时，开放队列是空的，然后我们把起始状态入队，此时开放队列有了一个待搜索的状态，搜索循环开始。
4. 每一次循环的目的，就是搜索一个状态。所谓搜索，前面已经讲过，可以通俗理解为就是比较。我们需要从开放队列中取出一个状态来，假如取出的状态是已经比较过了的，则放弃此次循环，直到取出一个从来没有比较过的状态。
5. 拿着取出的新状态，与目标状态比较，如果一致，则说明路径已找到。为何说路径已找到了呢？因为每一个状态都持有一个父状态的引用，意思是它记录着自己是来源于哪一个状态衍生出来的，所以每一个状态都必然知道自己上一个状态是谁，除了开始状态。
6. 找到目标状态后，就可以构建路径。所谓路径，就是从开始状态到目标状态的搜索过程中，经过的所有状态连起来组成的数组。我们可以从搜索结束的状态开始，把它放入数组中，然后把这个状态的父状态放入数组中，再把其祖先状态放入数组中，直到放入开始状态。如何识别出开始状态呢？当发现某个状态是没有父状态的，就说明了它是开始状态。最后算法把构建完成的路径作为结果返回。
7. 在第 5 步中，如果发现取出的新状态并非目标状态，这时就需要衍生新的状态来推进搜索。调用生成子状态的方法，把产生的子状态入队，依次追加到队列尾，这些入队的子状态将会在以后的循环中被搜索。由于队列的 FIFO 特性，在循环进行过程中，将会优先把某个状态的子状态全部出列完后，再出列其子状态的子状态。入列和出列的两步操作决定了算法的搜索顺序，这里的操作实现了广度优先搜索。

广度优先搜索：

- (NSMutableArray *)search {
    if (!self.startStatus || !self.targetStatus || !self.equalComparator) {
        return nil;
    }
    NSMutableArray *path = [NSMutableArray array];
    
    // 关闭堆，存放已搜索过的状态
    NSMutableDictionary *close = [NSMutableDictionary dictionary];
    // 开放队列，存放由已搜索过的状态所扩展出来的未搜索状态
    NSMutableArray *open = [NSMutableArray array];
    
    [open addObject:self.startStatus];
    
    while (open.count > 0) {
        // 出列
        id status = [open firstObject];
        [open removeObjectAtIndex:0];
        
        // 排除已经搜索过的状态
        NSString *statusIdentifier = [status statusIdentifier];
        if (close[statusIdentifier]) {
            continue;
        }
        close[statusIdentifier] = status;
        
        // 如果找到目标状态
        if (self.equalComparator(self.targetStatus, status)) {
            path = [self constructPathWithStatus:status isLast:YES];
            break;
        }
        
        // 否则，扩展出子状态
        [open addObjectsFromArray:[status childStatus]];
    }
    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

构建路径：

/// 构建路径。isLast表示传入的status是否路径的最后一个元素
- (NSMutableArray *)constructPathWithStatus:(id<JXPathSearcherStatus>)status isLast:(BOOL)isLast {
    NSMutableArray *path = [NSMutableArray array];
    if (!status) {
        return path;
    }
    
    do {
        if (isLast) {
            [path insertObject:status atIndex:0];
        }
        else {
            [path addObject:status];
        }
        status = [status parentStatus];
    } while (status);
    return path;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18