搜索总结

学习
字数统计: 2.7k   |   阅读时长≈ 12 分钟

搜索总结

1. 深度优先搜索DFS

数据结构 stack，空间复杂度O(n)，不具有最短性，深搜问题没有模板

  • 关键在于：剪枝和回溯

1.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
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;

const int maxn=10;

int n;
int path[maxn]; // 每一步填的数字
bool st[maxn]; // 遍历状态

// 深度优先
void dfs(int u) {
	// 跳出条件
	if(u==n) {
		for(int i=0;i<n;i++) 
			cout<<path[i]<<' ';
		cout<<endl;
		return;
	}
	// 如果还没有填满,从数字1开始
	for(int i=1;i<=n;i++) {
		if(!st[i]) {
			path[u]=i;
			st[i]=true;
			// 进入下一层
			dfs(u+1);
			// 回溯
			st[i]=false;
		}
	}
}

int main() {
	cin>>n;
	dfs(0);
	return 0;
}

1.2. n皇后问题

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
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;

int n; // 皇后个数
const int maxn=9; // 最大皇后个数
int x[maxn+1]; // 存放皇后位置,x[i]表示第i个皇后的在第几列
int res; // n皇后的可行解个数

// 判断第i个皇后放置在x[i]列是否会发生冲突
bool place(int j) {
	// j=1~i-1是已经放置了皇后的行
	for(int i=1;i<j;i++) {
		// x数组的物理性质决定两个皇后不会发生行冲突
		// x[j]==x[i]:发生列冲突
		// abs(i-j)==abs(x[i]-x[j]):发生对角线冲突,可画图推导
		if(x[j]==x[i] || abs(i-j)==abs(x[i]-x[j]))
			return false; // 冲突就返回false
	}
	return true;
}

// 打印棋盘
void print() {
	res++; // 答案+1
	// 遍历每个皇后
	for(int i=1;i<=n;i++) {
		// 遍历每一列
		for(int j=1;j<=n;j++) {
			// 如果皇后所在列就是j,打印'Q'
			if(x[i]==j)
				cout<<'Q';
			else
				cout<<'.';
		}
		cout<<endl;
	}
	cout<<endl;
}

// 放置每个皇后的深度优先搜索函数
void dfs(int u) {
	// 遍历第1列到n列
	for(int j=1;j<=n;j++) {
		// 先把皇后放到第j列
		x[u]=j;
		// 如果第u个皇后放在这列不冲突
		if(place(u)) {
			// 找到了一个可行解,直接打印
			if(u==n)
				print();
			// 向下递归
			else
				dfs(u+1);
		}
	}
}

int main() {
	cin>>n;
	dfs(1); // 从第一个皇后开始
	cout<<"可行解一共有 "<<res<<" 个"<<endl;
	return 0;
}

2. 广度优先搜索BFS

数据结构 queue，空间复杂度O(2^n)，最短路，宽搜问题有模板

2.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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;

const int N=1e2+2;
int n,m; // 地图范围
int g[N][N]; // 存图的情况
int d[N][N]; // 每个点到初始点的距离
PII q[N*N]; // BFS的队列
PII Prev[N][N]; // 记录遍历的顺序

int bfs() {
	// hh:队头,当前要处理元素的下标
	// tt:队尾,最后一个入队元素的下标
	int hh=0,tt=0;
	q[0]={0,0}; 
	
	// 初始化,表示害没有任何点经过
	memset(d,-1,sizeof d);
	d[0][0]=0;
	
	// 向量表示四个方向
	int dx[4]={-1,0,1,0};
	int 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];
			// 如果没有超出地图范围且g[x][y]=0且没有到过
			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; // 距离加1
				Prev[x][y]=t; // 记录上一步
				q[++tt]={x,y}; // 把x,y放进队头
			}
		}
	}
	
	// 输出路径
//	int x=n-1,y=m-1;
//	// [0,1] [1,0]都可以输出
//	while(x||y) {
//		cout<<x<<' '<<y<<endl;
//		auto t=Prev[x][y];
//		x=t.first,y=t.second;
//	}
	
	// 返回距离
	return d[n-1][m-1];
}

int main() {
	cin>>n>>m;
	// 输入图
	for(int i=0;i<n;i++) {
		for(int j=0;j<m;j++) {
			cin>>g[i][j];
		}
	}
	
	cout<<bfs()<<endl;
	return 0;
}

2.2. 八数码

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
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef unsigned long long ULL;
typedef pair<int,int> PII;

// 八重码:类似于一个数字华容道嘛,求移动的最少步数(BFS)
// 难点在于状态表示比较复杂,每个状态是一个3*3的小矩阵
// 问题一:队列,如果把每个状态放进队列中 "12345678x"
// 问题二:如何计算每个状态的距离 "queue<string>,unordered_map<string,int>"

queue<string> q; // 定义队列
// 让字符串映射到int类型的值
unordered_map<string,int> d; // 通过哈希表来让字符串变化时和移动的距离数值关联

int bfs(string st)
{
	q.push(st); // 将字符串入队
	d[st]=0; // 将初始状态的字符串的哈希值设定为0
	
	int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1}; // 定义四个方向向量
	
	// 5在一维数组中的下标是4
	string end="12345678x"; // 定义宽度优先搜素的终止状态
	while(q.size()) // 循环终止状态
	{
		auto t=q.front(); // 将队列中存着的字符串赋值给t
		q.pop(); // 队头元素弹出
		
		if(t==end) 
			return d[t]; // 如果当前字符串等于终止状态搜索结束返回该字符串对应的哈希值
		//此处的哈希函数值对应于字符串移动的次数    
		int distance = d[t]; // 定义一个临时变量distance存储形成t字符串当前的移动次数
		int k = t.find('x'); // k表示'x'字符在字符串当前的下标
		// 把'x'所在的下标转换成二维数组的形式,比如"12345678x",x就是8,8/3=2,8%3=2,所以是第三行第三列
		int x = k/3,y = k%3; // 由于字符串当前是一维的将一维下标转化为二维坐标
		for(int i=0;i<4;i++) // 分别遍历四个方向
		{ 
			// 遍历'x'可以走的四个方向
			int a=x+dx[i],b=y+dy[i]; //将下一个搜索位置的x,y坐标表示
			// 越界处理
			if(a>=0&&a<3&&b>=0&&b<3) //当二维坐标满足位于3X3矩阵中时
			{
				// 将搜索位置和'x'相交换,a*3+b变回一维数组索引
				swap(t[a*3+b],t[k]); //将字符串中的搜索位置与字符'x'交换
				// d.count(t)是统计d这个哈希表容器中t出现的次数,如果一次都没出现过,就放进队列,同时在dist[t]上做加减
				if(!d.count(t)) // 如果当前的字符串的哈希值为0
				{
					d[t]=distance+1; // 将该字符串对应的哈希值在原字符串对应的哈希值基础上加1
					q.push(t); // 将该字符串入队
				}
				swap(t[a*3+b],t[k]); // 恢复现场,返回位置判断其他方向
			}
		}
	}	
	return -1; // 如果无法移动到终止位置返回-1
}

int main()
{
	string s;
	string st;
	// 输入一个初始状态
	for(int i=0;i<9;i++)
	{
		cin>>s;
		st+=s; //逐个输入字符串
	}
	cout<<bfs(st)<<endl; //输出宽度优先搜索的数值	
	return 0;
}

3. 树和图的存储

树是一种特殊的图，因此只讨论图

3.1. 有向图

3.1.1. 邻接矩阵

  • 邻接矩阵不能存储重边，空间复杂度O(n²)，适合稠密图

3.1.2. 邻接表

  • 每个结点开一个单链表，邻接表内部的顺序是无所谓的，邻接表插入新边后引入新的结点一般用头插法

4. 树和图的遍历

4.1. 深度优先遍历

时间复杂度O(n+m)，点数+边数

  • 优点在于可以求出每一棵子树的大小。

4.2. 广度优先遍历

时间复杂度O(n+m)，点数+边数

  • 优点在于可以求出最短路径，但前提是每条路的权重相同

4.3. 模板

注意DFS是没有模板的，但基本可以分为终止条件、递归逻辑、剪枝、恢复现场几个步骤，在另一篇博客里给出了我自己对于DFS的模板，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
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
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;

// 输入输出规模在100w的时候必须用scanf
// 树和图的存储
const int N=1e5+5,M=N*2;
// h[i]:第i个结点的邻接表,头插,存储边
// e[j]:第j条边指向的结点
// ne[j]:第j条边的下一条边
// idx:边的编号
int n,m;
int h[N],e[M],ne[M],idx;
bool st[N]; // 每个点的搜索状态

int q[N],d[N]; // bfs队列和距离数组
int Prev[N]; // 记录顺序

void add(int a,int b) {
	// 第idx条边指向的结点是b
	// 第idx条边的下一条边是a的单链表(头结点)
	// 结点a的邻接表的第一条边变为idx,idx++
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

// bfs找最短路径为例:注意每条路的权重必须都相同,如这里的1
int bfs() {
	int hh=0,tt=0; // 队头和队尾
	q[0]=1; // 头结点是1
	memset(d,-1,sizeof d); // 距离初始化为-1
	d[1]=0; // 第1个结点到第1个结点的距离是0
	while(hh<=tt) {
		int t=q[hh++]; // 取出头结点,hh++
		for(int i=h[t];i!=-1;i=ne[i]) {
			int j=e[i];
			// 如果j还未访问过
			if(d[j]==-1) {
				d[j]=d[j]+1;
				q[++tt]=j; // 在队尾增加一个空位,再把j的值赋给q[tt]
			}
		}
	}	
}

void dfs(int u) {
	st[u]=true;
	// 从u的第一条边开始往下遍历每一条边
	for(int i=h[u];i!=-1;i=ne[i]) {
		int j=e[i];
		// 如果还未被访问过,就继续dfs[j]
		if(!st[j])
			dfs[j];
	}
}

int main() {
	memset(h,-1,sizeof h); // 初始化为-1
	return 0;
}
打赏
  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
  • Copyrights © 2015-2024 John Doe
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信