信奥赛C++提高组csp-s之搜索进阶（双向BFS）

信奥赛C++提高组csp-s之搜索进阶（双向BFS）

一、双向广度优先搜索（双向BFS）

1.1 算法原理

双向广度优先搜索是BFS的一种优化算法。传统的单向BFS从起点出发，向四周逐层扩展，直到找到终点，搜索空间随着步数指数级增长（约O ( 2 d ) O(2^d)O(2d)，其中d dd为最短路径长度）。而双向BFS同时从起点和终点两个方向出发，分别进行BFS搜索，直到两个方向的搜索树相遇，此时拼接出来的路径即为最优解。

从搜索量的角度对比：假设最短路径长度为d dd，每步扩展b bb个节点。单向BFS需要搜索b d b^dbd量级的节点，而双向BFS只需要搜索约2 × b d / 2 2 \times b^{d/2}2×bd/2个节点，搜索规模从指数级降低到平方根级。以b = 4 , d = 20 b=4,d=20b=4,d=20为例，双向比单向快约5.2 × 10 5 5.2 \times 10^55.2×105倍。

1.2 适用条件

双向BFS有两个核心前提条件：

1. 起点和终点都必须明确已知：只有同时知道起始状态和目标状态，才能从两端同时出发搜索
2. 状态空间较大的最短路径问题：当搜索深度较深、分支因子较大时，双向BFS的优势尤为明显

典型应用场景包括：八数码问题、迷宫最短路径、字串变换、单词接龙、旋钮机关问题等。

1.3 两种主流实现策略

策略一（交替扩展）：起点和终点先后入队，两个方向的搜索交替扩展子状态，直到两个方向产生相同的子状态时结束。此策略实现简单，但两个方向搜索树生长速度可能不平衡。

策略二（规模优先）：每次选择当前队列规模较小的方向先扩展，使两个方向的搜索进度保持平衡，进一步提升效率。此策略为本文代码所采用。

二、案例研究：八数码难题

题目描述

在3 × 3 3\times 33×3的棋盘上，摆有八个棋子，每个棋子上标有1 11至8 88的某一数字。棋盘中留有一个空格，空格用0 00来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765 123804765123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。

输入格式

输入初始状态，一行九个数字，空格用0 00表示。

输出格式

只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数。保证测试数据中无特殊无法到达目标状态数据。

输入输出样例 1

输入 1

283104765

输出 1

4

说明/提示

样例解释

图中展示了样例当中从初始状态到目标状态的一种方案，共需要4 44步。

并且可以证明，不存在更优的策略。

思路分析

题目理解

在3 × 3 3 \times 33×3的棋盘上摆有8个棋子（标号1~8）和1个空格（用0表示）。空格周围的棋子可以移动到空格中。给定初始布局，目标状态为123804765（将矩阵按行展开成的9位数字），求最少移动次数。

数据保证有解，因此无需考虑无解情况。

为什么选择双向BFS

• 起点和终点都明确已知：初始状态由输入给出，终点状态固定为123804765
• 状态空间较大：9! = 362880 种排列，单向BFS在最坏情况下可能遍历大量节点。实际测试中，单向BFS约8388ms，双向BFS仅228ms，效率提升显著
• 目标状态固定：这是双向BFS最理想的场景

状态表示

将3 × 3 3 \times 33×3棋盘展平为9位十进制整数，例如：

2 8 3 283 1 0 4 -> 104765 7 6 5

这种编码方式便于快速存储和判重，同时方便通过队列传递。

判重机制

维护两个哈希表v（方向标记）和d（步数）：

• v[state] = 1表示该状态由正向（起点→终点）搜索访问过
• v[state] = 2表示该状态由反向（终点→起点）搜索访问过
• v[state] = 0表示该状态尚未被任何方向访问过

当扩展某个状态时，若发现该状态已被另一个方向访问过，则两个方向在此相遇，答案即为d[state1] + d[state2]。

转移方式

每步操作是将空格与相邻棋子交换位置。具体实现时，每次从队首取出一个状态，将其转换回3 × 3 3 \times 33×3矩阵，找到空格位置（值为0的格子），尝试向四个方向移动，生成新的状态并入队。

关键细节：正向和反向的转移规则是对称的，因为移动操作是可逆的（交换两个格子），因此正向和反向可以共用同一套转移逻辑。

复杂度分析

• 时间复杂度：假设最短路径长度为d dd，分支因子约为4，双向BFS扩展节点数约为2 × 4 d / 2 2 \times 4^{d/2}2×4d/2，相比单向BFS的4 d 4^d4d呈指数级优化
• 空间复杂度：需要存储两个方向的已访问状态集合，使用unordered_map时最坏情况O ( 4 d / 2 ) O(4^{d/2})O(4d/2)

代码实现

#include<bits/stdc++.h>usingnamespacestd;// 目标状态：123804765inted=123804765;// 方向数组：上、下、左、右intdx[4]={-1,1,0,0};intdy[4]={0,0,-1,1};// 存储3x3矩阵，下标从1开始inta[4][4];intmain(){intst;scanf("%d",&st);// 特判：起点即终点if(st==ed){printf("0\n");return0;}queue<int>q;// BFS队列unordered_map<int,int>v;// 方向标记：1=正向，2=反向unordered_map<int,int>d;// 步数记录// 初始化：起点和终点同时入队q.push(st);q.push(ed);v[st]=1;v[ed]=2;d[st]=0;d[ed]=1;// 反向起点步数设为1，便于相遇时统一计算while(!q.empty()){intcur=q.front();q.pop();inttmp=cur;// 将9位数字转换为3x3矩阵，同时记录空格位置intx=0,y=0;for(inti=3;i>=1;i--){for(intj=3;j>=1;j--){a[i][j]=tmp%10,tmp/=10;if(a[i][j]==0)x=i,y=j;}}// 向四个方向扩展for(inti=0;i<4;i++){intnx=x+dx[i],ny=y+dy[i];if(nx<1||nx>3||ny<1||ny>3)continue;// 交换空格与相邻棋子swap(a[x][y],a[nx][ny]);// 将新矩阵转换回数字intnxt=0;for(intp=1;p<=3;p++)for(intq=1;q<=3;q++)nxt=nxt*10+a[p][q];// 判重：如果已被当前方向访问过，跳过if(v[nxt]==v[cur]){swap(a[x][y],a[nx][ny]);continue;}// 相遇判断：若被另一方向访问过，输出总步数if(v[nxt]+v[cur]==3){printf("%d\n",d[cur]+d[nxt]);return0;}// 新状态入队v[nxt]=v[cur];d[nxt]=d[cur]+1;q.push(nxt);// 恢复矩阵，继续尝试其他方向swap(a[x][y],a[nx][ny]);}}return0;}

功能分析

1. 状态表示：将3 × 3 3 \times 33×3棋盘压缩为9位整数，便于存储和判重
2. 双向搜索初始化：起点和终点同时入队，分别标记方向1和2，各自记录步数
3. 转移逻辑：每次找到空格位置（值为0的格子），向四个方向尝试交换，生成新状态
4. 相遇判定：当新生成的状态nxt的方向标记与当前状态cur的方向标记之和等于3（即一个来自正向1、一个来自反向2）时，说明两个方向相遇，步数相加即为最少移动次数
5. 代码简洁性：使用unordered_map实现判重，使用swap操作进行状态转移，无需手动恢复状态（交换两次即可还原），实现清晰高效

三、总结

双向BFS的核心价值在于指数级降低搜索规模。其实现要点包括：

更多系列知识，请查看专栏：《信奥赛C++提高组csp-s知识详解及案例实践》：
https://blog.csdn.net/weixin_66461496/category_13113932.html

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

1、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html

2、csp信奥赛冲刺一等奖有效刷题题解：

信奥赛C++普及组csp-j初赛&复赛真题题解（持续更新）https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）
https://blog.csdn.net/weixin_66461496/category_13125089.html

3、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html

4、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}