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

信奥赛C提高组csp-s之搜索进阶双向BFS一、双向广度优先搜索双向BFS1.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 b4,d20b4,d20为例双向比单向快约5.2 × 10 5 5.2 \times 10^55.2×105倍。1.2 适用条件双向BFS有两个核心前提条件起点和终点都必须明确已知只有同时知道起始状态和目标状态才能从两端同时出发搜索状态空间较大的最短路径问题当搜索深度较深、分支因子较大时双向BFS的优势尤为明显典型应用场景包括八数码问题、迷宫最短路径、字串变换、单词接龙、旋钮机关问题等。1.3 两种主流实现策略策略一交替扩展起点和终点先后入队两个方向的搜索交替扩展子状态直到两个方向产生相同的子状态时结束。此策略实现简单但两个方向搜索树生长速度可能不平衡。策略二规模优先每次选择当前队列规模较小的方向先扩展使两个方向的搜索进度保持平衡进一步提升效率。此策略为本文代码所采用。二、案例研究八数码难题题目描述在3 × 3 3\times 33×3的棋盘上摆有八个棋子每个棋子上标有1 11至8 88的某一数字。棋盘中留有一个空格空格用0 00来表示。空格周围的棋子可以移到空格中。要求解的问题是给出一种初始布局初始状态和目标布局为了使题目简单,设目标状态为123804765 123804765123804765找到一种最少步骤的移动方法实现从初始布局到目标布局的转变。输入格式输入初始状态一行九个数字空格用0 00表示。输出格式只有一行该行只有一个数字表示从初始状态到目标状态需要的最少移动次数。保证测试数据中无特殊无法到达目标状态数据。输入输出样例 1输入 1283104765输出 14说明/提示样例解释图中展示了样例当中从初始状态到目标状态的一种方案共需要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)代码实现#includebits/stdc.husingnamespacestd;// 目标状态123804765inted123804765;// 方向数组上、下、左、右intdx[4]{-1,1,0,0};intdy[4]{0,0,-1,1};// 存储3x3矩阵下标从1开始inta[4][4];intmain(){intst;scanf(%d,st);// 特判起点即终点if(sted){printf(0\n);return0;}queueintq;// BFS队列unordered_mapint,intv;// 方向标记1正向2反向unordered_mapint,intd;// 步数记录// 初始化起点和终点同时入队q.push(st);q.push(ed);v[st]1;v[ed]2;d[st]0;d[ed]1;// 反向起点步数设为1便于相遇时统一计算while(!q.empty()){intcurq.front();q.pop();inttmpcur;// 将9位数字转换为3x3矩阵同时记录空格位置intx0,y0;for(inti3;i1;i--){for(intj3;j1;j--){a[i][j]tmp%10,tmp/10;if(a[i][j]0)xi,yj;}}// 向四个方向扩展for(inti0;i4;i){intnxxdx[i],nyydy[i];if(nx1||nx3||ny1||ny3)continue;// 交换空格与相邻棋子swap(a[x][y],a[nx][ny]);// 将新矩阵转换回数字intnxt0;for(intp1;p3;p)for(intq1;q3;q)nxtnxt*10a[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;}功能分析状态表示将3 × 3 3 \times 33×3棋盘压缩为9位整数便于存储和判重双向搜索初始化起点和终点同时入队分别标记方向1和2各自记录步数转移逻辑每次找到空格位置值为0的格子向四个方向尝试交换生成新状态相遇判定当新生成的状态nxt的方向标记与当前状态cur的方向标记之和等于3即一个来自正向1、一个来自反向2时说明两个方向相遇步数相加即为最少移动次数代码简洁性使用unordered_map实现判重使用swap操作进行状态转移无需手动恢复状态交换两次即可还原实现清晰高效三、总结双向BFS的核心价值在于指数级降低搜索规模。其实现要点包括要素说明适用范围起点和终点均明确的最短路径问题状态表示选择紧凑的编码方式数字压缩、位运算等判重机制使用哈希表记录方向标记和步数平衡策略每次选择队列较小的方向扩展保持双向搜索均衡相遇判定当某状态被两个方向都访问过时拼接路径得到最优解更多系列知识请查看专栏《信奥赛C提高组csp-s知识详解及案例实践》https://blog.csdn.net/weixin_66461496/category_13113932.html各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}1、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html2、csp信奥赛冲刺一等奖有效刷题题解信奥赛C普及组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html3、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.html4、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}