第9章 搜索计算

搜索算法概论搜索算法是计算机解题中的“万能解题法”，尤其适用于那些没有有效算法的问题。在本章中，我们将学习搜索的基本概念、深度优先搜索（DFS）、广度优先搜索（BFS）以及重要的回溯法，并通过经典的排列、子集和、迷宫等问题来掌握它们的应用。第9章搜索目录9.1搜索基础9.2回溯法9.3深搜与广搜9.1.1搜索概述定义：一种“万能解题法”，主要用于解决那些没有已知有效算法的问题。定义核心思想：在解空间中进行有组织地枚举，并通过“剪枝”策略避免无意义的搜索，从而显著提高效率。核心思想与暴力枚举的关系：搜索本质上是一种更高效、更有条理的枚举方式，相比暴力枚举减少了大量无效尝试。与暴力枚举的关系9.1.2全排列与解空间树全排列问题：枚举所有可能的排列组合，是理解搜索算法的经典案例。解空间树：解空间的一种树形组织形式，直观展示了解的逐步生成过程与状态空间。剪枝：在搜索过程中，通过约束条件提前判断并放弃不可能得到解的路径，从而大幅减少无效搜索，提高效率。三位数字全排列的解空间树示意图深度优先搜索（DFS）：沿着一条路径尽可能深地搜索，直到尽头再回溯。通常用递归或栈实现。广度优先搜索（BFS）：从根节点开始，“齐头并进”地搜索所有分支。通常用队列实现。回溯法：深搜的一种常见形式，强调“探索与撤销”，通过状态管理来穷举所有可能解。9.1.3深搜、广搜与回溯向前探索，发现错误就退回一步重新选择，反复进行直到找到解。基本思想包含“搜索”和“回溯”两大步骤，核心是“修改→递归→恢复”的三段式结构。算法框架排列组合、图与棋盘问题、人机对弈、决策问题等场景。典型应用9.2.1回溯法概述算法框架：voidSearch(intk)//第k步操作{if(到达目的地){输出解;return;}for(i=1;i<=本步可选方案总数;i++)if(第i种选法能够满足条件) //剪枝{

保存结果 //保存第k步的选择Search(k+1);

//进入第k+1步

回溯 //退回第k步的初始状态

}}问题描述：从n个整数中取出r个进行排列，列出所有可能。解题思路：通过交换元素来选择当前位置的数字（破坏现场），递归处理下一个位置，递归返回后再交换回来（恢复现场）。9.2.2排列问题voidsearch(intk)//参数k表示进行第k步选择{if(k>r)

{输出排列方案；return;}//已经选够了r位数

for(inti=k;i<=n;i++)//选择第k个字符{

swap(a[i],a[k]); //交换元素

search(k+1); //进入下一步

swap(a[i],a[k]); //恢复现场

}}问题描述：找出集合中所有和为给定值W的子集。解题思路：对每个元素，有选与不选两种选择。通过剪枝（左子树剪枝和右子树剪枝）来避免无效搜索。剪枝策略：若已选元素和超过W，则剪去左子树；若剩余元素和不足以达到W，则剪去右子树。子集和问题的解空间树9.2.3子集和问题程序核心代码：回溯法实现子集和问题（含剪枝）voiddfs(inti,intsum1,intsum2){if(i==n){...}//输出满足条件的解并结束if(sum1+w[i]<=W)//左子树剪枝：选择当前元素不超限{

x[i]=1;dfs(i+1,sum1+w[i],sum2-w[i]);}if(sum1+sum2>W)//右子树剪枝：不选当前元素仍有希望{x[i]=0;dfs(i+1,sum1,sum2-w[i]);}}子集和问题程序实现代码说明：1.左子树剪枝：判断加入当前元素后总和是否超过目标值W，若未超过则递归。2.右子树剪枝：判断即使不选当前元素，剩余元素的和加上已选和是否仍大于W，若是则递归。栈（stack）特性：先进后出，常用于实现深度优先搜索（循环方式）。常用操作：push(),pop(),top(),empty()队列（queue）特性：先进先出，常用于实现广度优先搜索。常用操作：push(),pop(),front(),back(),empty()9.3.1STL中的栈与队列9.3.2迷宫类问题问题描述在迷宫中找到从入口到出口的路径。问题分类1.寻找出口：找到任意一条可行路径，DFS和BFS均可。2.寻找最短路径：找到从入口到出口的最短路径，必须使用BFS。迷宫结构示意图问题：给定一个迷宫，求从左上角走到右下角最少需要走多少步？解题思路：使用队列来管理待探索的节点，从起点开始，依次探索其周围的节点，直到找到终点。搜索过程：像水波纹一样，从起点开始，一层一层地向外扩散，确保最先到达终点的路径是最短的。9.3.3广度优先搜索（迷宫最短路径）广度优先搜索迷宫路径过程迷宫最短路径广搜程序实现intbfs(intx,inty){queue<Node>q;q.push({x,y,1});a[x][y]='#';//标记为已访问while(!q.empty())

{Nodenode=q.front();q.pop();

//取队列首元素if(node.x==r&&node.y==c)returnnode.step;

//到达终点for(inti=0;i<4;++i)

//遍历四个方向

{inttx=node.x+f[i][0],ty=node.y+f[i][1];if(tx<1||tx>r||ty<1||ty>c||a[tx][ty]=='#')continue;a[tx][ty]='#';

//将新增的路径点设置为墙，以免重复进入q.push({tx,ty,node.step+1});

//将新增的路径点加入队列}}return-1;

//没有任何路径能到达出口时}迷宫最短路径BFS核心代码问题：给定一个迷宫，寻找从入口到出口的一条路径。解题思路：使用深度优先搜索即可，深搜可以使用递归模式来实现，也可以使用”栈+循环”模式来实现，本处选择使用”栈+循环”模式。9.3.4深度优先搜索搜索过程：while（栈非空）{

if(栈顶元素是出口){

输出路径;

结束;}else{

针对栈顶元素，在其四周寻找一个从未走过并且是“路”的单元格 if(