搜索算法
在百度百科中介绍 搜索算法是利用计算机的高性能来有目的的穷举一个问题解空间的部分或所有的可能情况，从而求出问题的解的一种方法。现阶段一般有枚举算法、深度优先搜索、广度优先搜索、A*算法、回溯算法、蒙特卡洛树搜索、散列函数等算法。在大规模实验环境中，通常通过在搜索前，根据条件降低搜索规模；根据问题的约束条件进行剪枝；利用搜索过程中的中间解，避免重复计算这几种方法进行优化。
这里先介绍搜索算法的深度优先和广度优先
常用在树和图的搜索上面，搜索算法中，也包含我们心心念念的回溯算法，动态规划你可以不会，但是回溯你不能不会。99%的难题，其实都可以用回溯做出来，就算是超时，也能 AC 不少，可谓是刷题面试，人前装B 的必备算法！
深度优先搜索(DFS)算法
深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图。在深度优先搜索中，对于最新发现的顶点，如果它还有以此为起点而未探测到的边，就沿此边继续汉下去。当结点v的所有边都己被探寻过，搜索将回溯到发现结点v有那条边的始结点。这一过程一直进行到已发现从源结点可达的所有结点为止。如果还存在未被发现的结点，则选择其中一个作为源结点并重复以上过程，整个进程反复进行直到所有结点都被发现为止。
简单例题：
排列数字
给定一个整数 nn，将数字 1∼n1∼n 排成一排，将会有很多种排列方法。
现在，请你按照字典序将所有的排列方法输出。
输入格式
共一行，包含一个整数 nn。
输出格式
按字典序输出所有排列方案，每个方案占一行。
数据范围
1≤n≤71≤n≤7
输入样例：
3
输出样例：
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
usingnamespacestd; constintN=10; intn; intpath[N] ; boolst[N]; voiddfs(intu) { if (u==n) { for(inti=0; i<n; i++) {printf("%d ",path[i]);} puts(" "); return ; } for(inti=0;i<=n;i++) { if(!st[i]) { path[u]=i; st[i]=true; dfs(u+1); // path [u] = 0;st[i]=false; } } } intmain() { cin>>n; dfs(0); return0; }
经典例题：
n-皇后问题n−n−皇后问题是指将 nn 个皇后放在 n×nn×n 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。
现在给定整数 nn，请你输出所有的满足条件的棋子摆法。
输入格式
共一行，包含整数 nn。
输出格式
每个解决方案占 nn 行，每行输出一个长度为 nn 的字符串，用来表示完整的棋盘状态。
其中 . 表示某一个位置的方格状态为空，Q 表示某一个位置的方格上摆着皇后。
每个方案输出完成后，输出一个空行。
注意：行末不能有多余空格。
输出方案的顺序任意，只要不重复且没有遗漏即可。
数据范围
1≤n≤91≤n≤9
输入样例：
4
输出样例：
.Q.. ...Q Q... ..Q. ..Q. Q... ...Q .Q..
题解一：
usingnamespacestd; constintN=20; // bool数组用来判断搜索的下一个位置是否可行// col列，dg对角线，udg反对角线// g[N][N]用来存路径intn; charg[N][N]; boolcol[N], dg[N], udg[N]; voiddfs(intu) { // u == n 表示已经搜了n行，故输出这条路径if (u==n) { for (inti=0; i<n; i++ ) puts(g[i]); // 等价于cout << g[i] << endl;puts(""); // 换行return; } // 枚举u这一行，搜索合法的列intx=u; for (inty=0; y<n; y++ ) // 剪枝(对于不满足要求的点，不再继续往下搜索) if (col[y] ==false&&dg[y-x+n] ==false&&udg[y+x] ==false) { col[y] =dg[y-x+n] =udg[y+x] =true; g[x][y] ='Q'; dfs(x+1); g[x][y] ='.'; // 恢复现场col[y] =dg[y-x+n] =udg[y+x] =false; } } intmain() { cin>>n; for (inti=0; i<n; i++ ) for (intj=0; j<n; j++ ) g[i][j] ='.'; dfs(0); return0; }
广度优先搜索（BFS）算法
广度优先搜索算法（Breadth-First Search，BFS）是一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。BFS并不使用经验法则算法。
简单例题：
走迷宫
给定一个 n×mn×m 的二维整数数组，用来表示一个迷宫，数组中只包含 00 或 11，其中 00 表示可以走的路，11 表示不可通过的墙壁。
最初，有一个人位于左上角 (1,1)(1,1) 处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。
请问，该人从左上角移动至右下角 (n,m)(n,m) 处，至少需要移动多少次。
数据保证 (1,1)(1,1) 处和 (n,m)(n,m) 处的数字为 00，且一定至少存在一条通路。
输入格式
第一行包含两个整数 nn 和 mm。
接下来 nn 行，每行包含 mm 个整数（00 或 11），表示完整的二维数组迷宫。
输出格式
输出一个整数，表示从左上角移动至右下角的最少移动次数。
数据范围
1≤n,m≤1001≤n,m≤100
输入样例：
5 5 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0
输出样例：
8
//使用队列的需要用的头文件//使用memset()需要用到的头文件usingnamespacestd; typedefpair<int, int>PII; //定义坐标的数据结构constintN=110; intn, m; intg[N][N]; //记录地图信息intd[N][N]; //记录每个顶点到源点的距离intbfs() { queue<PII>q; //定义一个坐标队列q.push({0,0}); //源点进队memset(d, -1, sizeofd); //初始化各个点到源点的距离为-1d[0][0] =0; //源点到自己的距离为0intdx[4] = {0,1,0,-1}, dy[4] = {1,0,-1,0}; //向四个方向扩展的坐标数组(个人按照[上右下左]的顺序)while(!q.empty()) { autot=q.front(); //取队头元素q.pop(); //队头元素出队for(inti=0; i<4; i++) { //分别向四个方向扩展intx=t.first+dx[i], y=t.second+dy[i]; //扩展后的坐标//首先(x,y)不能越界, 然后g[x][y] == 0说明可以走(g[x][y] == 1说明是障碍物)//最后是只更新未被访问的点到源点的距离 (要求d[x][y] == -1)if(x>=0&&x<n&&y>=0&&y<m&&g[x][y] ==0&&d[x][y] ==-1) { d[x][y] =d[t.first][t.second] +1; //更新未被访问的点到源点的距离q.push({x,y}); //(x,y)进队 } } } returnd[n-1][m-1]; //返回右下角元素到源点的距离} intmain() { cin>>n>>m; for(inti=0; i<n; i++) for(intj=0; j<m; j++) cin>>g[i][j]; //读入地图信息cout<<bfs() <<endl; return0; }
经典例题：
八数码
在一个 3×33×3 的网格中，1∼81∼8 这 88 个数字和一个 x 恰好不重不漏地分布在这 3×33×3 的网格中。
例如：
1 2 3 x 4 6 7 5 8
在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。
我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：
1 2 3 4 5 6 7 8 x
例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。
交换过程如下：
1 2 3 1 2 3 1 2 3 1 2 3 x 4 6 4 x 6 4 5 6 4 5 6 7 5 8 7 5 8 7 x 8 7 8 x
现在，给你一个初始网格，请你求出得到正确排列至少需要进行多少次交换。
输入格式
输入占一行，将 3×33×3 的初始网格描绘出来。
例如，如果初始网格如下所示：
1 2 3 x 4 6 7 5 8
则输入为：1 2 3 x 4 6 7 5 8
输出格式
输出占一行，包含一个整数，表示最少交换次数。
如果不存在解决方案，则输出 −1−1。
输入样例：
2 3 4 1 5 x 7 6 8
输出样例
19
//用变化后的状态以及的对应的变化次数来实现 最终的目标对应的变化次数即是结果//unordered_map的增删改查操作的时间复杂度是O(1);usingnamespacestd; stringstart,c,en; intbfs(stringstart) { en="12345678x";//所求目标状态queue<string>q;//定义队列unordered_map<string,int>d; q.push(start);//入队d[start]=0;//最初没有变化 所以对应的值为0；intdx[4]={-1,1,0,0};intdy[4]={0,0,-1,1};//四方向while(!q.empty()){ autot=q.front();//对头开始操作intdistance=d[t]; if(t==en)returndistance;//找到最终目标 返回变化值q.pop();//对头出队intk=t.find('x');//查找x的下标 //k=x*3+y; 所以对应二维数组的下标 x=k/3;y=k%3;for(inti=0;i<4;i++){//我在此放的x,y分别为移动后的x,y;intx=k/3+dx[i];inty=k%3+dy[i]; if(x>=0&&x<3&&y>=0&&y<3){//在地图范围内 swap(t[k],t[3*x+y]);//交换位置if(d[t]==0){//变换后 且没有对应的该状态（未被拓展）d[t]=distance+1;//变化值+1;q.push(t); } swap(t[k],t[3*x+y]);//还原现场 } } } return-1; } intmain(){ cin.tie(0); ios::sync_with_stdio(0); for(inti=0;i<9;i++){ cin>>c; start+=c; } cout<<bfs(start); }
