做网站行业现状,做商城网站的公司推荐,高端网站建设成都,西安电脑网站建设深度优先搜索
广度优先搜索
深搜与广搜的区别 深搜 dfs——回溯——“不撞南墙不回头”
思路
总的来说是不撞南墙不回头#xff0c;相当于一个人严格按照固定的行为模式。
例如走方格#xff0c;依次走上下左右#xff0c;每次走到一个新格子记录自己已经走过的方向相当于一个人严格按照固定的行为模式。
例如走方格依次走上下左右每次走到一个新格子记录自己已经走过的方向当到达终点或是所有方向走完之后会重新回到上一格代表上一格此方向【之前按照哪个方向到达此格的方向】的遍历完成。
形成效果
一个dfs其实是对一个问题的结果集的所有解题情况的遍历【不管这个解题情况是否复合题意】。
dfs 搜索树与回溯
一个dfs其实是对一个问题的结果集的所有解题情况的遍历在遍历过程中前面解题情况的选择会影响到后面的解题情况。
例如走迷宫解题情况其实就是主人公走到哪个格子他会影响到之后走过的路径。
所以我们其实可以将解题情况进行串联将前面的选择作为一个图的前驱节点而后面的结果作为后继节点那么所有的解题情况的遍历便可以组成一个树我们叫做搜索树。树上的根节点到 某个叶节点的一条路径就是一条解题过程。
那迷宫来进行距离我们把主人公当前正在走的点当作前驱而之后依照行为模式工作后所走到的下一个点作为后继。那么所有所走过的路径的集合便可构成一个树。
在dfs遍历解题结果的过程中会存储并改变一些解题的状态由于我们是会对所有情况依次进行遍历当一种情况遍历完成后dfs应该回到上一个节点进行行为模式的继续遍历。
例如迷宫走到死胡同或者终点时应该回到上一次走过的点看其他方向能否到达终点。
注意dfs是进行所有结果的遍历所以在到达终点后并不会停止而是会继续回到上一步运行。
而此时回到上一个节点就意味着之前走过的一些点在这个时刻应该是没有走过的所以的话在写代码的时候应该进行一个状态的回溯。在回到上一个节点之前本节点对于上一个节点应该是没有遍历过的所以要进行状态改变。
代码模板
人走迷宫迷宫情况使用0、1表示1可行0不可行。先给定起点与终点求所有路径中最少要走多少格子。
递归实现
#includestdio.h
_Bool map[100][100] { 0 };//1代表可行0不可行
_Bool visit[100][100] { 0 };//0未走1走过
int mov[4][2] { {0,1},{1,0},{0,-1},{-1,0} };//右下左上
int endx, endy, startx, starty;
int col, row, t;
_Bool can 0;
int min 0x3f3f3f3f;//代表正无穷
void dfs(int x,int y, int value) {//如果value没有被设为参数回溯的时候需要改变value值if (value min)//最优剪枝1return;if (x0 || y0 || xrow || ycol)//判断是否出界return;if (x endx y endy) {//结束条件找到终点can 1;if (value min)min value;return;//回退防止继续走下去已经到达终点了没必要再走了}if (value min)//最优剪枝2,未到达终点便valuemin那么到达终点时一定回valueminreturn;for (int i 0;i 4;i) {int xx x mov[i][0], yy y mov[i][1];//人物偏移if (map[xx][yy] !visit[xx][yy]) {//判断是否可以进入下一格可行性剪枝visit[xx][yy] 1;//先标记再访问dfs(xx, yy, value1);//让人物移动到下一格visit[xx][yy] 0;//回溯操作当递归回到这一层的时候(xx,yy)应该未访问所以置为0//回溯操作是一层递归一层递归进行回溯每次只会回溯到上一层所以每次只用将当前位置的下一个操作的数据回溯}}
}
int main() {scanf(%d, t);while (t--) {//t轮数据每一次数据进行操作时都要保证所有的状态都为最初状态不被上一次操作所影响scanf(%d%d, col, row);for (int i 0;i row;i)for (int j 0;j col;j) {scanf(%d, map[i][j]);visit[i][j] 0;}scanf(%d%d%d%d, startx, starty, endx, endy);visit[startx][starty] 1;dfs(startx, starty, 0);if (can)printf(能,min%d\n, min);elseprintf(不能\n);_Bool can 0;}return 0;
}
栈实现
#includeiostream
#includecstdio
#includestack
using namespace std;
struct Point {int x, y, value, dir;Point(int a,int b,int value):x(a),y(b),value(value),dir(0){}
};
typedef struct Point TYPE;
int main(void) {stackTYPE Stack;//这个类可以用指定里面的内容的类型类似于一个栈bool map[100][100] { 0 }, visited[100][100] { 0 };int mov[4][2] { {0,1},{0,-1},{1,0},{-1,0} };int m, n;cin m n;int i, j;for (i 0;i m;i)for (j 0;j n; j)cin map[i][j];int startx, starty, endx, endy;scanf(%d%d%d%d, startx, starty, endx, endy);Stack.emplace(startx, starty, 0);visited[startx][starty] 1;while (!Stack.empty()) {//栈非空进行循环TYPE* cur Stack.top();if (cur-x endx cur-y endy) {//判断是否到达终点printf(%d\n, cur-value);visited[cur-x][cur-y] 0;Stack.pop();continue;//如果到达弹栈回到上一次位置进行下一轮循环}if (cur-dir 3) {//遍历int xx cur-x mov[cur-dir][0];int yy cur-y mov[cur-dir][1];cur-dir;//进入一个新的结点的时候dir0当遍历之后要自增if (xx m yy n xx 0 yy 0 !visited[xx][yy] !map[xx][yy]) {Stack.emplace(xx, yy, cur-value 1);//压栈visited[xx][yy] 1;}}else {//弹栈visited[cur-x][cur-y] 0;Stack.pop();}}return 0;
}
与模板差异
是否回溯遍历方向结束条件结束处理
超时后的解决方法
换思路主要换遍历的方式【mov之类的】剪枝
普通无回溯 dfs
例题
海战 - 洛谷
该题与走迷宫不同走迷宫是从一个点为起点然后一直走下去每走完一种情况后需要回过头检查是否有其他路可走需要进行回溯。该题是需要遍历每一个点若该点是船只的一部分需要判断该点是否可以与其它点相连构成船只且每个点只能使用一次【使用过之后就不能再次使用】走到头后不需要回过头检查其他的路径所以不需要回溯。
#includestdio.h
int R, C, S 0;
char map[1005][1005] { 0 };
int mov[4][2] { {-1,0},{1,0},{0,-1},{0,1} };
void dfs(int x, int y) {map[x][y] .;//因为每只船只能使用一次所以在使用之后要将‘#’标记为‘.’后期不可以再使用for (int i 0;i 4;i) {int xx x mov[i][0], yy y mov[i][1];if (xx 0 xx R yy 0 yy C map[xx][yy] #) {dfs(xx, yy);}}return;
}
//判断船的位置是否合法即在一个正方形中四个角上如果有三个角有船就是不合理的那样子会出现一个三角形不是方形
_Bool d(int i, int j) {int c 0;if (map[i][j] #)c;if (map[i 1][j] #)c;if (map[i][j 1] #)c;if (map[i 1][j 1] #)c;if (c 3)return 0;return 1;
}
int main() {scanf(%d%d, R, C);for (int i 0;i R;i) {scanf(%s, map[i]);}for (int i 0;i R;i) {for (int j 0;j C;j) {if (d(i, j) 0) {printf(Bad placement.);return 0;}}}for (int i 0;i R;i) {for (int j 0;j C;j) {if (map[i][j] #) {S;dfs(i, j);}}}printf(There are %d ships., S);return 0;
}
剪枝
在搜索树中剪去多余枝干。
另一个结束递归的条件
可行性剪枝(判断可不可以走包括有无障碍物和是否走过……)最优剪枝(消耗的能量若目前未到终点但是使用的能量已经超过min)奇偶性剪枝优化搜索顺序(人眼看)冗余剪枝记忆化搜索α-β剪枝(博弈算法可能被人工智能使用)
优化搜索顺序
靠数学功底
可行性剪枝
就像上面的迷宫问题能否走这个格子就是一个可行性剪枝。这个是根据题意来进行判断看下一步路线是否可能符合题意若直接违背则就不用走。
最优剪枝
适用于求最短路径
例题
[USACO2.1] 健康的荷斯坦奶牛 Healthy Holsteins - 洛谷
#includestdio.h
int v, g, need[30], food[20][30], ans[20], min 0x3f3f3f3f, temp[20], len;//v所需要v种营养 g有g种饲料 need每种营养成分需要多少 food二维数组低维:每种营养的含量高维:饲料总类 ans答案数组 temp存储现在选择的饲料 len目前选了len种饲料 min做优情况即选最少的种类便可达到所需的营养
_Bool visited[20];//状态数组表示是否被选过
_Bool check(int len) {//检查是否达到所需的营养int nutrition[30] { 0 };//每种营养现在的含量for (int i 1;i len;i) {for (int l 1;l v;l) {nutrition[l] food[temp[i]][l];} }for (int i 1;i v;i) {if (need[i] nutrition[i])//只要有一种营养成分含量不合格就返回0return 0;}return 1;
}
void dfs() {//搜索//最优剪枝if (len g || len min)//现在的饲料种类超过最优或超过总的饲料种类就退出递归return;if (check(len) 1) {//检验是否达到所需的营养含量若达到与最优解进行比较若所需的种类少于目前的最小的则代替最小成为新的最少即新的最优情况if (min len) {min len;for (int i 1;i min;i)ans[i] temp[i];}return;}for (int i temp[len]1;i g;i) {//遍历注意遍历的开始是上一次选择下一个【遍历选择每一种饲料不需要每次都从头开始选】if (!visited[i]) {visited[i] 1;len;temp[len] i;dfs();visited[i] 0;//回溯temp[len] 0;len--;}}}
int main() {scanf(%d, v);for (int i 1;i v;i) {scanf(%d, need[i]);}scanf(%d, g);for (int i 1;i g;i) {for (int j 1;j v;j) {scanf(%d, food[i][j]);}}dfs();printf(%d , min);for (int i 1;i min;i)printf(%d , ans[i]);return 0;
}
奇偶性剪枝
横纵坐标从1开始横纵坐标相加为奇数赋为0偶数赋为1
1-1:最近的1走两步任何一个1走偶数步0-0也是【同偶异奇】
冗余剪枝
重复的删除去
[USACO2.1] 健康的荷斯坦奶牛 Healthy Holsteins - 洛谷
#includestdio.h
int v, g, need[30], food[20][30], ans[20], min 0x3f3f3f3f, temp[20], len;//v所需要v种营养 g有g种饲料 need每种营养成分需要多少 food二维数组低维:每种营养的含量高维:饲料总类 ans答案数组 temp存储现在选择的饲料 len目前选了len种饲料 min做优情况即选最少的种类便可达到所需的营养
_Bool visited[20];//状态数组表示是否被选过
_Bool check(int len) {//检查是否达到所需的营养int nutrition[30] { 0 };//每种营养现在的含量for (int i 1;i len;i) {for (int l 1;l v;l) {nutrition[l] food[temp[i]][l];} }for (int i 1;i v;i) {if (need[i] nutrition[i])//只要有一种营养成分含量不合格就返回0return 0;}return 1;
}
void dfs() {//搜索//最优剪枝if (len g || len min)//现在的饲料种类超过最优或超过总的饲料种类就退出递归return;if (check(len) 1) {//检验是否达到所需的营养含量若达到与最优解进行比较若所需的种类少于目前的最小的则代替最小成为新的最少即新的最优情况if (min len) {min len;for (int i 1;i min;i)ans[i] temp[i];}return;}for (int i temp[len]1;i g;i) {//遍历注意遍历的开始是上一次选择下一个【遍历选择每一种饲料不需要每次都从头开始选】if (!visited[i]) {visited[i] 1;len;temp[len] i;dfs();visited[i] 0;//回溯temp[len] 0;len--;}}}
int main() {scanf(%d, v);for (int i 1;i v;i) {scanf(%d, need[i]);}scanf(%d, g);for (int i 1;i g;i) {for (int j 1;j v;j) {scanf(%d, food[i][j]);}}dfs();printf(%d , min);for (int i 1;i min;i)printf(%d , ans[i]);return 0;
}
记忆化搜索
将之前计算的结果存储在数组中当计算同样的数据时可以直接使用之前计算过的答案。
冗余重复的直接被删除
记忆化搜索借用之前重复的数据而不是舍去
(x,y) data[x][y]
dfs(x,y)
if(data[x][y]算过){
return data[x][y];
}
dfs函数返回值类型不是void
使用条件
1.有限个 2.有重复值
例题 int dp[25][25][25];
int dfs(int a, int b, int c) {
if (a 0 || b 0 || c 0)
return 1;
if (a 20 || b 20 || c 20) {
return dfs(20, 20, 20);
}
if (dp[a][b][c]) //先判断该值是否计算过如果算过直接调结果不需要再次计算直接返回即可
return dp[a][b][c];
if (a b b c) {
dp[a][b][c] dfs(a, b, c - 1) dfs(a, b - 1, c - 1) - dfs(a, b - 1, c);
}
else
dp[a][b][c] dfs(a - 1, b, c) dfs(a - 1, b - 1, c) dfs(a - 1, b, c - 1) - dfs(a - 1, b - 1, c - 1);
return dp[a][b][c];
}
例题——全排列
给定一个整数 n将数字 1∼n 排成一排将会有很多种排列方法。
现在请你按照字典序将所有的排列方法输出。
输入格式
共一行包含一个整数 n。
输出格式
按字典序输出所有排列方案每个方案占一行。
数据范围
1≤n≤7
输入样例
3
输出样例
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
#includestdio.h
int n;
int a[10],state[10]{0};
void dfs(int step){if(stepn1){for(int i1;in;i)printf(%d ,a[i]);printf(\n);return;}for(int i1;in;i){if(state[i]0){a[step]i;state[i]1;dfs(step1);a[step]0;state[i]0;}}return;
}
int main(){scanf(%d,n);dfs(1);return 0;
}
例题——八皇后
[USACO1.5] 八皇后 Checker Challenge - 洛谷
n*n的正方形i表示行j表示列ij表示其中一条对角线i-jn表示另外一条对角线
#includestdio.h
int a[15]{0},b[15]{0},c[30]{0},d[30]{0};
int n,sum0;
void dfs(int i){if(in){if(sum3){for(int k1;kn;k){printf(%d ,a[k]);}printf(\n);}sum;return;}for(int j1;jn;j){if((!b[j])(!c[ij])(!d[i-jn])){a[i]j;//行第i行是第j个b[j]1;//列c[ij]1;//对角线1,根据截距给对角线命名d[i-jn]1;//对角线2dfs(i1);b[j]0;//回溯c[ij]0;d[i-jn]0;}}
}
int main(){scanf(%d,n);dfs(1);printf(%d,sum);return 0;
}
广搜 bfs——一层一层走
一层一层搜索首先先把所有第一层的点即距离为1的点搜完然后进入下一层直到搜完。
边权相同时可以用bfs求最短路。
实现思路
使用队列来实现每次将要搜索的点放在队列中刚开始搜索时队列中只有一个点然后每次将所有与队头元素相连的且没有访问过的符合条件的点都放入队列之后对 队头元素进行处理然后出队。当队列为空则说明搜索停止。
这样就可以保证一层一层遍历遍历整体深度逐渐增大。
而由这样遍历出来的合法路径若是两点间权值相同的话是具有最优性质的。
框架
queue 初始状态
while queue 不空
{
t--每次取队头
扩展队头t
}
例题——走迷宫
给定一个n*m的二维整数数组用来表示一个迷宫数组中只包含0或1其中0表示可以走的路1表示不可通过的墙壁。
最初有一个人位于左上角(1, 1)处已知该人每次可以向上、下、左、右任意一个方向移动一个位置。
请问该人从左上角移动至右下角(n, m)处至少需要移动多少次。
数据保证(1, 1)处和(n, m)处的数字为0且一定至少存在一条通路。
输入格式
第一行包含两个整数n和m。
接下来n行每行包含m个整数0或1表示完整的二维数组迷宫。
输出格式
输出一个整数表示从左上角移动至右下角的最少移动次数。
数据范围
1≤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
//bfs使用手写队列实现
//输出路径只需要再开一个数组prev记录这个点是由那个点扩展出来即可
#includeiostream
#includecstring
using namespace std;
typedef pairint, int PII;
const int N 110;
int n, m;
char map[N][N];
int len[N][N];//每个点到起点的距离
PII q[N * N];//实现队列
//PII Prev[N][N]; //输出路径
int bfs() {int hh 0, tt 0;q[0] { 0,0 };memset(len, -1, sizeof len);//初始化函数将某一块内存中的内容全部设置为指定的值通常为新申请的内存做初始化工作//参数1指针或数组参数2赋给参数1的值参数3参数1的长度len[0][0] 0;int dx[4] { -1,0,1,0 }, dy[4] { 0,1,0,-1 };while (hh tt) {auto t q[hh];//每次取出队头元素for (int i 0;i 4;i) {int x t.first dx[i], y t.second dy[i];if (x 0 x n y 0 y m map[x][y] 0 len[x][y] -1) {len[x][y] len[t.first][t.second] 1;//Prev[x][y] t;q[tt] { x,y };//在队尾插入元素}}}/*int x n - 1, y m - 1;while (x || y) {cout x y endl;auto t Prev[x][y];x t.first, y t.second;}*/return len[n - 1][m - 1];
}
int main() {cin n m;for (int i 0;i n;i)cin map[i];cout bfs() endl;return 0;
}
有向图的遍历
宽度优先遍历
一层一层搜索 框架
queue —— 将起始状态插入队列中即将1号点插入队列
while queue 不空{
t 每次取队头元素
拓展 t 所有能到的点 x
ifx 未被遍历{ queue ——x 将 x 入队
d[x]d[t]1
}
}
例题——图中点的层次
给定一个n个点m条边的有向图图中可能存在重边和自环。
所有边的长度都是1点的编号为1~n。
请你求出1号点到n号点的最短距离如果从1号点无法走到n号点输出-1。
输入格式
第一行包含两个整数n和m。
接下来m行每行包含两个整数a和b表示存在一条从a走到b的长度为1的边。
输出格式
输出一个整数表示1号点到n号点的最短距离。
数据范围
1≤n,m≤10^5
输入样例
4 5
1 2
2 3
3 4
1 3
1 4
输出样例
1
代码
#includeiostream
#includecstring
using namespace std;
const int N 100010;
int n, m;
int h[N], e[N], ne[N], idx;
int d[N], q[N];
void add(int a, int b) {//插入函数e[idx] b;ne[idx] h[a];h[a] idx;
}
int bfs() {int hh 0, tt 0;q[0] 1;memset(d, -1, sizeof d);//初始化距离-1代表未被初始化d[1] 0;while (hh tt) {//判断队列是否为空int t q[hh];//取队头for (int i h[t];i ! -1;i ne[i]) {//扩展队头int j e[i];if (d[j] -1) {d[j] d[t] 1;q[tt] j;}}}return d[n];
}
int main() {cin n m;memset(h, -1, sizeof h);//初始化表头for (int i 0;i m;i) {int a, b;cin a b;add(a, b);}cout bfs() endl;
}
深度优先遍历
找到一个起点然后从这个 起点开始一条路走向黑 邻接表的深度优先遍历
主函数
for(int i0;in;i) dfs(i); //枚举起点
dfs
利用图中结点的编号进行搜索e存图中结点的编号
int h[N], e[M], ne[M], idx;//h存n个链表的链表头e存每个结点的值是多少ne存每个结点的next值
bool st[N];
//树和图的深度优先搜索
void dfs(int u) {//u是当前dfs到的点
st[u] true;//标记一下已经被搜过了
for (int i h[u];i ! -1;i ne[i]) {//遍历u的所有出边
int j e[i];//链表中该点在图中的编号
if (!st[j])//如果j没有被搜过那么就进行搜索
dfs(j);
}
例题——树的重心
给定一颗树树中包含n个结点编号1~n和n-1条无向边【无向图】。
请你找到树的重心并输出将重心删除后剩余各个连通块中点数的最大值。
重心定义重心是指树中的一个结点如果将这个点删除后剩余各个连通块中点数的最大值最小那么这个节点被称为树的重心。
输入格式
第一行包含整数n表示树的结点数。
接下来n-1行每行包含两个整数a和b表示点a和点b之间存在一条边。
输出格式
输出一个整数m表示重心的所有的子树中最大的子树的结点数目。
数据范围
1≤n≤10^5
输入样例
9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6
输出样例
4
代码
