双向BFS：八数码问题的高效解法

双向BFS：八数码问题的高效解法

引用

CSDN

1.

https://m.blog.csdn.net/qqqqqwerttwtwe/article/details/145511701

在解决状态空间搜索问题时，广度优先搜索（BFS）是最直观的解法。但当我们面对指数级增长的状态空间时（如八数码问题），传统BFS的时间复杂度会变得难以接受。这时，双向BFS就像一把锋利的手术刀，能精准地切开问题的复杂度。

一、从传统BFS到双向BFS

在解决状态空间搜索问题时，广度优先搜索（BFS）是最直观的解法。但当我们面对指数级增长的状态空间时（如八数码问题），传统BFS的时间复杂度会变得难以接受。这时，双向BFS就像一把锋利的手术刀，能精准地切开问题的复杂度。通俗的讲，BFS像是单向暗恋，从起点开始尝试无数种可能才能了解终点，而双向BFS则是相互了解，双向奔赴的感情，起点和终点相互靠近并在中间相遇

传统BFS的局限：

• 单方向搜索形成爆炸式增长
• 大量无效节点被访问
• 深度较大时效率急剧下降

双向BFS的突破：

• 从起点和终点同时发起搜索
• 两个方向的波浪在中间相遇
• 搜索空间呈几何级数缩减

从下图可以观察到，双向BFS搜索树的宽度会比较小。

二、八数码问题分析

ACWing 八数码问题

问题描述：
在3 × 3的棋盘上，摆放着1-8的数字和一个x（空格）。通过滑动数字块，最终达到目标状态12345678 x。

状态空间：

• 理论最大状态数：9! = 362880
• 实际可达状态数：9!/2 = 181440

移动规则：
每个状态可产生2-4个子状态（取决于空格位置）

示例状态变换：
1 2 3   1 2 3
4 x 5 → 4 5 x
6 7 8   6 7 8

三、双向BFS实现解析

1. 核心数据结构

// 方向数组：右、左、下、上（基于一维数组索引）
const int DX[] = {1, -1, 3, -3};
// 状态节点结构体
struct Node {
    int pos;    // 空格位置（'x'的索引）
    int flag;   // 搜索方向标记（0：正向搜索，1：反向搜索）
    string state; // 当前状态字符串
    Node(int pos, int flag, string state) 
        : pos(pos), flag(flag), state(state) {}
};

2. 算法流程图解

3. 关键代码解析

移动合法性判断：

// 防止越界和跨行移动
// 检查移动是否合法
if (new_pos < 0 || new_pos > 8 || // 越界检查
    abs((new_pos % 3) - (current.pos % 3)) == 2) { // 跨行检查
    continue;
}

双向相遇检测：

// 如果当前状态在另一个方向被访问过，说明相遇
if (step_count[1 - current.flag].count(current.state)) {
    // 总步数 = 正向步数 + 反向步数 - 2（因为起点和终点都记为1）
    return step_count[0][current.state] + step_count[1][current.state] - 2;
}

状态扩展过程：

// 扩展当前节点的邻居
for (int i = 0; i < 4; i++) {
    int new_pos = current.pos + DX[i];
    // 检查移动是否合法
    if (new_pos < 0 || new_pos > 8 || // 越界检查
        abs((new_pos % 3) - (current.pos % 3)) == 2) { // 跨行检查
        continue;
    }
    // 生成新状态
    string new_state = current.state;
    swap(new_state[current.pos], new_state[new_pos]);
    // 如果新状态在当前方向已被访问，跳过
    if (step_count[current.flag].count(new_state)) {
        continue;
    }
    // 记录步数并加入队列
    step_count[current.flag][new_state] = step_count[current.flag][current.state] + 1;
    q.push(Node(new_pos, current.flag, new_state));
}

到这里，双向BFS看似完成了，实际不然，双向BFS存在一个比较大的问题，那就是当局面无解的时候，双向BFS的搜索空间会比单向BFS大两倍。简单理解，就是两个不合适的人拼尽全力之后了解到自己和对方不合适（bushi）。面对这种情况，我们需要根据问题设计早停机制，及时止损。对于八数码问题，解绝对不会超过36步，为此，我们在双向BFS是设定层数为18，超出则返回无解。

完整代码

#include <iostream>
#include <queue>
#include <unordered_map>
#include <string>
using namespace std;
// 目标状态
const string TARGET = "12345678x";
// 方向数组：右、左、下、上（基于一维数组索引）
const int DX[] = {1, -1, 3, -3};
// 状态节点结构体
struct Node {
    int pos;    // 空格位置（'x'的索引）
    int flag;   // 搜索方向标记（0：正向搜索，1：反向搜索）
    string state; // 当前状态字符串
    Node(int pos, int flag, string state) 
        : pos(pos), flag(flag), state(state) {}
};
// 双向BFS函数
int bidirectional_bfs(int start_pos, const string& start_state) {
    // 双队列：分别用于正向和反向搜索
    queue<Node> q;
    // 双哈希表：记录每个状态从起点或终点的步数
    unordered_map<string, int> step_count[2];
    // 初始化正向搜索
    q.push(Node(start_pos, 0, start_state));
    step_count[0][start_state] = 1; // 起点步数为1
    // 初始化反向搜索
    q.push(Node(8, 1, TARGET));
    step_count[1][TARGET] = 1; // 终点步数为1
    while (!q.empty()) {
        Node current = q.front();
        q.pop();
        
        if(step_count[current.flag][current.state] > 18)
            return -1;
        // 如果当前状态在另一个方向被访问过，说明相遇
        if (step_count[1 - current.flag].count(current.state)) {
            // 总步数 = 正向步数 + 反向步数 - 2（因为起点和终点都记为1）
            return step_count[0][current.state] + step_count[1][current.state] - 2;
        }
        // 扩展当前节点的邻居
        for (int i = 0; i < 4; i++) {
            int new_pos = current.pos + DX[i];
            // 检查移动是否合法
            if (new_pos < 0 || new_pos > 8 || // 越界检查
                abs((new_pos % 3) - (current.pos % 3)) == 2) { // 跨行检查
                continue;
            }
            // 生成新状态
            string new_state = current.state;
            swap(new_state[current.pos], new_state[new_pos]);
            // 如果新状态在当前方向已被访问，跳过
            if (step_count[current.flag].count(new_state)) {
                continue;
            }
            // 记录步数并加入队列
            step_count[current.flag][new_state] = step_count[current.flag][current.state] + 1;
            q.push(Node(new_pos, current.flag, new_state));
        }
    }
    // 未找到解
    return -1;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string start_state; // 初始状态
    int start_pos = -1; // 初始空格位置
    // 读取输入
    for (int i = 0; i < 9; i++) {
        string c;
        cin >> c;
        if (c == "x") {
            start_pos = i; // 记录空格位置
        }
        start_state += c; // 拼接初始状态
    }
    // 调用双向BFS求解
    int result = bidirectional_bfs(start_pos, start_state);
    cout << result << endl;
    return 0;
}

四、性能优化策略

1. 交替扩展策略
   每次选择较小的队列进行扩展，保持搜索平衡

2. 剪枝优化
   设置最大步数阈值（示例代码中为18步）

3. 高效哈希
   使用字符串直接哈希，O(1)时间复杂度查询

4. 空间压缩
   使用两个bit标记访问状态（0:未访问，1:正向访问，2:逆向访问）

五、复杂度对比

可以看出，双向BFS带来的性能提升还是比较大的。

六、应用场景扩展

1. 单词接龙问题
2. 基因序列比对
3. 社交网络关系链查找
4. 迷宫最短路径问题

七、算法演进展望

1. 启发式双向搜索
   结合A*算法与双向搜索

2. 并行化实现
   利用多核优势加速搜索

3. 机器学习引导
   预测更优的扩展方向

// 示例：启发式双向搜索伪代码
priority_queue<Node> q[2]; // 带优先级的队列

结语

双向BFS通过巧妙的双向夹逼策略，在八数码问题中展现了惊人的效率。这种算法思想启示我们：当面对复杂问题时，换个角度思考，往往能找到突破困境的新路径。正如计算机科学大师Dijkstra所说：“问题的解决往往不在于更强的算力，而在于更聪明的策略。”