一、深度优先搜索（DFS）
1、概念
DFS（Depth First Search）是从初始结点开始扩展，扩展顺序总是先扩展最新产生的结点。这就使得搜索沿着状态空间某条单一的路径进行下去，直到最后的结点不能产生新结点或者找到目标结点为止。当搜索到不能产生新的结点的时候，就沿着结点产生顺序的反方向寻找可以产生新结点的结点，并扩展它，形成另一条搜索路径。
2、剪枝策略
剪枝就是通过一些判断，剪掉搜索树上不必要的子树。在采用DFS算法搜索时，有时候我们会发现某个结点对应的子树的状态都不是我们要的结果，这时候我们没必要对这个分支进行搜索，砍掉这个子树，就是剪枝。
在DFS搜索算法中，剪枝策略就是寻找过滤条件，提前减少不必要的搜索路径。应用剪枝策略的核心问题是设计剪枝判断方法，即确定哪些枝条应当舍弃，哪些枝条应当保留的方法。
有时没有剪枝或剪枝不全：答案错误，压爆栈（特别是模拟类、地图搜索问题）等
剪枝策略按照其判断思路可大致分成两类：可行性剪枝及最优性剪枝。
（1）可行性剪枝
可行性剪枝就是把能够想到的不可能出现的情况给它剪掉 。该方法判断继续搜索能否得出答案，如果不能直接回溯。
（2）最优性剪枝
最优性剪枝，又称为上下界剪枝，是一种重要的剪枝策略。它记录当前得到的最优值，如果当前结点已经无法产生比当前最优解更优的解时，可以提前回溯。
对于求最优解**（最小值）**的一类问题，通常可以用最优性剪枝。比如在求迷宫最短路的时候，如果发现当前的步数已经超过了当前最优解，那从当前状态开始的搜索都是多余的，因为这样搜索下去永远都搜不到更优的解。通过这样的剪枝，可以省去大量冗余的计算。
（一）非回溯
1、概念
DFS中一般用于操作个数不确定且终止值不连续的情况。
2、解题思路
剪枝:剪去已访问及不符合题意的点，直接return
（题意给的特殊值情况）
终止条件，否则拓展
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24public static void dfs(int x,int y,int mou,int times) { //1、剪枝:剪去已访问及不符合题意的点，直接return if(mou==0 || times>m*n || times>minans || x<=0 || x>n || y<=0 || y>m || a[x][y]==0) return; //2、处理，v数组或根据题意给的特殊值情况 if(a[x][y]==4) mou=6; //v[] = 1; //3、终止条件 if(a[x][y]==3) { minans=Math.min(times, minans); }//否则拓展 else { dfs(x + 1,y,mou - 1,times + 1); dfs(x - 1,y,mou - 1,times + 1); dfs(x,y + 1,mou - 1,times + 1); dfs(x,y - 1,mou - 1,times + 1); } //4、回溯 //v[] = 0; }
3、地图搜索问题？？
解题思路
a.剪枝：剪去已访问及不符合题意的点，直接return（先做不符合的希望后续统一更改）
b.接下来符合条件，每个点可沿题目给定的几个方向拓展
技巧
a.适用v数组记录已访问的点，防止重复计算要统计的点及爆栈。一半要但非必需，如（1）（2）用
（3）（4）不用：（3）使用了数组值进行区分，（4）有条件剪枝
b.
3.1 简单遍历
a.黑色方块问题
https://www.cnblogs.com/cs-whut/p/11147213.html
1
2
3
4
5
6
7
8
9
10
11
12
13void dfs(int x, int y) { if(x >=0 && x<h && y>=0 && y<w && map[x][y]!='#' && visit[x][y]==0) { visit[x][y] = 1; sum++; dfs(x+1,y); // 递归访问四个方向的砖块 dfs(x-1,y); dfs(x,y+1); dfs(x,y-1); } }
3.2 连通块
a.求细胞数量
为什么两次判断？主函数：起点不能重且符合条件，dfs：拓展点不能重且符合条件
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46import java.util.*; public class Main { static int m; static int n; static int[][] q; static int[][] v; public static void main(String args[]) { Scanner in = new Scanner(System.in); n = in.nextInt(); m = in.nextInt(); int sum = 0; q = new int[n][m]; v = new int[n][m]; in.nextLine(); for(int i = 0;i < n;i++) { String s = in.nextLine(); char[] c = s.toCharArray(); for(int j = 0;j < m;j++) { q[i][j] = c[j] - '0'; v[i][j] = 0; } } for(int i = 0;i < n;i++) { for(int j = 0;j < m;j++) { if(q[i][j] != 0 && v[i][j] == 0) { sum++; dfs(i,j); } } } System.out.println(sum); } public static void dfs(int x,int y) { if(x >= 0 && x <= n - 1 && y >= 0 && y <= m - 1 && v[x][y] == 0 && q[x][y] != 0) { v[x][y] = 1; dfs(x + 1,y); dfs(x - 1,y); dfs(x,y + 1); dfs(x,y - 1); } } }
b.Lake Counting S
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15//八个方向 public static void dfs(int x,int y) { if(x >= 0 && x <= m - 1 && y >= 0 && y <= n - 1 && q[x][y] == 'W' && v[x][y] == 0) { v[x][y] = 1; dfs(x + 1,y); dfs(x - 1,y); dfs(x,y + 1); dfs(x,y - 1); dfs(x - 1,y - 1); dfs(x - 1,y + 1); dfs(x + 1,y - 1); dfs(x + 1,y + 1); } }
3.3 染色问题
a.拯救oibh总部
为什么要外搜一圈呢？？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51import java.util.*; public class Main { static int n; static int m; static int[][] q = new int[500][500]; public static void main(String args[]) { Scanner in = new Scanner(System.in); n = in.nextInt(); m = in.nextInt(); int sum = 0; for(int y = 1;y <= n;y++) { String s = in.next(); char[] c = s.toCharArray(); for(int x = 1;x <= m;x++) { if(c[x - 1] == '0') { q[x][y] = 0; }else { q[x][y] = 1; } } } //染色，从外圈开始？ dfs(0,0); //统计染色后仍为0的数量，即保护到的数量 for(int x = 1;x <= m;x++) { for(int y = 1;y <= n;y++) { if(q[x][y] == 0) { sum++; } } } System.out.println(sum); } public static void dfs(int x,int y) { //外搜一圈？？ if(x >= 0 && x <= m+1 && y >= 0 && y <= n+1 && q[x][y] == 0) { //将水淹没的地方标为2 q[x][y] = 2; dfs(x + 1,y); dfs(x - 1,y); dfs(x,y + 1); dfs(x,y - 1); } } }
b.填涂颜色
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45import java.util.*; public class Main { static int n; static int[][] q = new int[901][901]; public static void main(String args[]) { Scanner in = new Scanner(System.in); n = in.nextInt(); for(int x = 1;x <= n;x++) { for(int y = 1;y <= n;y++) { q[x][y] = in.nextInt(); } } dfs(0,0); for(int x = 1;x <= n;x++) { for(int y = 1;y <= n;y++) { if(q[x][y] == 0) { q[x][y] = 2; }else if(q[x][y] == 3) { q[x][y] = 0; } System.out.print(q[x][y]); //注意空格 if(y < n) { System.out.print(" "); } } System.out.println(""); } } public static void dfs(int x,int y) { if(x >= 0 && x <= n+1 && y >= 0 && y <= n+1 && q[x][y] == 0) { q[x][y] = 3; dfs(x + 1,y); dfs(x - 1,y); dfs(x,y + 1); dfs(x,y - 1); } } }
3.4 模拟问题
回家
缺少剪枝：会爆栈！
可行性剪枝：times>m*n ，不可能大于mn之积
最优性剪枝：times>minans，要求的是最小
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47import java.util.Scanner; public class Main { static int n=0,m=0,tx=0,ty=0,lx=0,ly=0,minans=1<<30; //minans 1乘以2的30次方 static int[][] a=new int[11][11]; public static void main(String[] args) { Scanner in=new Scanner(System.in); n=in.nextInt(); m=in.nextInt(); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { a[i][j]=in.nextInt(); if(a[i][j]==2) { //记录开始点 tx=i; ty=j; } } } dfs(tx,ty,6,0); //如果此时 minans 与初值相等，则没有找到可行路径 if(minans!=1<<30) { System.out.println(minans); }else { System.out.println("-1"); } } public static void dfs(int x,int y,int mou,int times) { //如果血量为0或者超出步数上界或者此时的步数已经超过了答案 if(mou==0 || times>m*n || times>minans || x<=0 || x>n || y<=0 || y>m || a[x][y]==0) return; if(a[x][y]==4) mou=6; if(a[x][y]==3) { //如果到达终点 minans=Math.min(times, minans); }else { dfs(x + 1,y,mou - 1,times + 1); dfs(x - 1,y,mou - 1,times + 1); dfs(x,y + 1,mou - 1,times + 1); dfs(x,y - 1,mou - 1,times + 1); } } }
4、其他模拟问题
对于此类问题，理论上来说可以用回溯做，但若条件比较复杂，则最好还是用非回溯
一般还会搭配其他思想，如（2）中还使用了贪心思想，故以后遇到再做练习
（1）奇怪的电梯
https://www.luogu.com.cn/problem/P1135
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40import java.util.Scanner; public class Main { static int n; static int a,b; static int[] rule = new int[300]; static int[] v = new int[300]; static int min = Integer.MAX_VALUE; public static void main(String[] args) { Scanner in = new Scanner(System.in); n = in.nextInt(); a = in.nextInt(); b = in.nextInt(); for(int i = 1;i <= n;i++) { rule[i] = in.nextInt(); v[i] = 0; } dfs(a,0); if(min == Integer.MAX_VALUE) { System.out.println(-1); }else { System.out.println(min); } } public static void dfs(int t,int num) { if(t < 1 || t > n || num > min || v[t] == 1) return ; v[t] = 1; if(t == b) { min = num; }else { dfs(t + rule[t],num + 1); dfs(t - rule[t],num + 1); } v[t] = 0; } }
（2）Sum It Up？
复杂在于：要去重
https://www.itdaan.com/blog/2018/09/12/ee3c020f4a35870f29c39cba21319555.html
思路：
（1）可行性剪枝： 因为题目中所有待选数都是正数，因此一旦发现当前的和值sum都已经大于t了，那么之后不管怎么选，和值都不可能回到t，所有当sum > t时，可以直接剪掉。
（2）从大到小：因给的数从大到小，故只需从前往后遍历即可
（3）注意防止结果式子重复？
1
2
3i==k||a[i]!=a[i-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41#include <iostream> #include <stdio.h> #include <algorithm> using namespace std; int n,t,a[13],f=1,b[13]; void dfs(int len,int k,int sum) { if(sum==0){ //遇到满足题意的，输出。 f=0; printf("%d",b[0]); for(int i=1;i<len;i++) printf("+%d",b[i]); printf("n"); }else{ for(int i=k;i<n;i++){ if((i==k||a[i]!=a[i-1])&&sum-a[i]>=0){ //防止重复 b[len]=a[i]; dfs(len+1,i+1,sum-a[i]); } } } } int main() { while(1){ cin>>t>>n; f=1; if(t==0&&n==0) break; for(int i=0;i<n;i++) cin>>a[i]; printf("Sums of %d:n",t); dfs(0,0,t); if(f) printf("NONEn"); } return 0; }
（3）The Robbery （POJ 3900）？？？
复杂在于：物品种类太多，使用贪心思想
思路：
a.dfs
可行性剪枝（剪枝三：题目要求一种钻石要拿则必须全拿）
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lu1v5wI0-1595651391751)(C:Usersddjj6AppDataRoamingTyporatypora-user-images1583335893893.png)]
b.贪心：选择性价比最高的
https://blog.csdn.net/V5ZSQ/article/details/48894677
（二）回溯
适用于操作个数确定且连续的情况，具体见之前笔记。
二、广度优先搜索（BFS）
1、概念
广度优先搜索BFS（Breadth First Search）也称为宽度优先搜索，它是一种先生成的结点先扩展的策略。
为了便于进行搜索，要设置一个表存储所有的结点。由于在广度优先搜索算法中，要满足先生成的结点先扩展的原则，所以存储结点的表一般采用队列这种数据结构。
如果目标结点存在于解答树的有限层上，广度优先搜索算法一定能保证找到一条通向它的最佳路径，因此广度优先搜索算法特别适用于只需求出最优解的问题。当问题需要给出解的路径，则要保存每个结点的来源，也就是它是从哪一个节点扩展来的。
2、解题思路
1
2
3
4
5
6
7
8
9
10
11
12
13//1、起始入队 visit = 1; //2、循环 while(队列不为空){ //3、出队 //（4、处理出队元素，判断是否结束） //5、出队拓展{ //6、符合条件，入队 visit = 1; } }
3、技巧
（1）用有visit数组标识结点是否已访问；当求步数时，用visit数组标注访问到某点所需步数，为-1表示未访问
如果没有v数组去重：时间、空间爆表，所以bfs一定要有v数组！！
（2）队列操作
1
2
3
4
5
6
7
8
9
10
11
12//C int front = 0,rear = 0; // front为队头指针，rear为队尾指针 q[rear++]=cur; // 初始结点入队 cur=q[front++]; // 队头元素出队 //Java Queue<T> q = new LinkedList<T>(); q.offer(in); //入队 q.poll(); //出队并删除 while(!q.isEmpty)
（3）队列所放元素如何定义
（4）拓展方式：见题意；判断条件：访问与否、题目条件
（5）创建两个节点对象：放置赋值重叠！
in out
4、优化：双向广度搜索
所谓双向广度搜索指的是搜索沿两个方向同时进行：
（1）正向搜索：从初始结点向目标结点方向搜索；
（2）逆向搜索：从目标结点向初始结点方向搜索；当两个方向的搜索生成同一子结点时终止此搜索过程。
广度双向搜索通常有两种方法：
（1）两个方向交替扩展；
（2）选择结点个数较少的那个方向先扩展。
方法（2）克服了两方向结点的生成速度不平衡的状态，可明显提高效率。
https://www.cnblogs.com/cs-whut/p/11157732.html
4.1 双向
（1）定义一个队列
用同一个队列来保存正向和逆向扩展的结点。**开始时，将起点坐标和终点坐标同时入队列。**这样，第1个出队的坐标是起点，正向搜索扩展队列；第2个出队的坐标是终点，逆向搜索扩展队列。…，两个方向的扩展依次交替进行。
（2）使用vis数组
初始时，vis数组的全部元素值为0，由正向扩展来的结点的vis对应元素值置为1，由逆向扩展来的结点的vis对应元素值置为2。
（3）数组判断
若vis[next.x][next.y]==0，则next结点未访问过，将next结点入队并进行相应设置；
若vis[next.x][next.y]！=0，则next结点已访问过。由于vis[cur.x][cur.y]记录的是当前扩展方向（1代表正向，2代表逆向）；
若vis[next.x][next.y] != vis[cur.x][cur.y]，则表示next结点以前按相反的方向访问过，正向和反向遇到了同一个结点，搜索成功，返回step[cur.x][cur.y]+step[next.x][next.y]+1;
4.2 结点个数少的方向先扩展
（1） 定义两个队列
两个队列q1[]和q2[]分别用于两个方向的扩展，两个队列的队头指针和队尾指针分别为front1、front2和rear1、rear2。将起始节点放入队列q1，将目的节点放入队列q2；
（2）队列q1里的未处理节点比q2中的少（即rear1-front1 < rear2-front2)，则扩展队列q1；否则扩展队列q2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57int BFS(int start_x,int start_y,int end_x,int end_y,int n) // 在n*n的棋盘中搜索从起点（start_x,strat_y)到终点（end_x,end_y)所需的最少步数 { int front1,rear1,front2,rear2,i,flag; point cur,next,q1[45001],q2[45001]; front1=rear1=0; front2=rear2=0; cur.x = start_x; cur.y = start_y; vis[start_x][start_y] = 1; // 设置正向探索标记为1 q1[rear1++] = cur; // 起始坐标入正向队列 next.x = end_x; next.y = end_y; vis[end_x][end_y] = 2; // 设置逆向探索标记为2 q2[rear2++] = next; // 终点坐标入逆向队列 while (front1 < rear1 && front2<rear2) { if (rear1-front1 < rear2-front2) { cur = q1[front1++]; flag=1; // 扩展正向队列 } else { cur = q2[front2++]; flag=2; // 扩展逆向队列 } for (i=0; i<8; ++i) { next.x = cur.x + dx[i]; next.y = cur.y + dy[i]; if (next.x<0 || next.x>=n || next.y<0 || next.y>=n) continue; //可拓展 if (!vis[next.x][next.y]) { vis[next.x][next.y] = flag; step[next.x][next.y] = step[cur.x][cur.y] + 1; // 扩展正向队列 if (flag==1) q1[rear1++] = next; // 扩展逆向队列 else q2[rear2++] = next; } else if (vis[cur.x][cur.y] != vis[next.x][next.y]) { return step[cur.x][cur.y]+step[next.x][next.y]+1; } } } return -1; // 若搜索不成功，表示不可达 }
5、遍历全部
处理出队元素这里没有结束判断
（1）黑色方块问题
https://www.cnblogs.com/cs-whut/p/11147348.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77#include <iostream> using namespace std; #define N 21 struct Node { int x; int y; }; int dx[4]={-1,1,0,0}; int dy[4]={0,0,-1,1}; char map[N][N]; int visit[N][N]; int bfs(int startx, int starty,int w,int h) { Node q[N*N],cur,next; // q为队列 int front,rear; // front为队头指针，rear为队尾指针 int i,x,y,sum; front=rear=0; // 队列q初始化 sum=0; cur.x=startx; cur.y=starty; //1、起始入队 visit[startx][starty]=1; q[rear++]=cur; // 初始结点入队 //2、循环 while(rear!=front) // 队列不为空 { //3、出队 cur=q[front++]; // 队头元素出队 //4、处理出队元素 sum++; // 方砖计数 //5、拓展 for (i=0;i<4;i++) { //6、符合条件入队 x=cur.x+dx[i]; y=cur.y+dy[i]; if(x >=0 && x<h && y>=0 && y<w && map[x][y]!='#' && visit[x][y]==0) { visit[x][y] = 1; next.x=x; next.y=y; // 由cur扩展出新结点next q[rear++]=next; // next结点入队 } } } return sum; } int main() { int i,j,pos_x,pos_y,w,h,sum; while(1) { cin>>w>>h; if (w==0 && h==0) break; for(i=0;i<h;i++) { for(j=0;j<w;j++) { cin>>map[i][j]; if (map[i][j]=='@') { pos_x = i; pos_y = j; } visit[i][j] = 0; } } sum=bfs(pos_x, pos_y,w,h); cout<<sum<<endl; } return 0; }
6、求最优、最短解
处理出队元素这里有结束判断
（1）Knight Moves （POJ 2243）
求最优、最短解
（2）整数变换
用有visit数组标识结点是否已访问；当求步数时，用visit数组标注访问到某点所需步数，为-1表示未访问
https://www.cnblogs.com/cs-whut/p/11150285.html
（3）质数变换？
**拓展：**得到只有一位不同的数
**打表：**质数，10的倍数
https://www.cnblogs.com/cs-whut/p/11150285.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71#include <iostream> using namespace std; char prime[10000]; void GetPrime() // 用筛法构建质数判定表 { int i,j; for (i=2;i<10000;i++) prime[i]='1'; for(i=2;i<10000;i++) { if (prime[i]=='1') for (j=2*i;j<10000;j+=i) prime[j]='0'; } prime[1]='0'; } void BFS(int k,int m) { int visit[10000],que[10000],a[4]={1,10,100,1000}; //打表！！ int front,rear,i,j,s,x,y,num; for (i=1000;i<10000;i++) //一个个初始化为-1!!! visit[i]=-1; front=rear=0; que[rear++]=k; // k入队 visit[k]=0; while(front!=rear) { s=que[front++]; // 队头元素出队 if (s==m) { cout<<visit[s]<<endl; return; } for (i=0;i<4;i++) { //j是变换的位 for (j=0;j<10;j++) { //求一个不同的数？？？ //取前 x=s/(a[i]*10); //取后 y=s%a[i]; num=x*a[i]*10+j*a[i]+y; if (num>1000 && visit[num]==-1 && prime[num]=='1') { que[rear++]=num; // 变换后的质数入队 visit[num]=visit[s]+1; } } } } cout<<"Impossible"<<endl; } int main() { int n,k,m; GetPrime(); cin>>n; while (n--) { cin>>k>>m; BFS(k,m); } return 0; }
（4）医院设置？
由于二叉树可往上进行，故使用临界数组存储节点可达关系
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66import java.util.*; public class Main { public static class Node{ int index,step; public Node(int index,int step) { this.index = index; this.step = step; } } static int[][] g = new int[101][101]; static int[] num = new int[101]; static int n; public static void main(String[] args) { Scanner in = new Scanner(System.in); n = in.nextInt(); for(int i = 1;i <= n;i++) { num[i] = in.nextInt(); int l = in.nextInt(); int r = in.nextInt(); //不要写错！！！ if(l != 0) { g[i][l] = g[l][i] = 1; } if(r != 0) { g[i][r] = g[r][i] = 1; } } int min = Integer.MAX_VALUE; for(int i = 1;i <= n;i++) { int sum = bfs(i); if(sum < min) { min = sum; } } System.out.println(min); } public static int bfs(int start) { int sum = 0; Node out,in; int[] v = new int[101]; for(int i = 1;i <= 100;i++) { v[i] = 0; } Queue<Node> q = new LinkedList<Node>(); in = new Node(start,0); q.offer(in); v[start] = 1; while(!q.isEmpty()) { out = q.poll(); sum += num[out.index] * out.step; for(int i = 1;i <= n;i++) { if(g[out.index][i] == 1 && v[i] == 0) { in = new Node(i,out.step + 1); q.offer(in); v[i] = 1; } } } return sum; } }
（5）马的遍历
n m 不要写错了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65import java.util.*; public class Main { public static class Node{ int i,j,step; public Node(int i,int j,int step) { this.i = i; this.j = j; this.step = step; } } static int[][] map; static int[][] v; static int[] x = new int[] {1,1,-1,-1,2,2,-2,-2}; static int[] y = new int[] {2,-2,2,-2,1,-1,1,-1}; static int n; static int m; public static void main(String[] args) { Scanner in = new Scanner(System.in); n = in.nextInt(); m = in.nextInt(); map = new int[n + 1][m + 1]; v = new int[n + 1][m + 1]; for(int i = 1;i <= n;i++) { for(int j = 1;j <= m;j++) { map[i][j] = -1; } } int si = in.nextInt(); int sj = in.nextInt(); bfs(si,sj); for(int i = 1;i <= n;i++) { for(int j = 1;j <= m;j++) { //左对齐，宽5格 System.out.printf("%-5d",map[i][j]); } System.out.println(); } } public static void bfs(int si,int sj) { Node in,out; Queue<Node> q = new LinkedList<Node>(); in = new Node(si,sj,0); q.offer(in); while(!q.isEmpty()) { out = q.poll(); map[out.i][out.j] = out.step; v[out.i][out.j] = 1; for(int i = 0;i < 8;i++) { int ini = out.i + x[i]; int inj = out.j + y[i]; if(ini >= 1 && ini <= n && inj >= 1 && inj <= m && v[ini][inj] == 0) { in = new Node(ini,inj,out.step + 1); q.offer(in); v[ini][inj] = 1; } } } } }
（6）棋盘？？？？
https://www.luogu.com.cn/problem/P3956
7、搜索状态判重（bfs+hash）
在状态判重方法中，hash法是一种常用的方法。常用于对判断数组的压缩以节约空间。
hash法重点在于hash函数的构造。
a.排序的压缩
对n个数字的排列，可构造vis[n!]的数组存储遍历情况
n! 与n个数字组成的全排列如何映射呢？我们以3个数字1、2、3组成的全排列来说明问题。
设排列中所有数字满足从小到大排列，则称为正序。不是正序的排列中一定存在某个数字k后面有若干个数字比k小，比k小的数字个数n称为k的逆序个数。
例如，123的各位逆序个数序列为：0，0，0。映射整数为：0=02！+01！+0*0！=0
132的各位逆序个数序列为：0，1，0。映射整数为：1=02！+11！+0*0！=1
213的各位逆序个数序列为：1，0，0。映射整数为：2=12！+01！+0*0！=2
231的各位逆序个数序列为：1，1，0。映射整数为：3=12！+11！+0*0！=3
312的各位逆序个数序列为：2，0，0。映射整数为：4=22！+01！+0*0！=4
321的各位逆序个数序列为：2，1，0。映射整数为：5=22！+11！+0*0！=5
对6位数 654312而言，各位逆序个数序列为：5,4,3,2,0,0，应映射为：55！+44！+33！+22！+01！+00！=600+96+18+4=718。
实现方式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20int fact[]={1,1,2,6,24,120}; // 对应0！,1！,2！,3！,4！,5！ int hash(char *s) // 把1..6的排列映射为数字 0..(6!-1) { int i, j, temp, num; num = 0; for (i = 0; i <6-1; i++) { temp = 0; for (j = i + 1; j < 6; j++) { if (s[j] < s[i]) temp++; } num += fact[6-i-1] * temp; } return num; }
（1）最少交换
思路：
（1）用字符数组读取易于操作
（2）使用hash压缩
https://www.cnblogs.com/cs-whut/p/11162392.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68#include <stdio.h> #include <string.h> int fact[]={1,1,2,6,24,120}; // 对应0！,1！,2！,3！,4！,5！ int hash(char *s) // 把1..6的排列*s 映射为数字 0..(6!-1) { int i, j, temp, num; num = 0; for (i = 0; i <6-1; i++) { temp = 0; for (j = i + 1; j < 6; j++) { if (s[j] < s[i]) temp++; } num += fact[6-i-1] * temp; } return num; } int BFS(char src[],char dest[]) { int vis[720],front,rear,s0,s1,ts,i; for(int i = 0;i < 720;i++){ vis[i] = -1; } char q[720][7],cur[7],next[7],tmp; front=rear=0; s1=hash(dest); strcpy(q[rear++],src); s0=hash(src); vis[hash(src)]=0; while (front<rear) { strcpy(cur,q[front++]); // 出队列 s0=hash(cur); if (s0==s1) // 达到目标状态 return vis[s0]; for (i=0;i<6-1;i++) { strcpy(next,cur); tmp=next[i]; next[i]=next[i+1];next[i+1]=tmp; // 交换位置i和i+1中的数字 ts=hash(next); if (vis[ts]==-1) // 状态未出现过 { vis[ts]=vis[s0]+1; // 记录步数 strcpy(q[rear++],next); } } } } int main() { char src[7],dest[7]; while(scanf("%s%s",src,dest)!=EOF) { printf("%dn",BFS(src,dest)); } return 0; }
（2）八数码难题？？？
为保存状态空间，定义三个全局数据：
char visited[MAXN]; // visited[i]=1表示状态i被访问过；为0，表示未被访问
int parent[MAXN]; // parent[i]=k 表示状态结点i是由结点k扩展来的
char move[MAXN]; // move[i]=d 表示状态结点i是由父节点按照方式d扩展来的
https://www.cnblogs.com/cs-whut/p/11162663.html
bfs核心操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27while(!que.empty()) { cur = que.front(); que.pop(); for(i=0; i<4; ++i) { if(!(i==0 && cur.space<3 || i==1 && cur.space%3==0 || i==2 && cur.space%3==2 ||i==3 && cur.space>5)) { nst = cur; nst.space = cur.space-5+2*(i+1); nst.board[cur.space]=nst.board[nst.space]; nst.board[nst.space]=9; k = hash(nst.board); if(visited[k] != 1) { move[k] = i; visited[k] = 1; parent[k] = hash(cur.board); if(k == 0) //目标结点hash值为0 return; que.push(nst); } } } }
输出路径
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21void print_path() { int n, u; char path[1000]; n = 1; path[0] = move[0]; u = parent[0]; while(parent[u] != -1) { path[n] = move[u]; ++n; u = parent[u]; } for(int i=n-1; i>=0; --i) { cout<<md[path[i]]; } cout<<endl; }
三、DFS和BFS的比较
在采用BFS搜索时，BFS是按一层一层来访问的，层层搜索每一层就代表了一步。BFS优先访问的是兄弟节点，只有这一层全部访问完才能访问下一层，也就是说BFS第几层就代表从起点最少需要多少歩走到当前层的结点；而DFS是按递归来实现的，它优先搜索深度，到一条路径走不下去了再回溯，优先访问的是没有访问过的子结点。
由此可体会：BFS用来搜索最短径路的解是比较合适的，比如求最少步数的解，最少交换次数的解。因为BFS搜索过程中遇到的解一定是离根最近的，所以遇到一个解，一定就是最优解，此时搜索算法可以终止。这个时候一般不适宜使用DFS，因为DFS搜索到的解不一定是离根最近的，只有全局搜索完毕，才能从所有解中找出离根的最近的解。
DFS适合搜索全部的解，因为要搜索全部的解，那么BFS搜索过程中，遇到离根最近的解，并没有什么用，也必须遍历完整棵搜索树，DFS搜索也会搜索全部，但是相比DFS不用记录过多信息，所以搜素全部解的问题，DFS显然更加合适。
DFS：尽量使用，全部遍历及部分最小解、最大解
BFS：大多数求最小解时使用
https://www.cnblogs.com/cs-whut/p/11149521.html
最后
以上就是殷勤大米最近收集整理的关于算法（四）搜索的全部内容，更多相关算法（四）搜索内容请搜索靠谱客的其他文章。
发表评论 取消回复