[数据结构与算法]c++dfs详解

目录

一、dfs

二、如何使用

1.重要性

2.优化策略

剪枝

1.可行性剪枝

2.最优性剪枝

3.搜索顺序剪枝

去除等效冗余

三、例题

1.全排列问题

2.砝码称重

一、dfs

就是通过树建立起来的深度优先搜索，也就是树的先序遍历

二、如何使用

1.重要性

相信不会有人质疑他的用处，一个搜索玩得好的选手，可能所有题都不是他的对手。

有诗如此：

暴搜挂着机，打表出省一。偏分过样例，暴力出奇迹。

转载链接：https://www.cnblogs.com/ljy-endl/p/11337154.html

但搜索也不是那么好搜的，O(n^n)的复杂度就问你怕不怕

2.优化策略

常见的优化策略：可行性剪枝、最优性剪枝、搜索顺序剪枝、去除等效冗余、记忆化搜索

这里不讲记忆化搜索，因为那是bfs里的

剪枝

深搜，它的进程近似一颗树。

而剪枝就是一种生动的比喻：把不会产生答案的，或不必要的枝条“剪掉”。

剪枝的关键就在于剪枝的判断：什么枝该剪，什么枝不该剪，在什么地方减。

这就是剪枝的原则：

正确性，准确性，高效性。

1.可行性剪枝

最常见的就是去重，标记数组控制状态节点是否被访问

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

2.最优性剪枝

最优性剪枝一般是处理最优解的问题。
在求最优解的搜索问题中，如果我们在搜索过程中发现，当前路径已经不可能获得最优解，可以直接剪枝回退。

3.搜索顺序剪枝

例如数独问题，通过选择搜索顺序，可以确定某些状态结点，从而减少子状态结点的扩展

去除等效冗余

搜索的不同分支，最后的结果是一样的，那么只搜一个分支就够了。

三、例题

1.全排列问题

输出自然数 1 到 n 所有不重复的排列，即 n 的全排列，要求所产生的任一数字序列中不允许出现重复的数字，输出按字典序排列。

输入格式:

一个整数 n。

输出格式:

由 1～n 组成的所有不重复的数字序列，每行一个序列。

每个数字保留 5 个宽度。

限制:

空间限制：128MByte
时间限制：1秒

样例:

输入：

3

输出：

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

提示:

1≤n≤9

此题非常的经典，只需要判断一下，去个重，剩下的照常就行

代码如下：

#include<cstdio>
#include<iostream>
using namespace std;
int d[100],flag[100];
int n;
void dfs(int x){
	if(x==n+1){
		for(int i=1;i<=n;i++){
			printf("    %d",d[i]);
		}
		printf("\n");
		return;
	}
	for(int i=1;i<=n;i++){
		if(!flag[i]){
			d[x]=i;
			flag[i]=1;
			dfs(x+1);
			d[x]=0;
			flag[i]=0;
		}
	}
}
int main(){
	cin>>n;
	dfs(1);
	return 0;
}

2.砝码称重

#include<iostream>
using namespace std;
int a[100]= {1,2,3,5,10,20},flag[1000],nums[100];
int ans;
void dfs(int step,int sum) {
	if(step==6) {
		if(!flag[sum]&&sum) {
			ans++;
			flag[sum]=1;	
		}
		return;
	}
	for(int i=0; i<=nums[step]; i++) {
		dfs(step+1,sum+a[step]*i);
	}
}
int main() {
	for(int i=0; i<6; i++) {
		cin>>nums[i];
	}
	dfs(0,0);
	cout<<"Total="<<ans;
	return 0;
}