搜索进阶

双向搜索

定义

从起点和终点同时开始 BFS，直到两个搜索路径相遇。

实现

• 初始化两个队列，加入起点和终点。
• 分别扩展节点并标记
• 如果扩展出的节点被另一个队列标记过，则结束

vector<Node> nodes;
void doubleBFS(int start, int end){
    // 初始化访问记录
    vector<int> vis(nodes.size(), 0);
    vis[start] = 1;
    vis[end] = 2;
    // 初始化两个队列
    queue<int> q1, q2;
    q1.push(start);
    q2.push(end);
    // 双向搜索
    while(!q1.empty() && !q2.empty()){
        int u1 = q1.front();
        int u2 = q2.front();
        q1.pop();
        q2.pop();
        // 如果两个队列相遇，则结束
        if(vis[u1] == 2 || vis[u2] == 1) return;
        // 标记访问
        vis[u1] = 1;
        vis[u2] = 2;
        // 扩展节点
        for(int v : nodes[u1].neighbors)
            if(!vis[v]) q1.push(v);
        for(int v : nodes[u2].neighbors)
            if(!vis[v]) q2.push(v);
    }
}

优化

优先让较小的队列扩展节点，尽量让两个队列平衡。

void doubleBFS(int start, int end){
    ...
    while(!q1.empty() && !q2.empty()){
        ...
        if(q1.size() > q2.size()){
            int u1 = q1.front();
            ...
        }
        else{
            int u2 = q2.front();
            ...
        }
    }
}

A* 搜索

原理

维护一个优先队列，每个节点有一个估价： $f(n) = g(n) + h(n)$

• $g(n)$：从起点到节点 n 的实际代价（已走过的路）。
• $h(n)$：从节点 n 到目标的启发式估价（预估剩余代价）。
• $f(n)$：预估总代价，每次优先扩展 $f(n)$ 最小的节点。

可纳性

$h(n) \le h^*(n)$，

$h^*(n)$ 为实际剩余代价

估价不可高估实际剩余代价，保证不错过最优解。

一致性

$h(x ) \le h(y) + d(x \to y)$ 即三角不等式，使已弹出节点不会重新入队。

启发函数

1. 曼哈顿距离： $h(n) = |x_1 - x_2| + |y_1 - y_2|$

   适用于网格状地图

2. 欧几里得距离： $h(n) = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$

   适用于二维空间

3. 切比雪夫距离： $h(n) = \max(|x_1 - x_2|, |y_1 - y_2|)$

实现

struct Node {
    int x, y, g, h;
    int f(){return g + h;}
    bool operator<(const Node& other) const {
        return f() > other.f(); // 小顶堆
    }
};
int n, m;
vector<vector<int>> grid;
int sx, sy, tx, ty;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
// 启发函数：曼哈顿距离
int heuristic(int x, int y) {
    return abs(x - tx) + abs(y - ty);
}
int astar() {
    // 初始化
    priority_queue<Node> pq;
    pq.emplace(sx, sy, 0, heuristic(sx, sy));
    vector<vector<bool>> vis(n, vector<bool>(m, false));
    vis[sx][sy] = true;
    // 搜索
    while (!pq.empty()) {
        Node cur = pq.top();
        pq.pop();
        // 找到最优解      
        if (cur.x == tx && cur.y == ty) return cur.g; 
        // 遍历相邻节点    
        for (int i = 0; i < 4; i++) {
            int nx = cur.x + dx[i], ny = cur.y + dy[i];
            // 越界、障碍或已访问
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (grid[nx][ny] || vis[nx][ny]) continue; 
            // 入队
            pq.emplace(nx, ny, cur.g + 1, heuristic(nx, ny));
        }
    }
    return -1; // 未找到解
}

迭代加深

定义

每次限制搜索深度的 DFS，功能类似 BFS 但空间复杂度低。

搜索树越深节点越多，所以反复搜浅层几乎不会增加时间复杂度。

实现

• 进行 dfs，超过深度限制则返回
• 放宽深度限制，继续 dfs

int limit = 0, end = ?;
int dfs(int u, int d){
    // 超限终止
    if(d >= limit) return 0;
    // 找到目标节点
    if(u == end) return end;
    // 搜索子节点
    for(int v : nodes[u].next)
        if(v) dfs(v, d + 1);
}
void IDDFS(){
    // 逐渐增加深度限制
    for(limit = 1; limit <= n; limit++)
        // 搜到目标节点则结束
        if(dfs(start, 0) == end) return;
}

IDA*

迭代加深不限制深度，而是限制总估计代价。