AKSZ-深度优先搜索(DFS)

zcc

2024-05-19 12:46:24

发布于：广东

11阅读

0回复

0点赞

akday8 搜索算法——深度优先搜索(DFS)

回溯

剪枝

连通性判断

排列组合

加法原理与乘法原理

加法原理： $(0\sim 9+a\sim z)$ 任选一个共有多少种可能性 10+26=36种
乘法原理：
$A^m_n=n*(n-1)*......*(n-m+1)$
$C^m_n=A^m_n\div A^m_m$

“排列”例题

洛谷 $B3621$ ——枚举元组
寻找题目链接

#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[15]; 
void dfs(int x){//当前在第x层循环下的情况 
	//确定递归边界
	if(x > n){//进入的是最里面的循环 
		//元组输出出来 
		for(int i=1;i<=n;++i){
			cout << a[i] <<" ";
		}
		cout<<endl;
		return;
	} 
	for(int i=1;i<=k;++i){
		a[x] = i;
		dfs(x+1);//进入下一层循环 
	} 
}
int main(){
	cin>>n>>k;
	dfs(1);
	return 0;
}

“组合”例题

洛谷 $B3623$ ——枚举排列
寻找题目链接

#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[18];
void dfs(int x){
	
	//当前在第k层循环 
	if(x==k){
		for(int i=1;i<=k;++i){
			cout<<a[i]<<" ";
		}
		puts("");
		return;
	}
	for(int i=1;i<=n;++i){
		bool ok=1;
		for(int j=1;j<=x;++j){
			if(a[j]==i){
				ok=0;
				break;
			} 
		}
		if(ok){
			a[x+1]=i;
			dfs(x+1);
		}
	}
}
int main(){
	cin>>n>>k;
	dfs(0);
	return 0;
}

综合例题

洛谷 $B3622$ ——枚举子集
寻找题目链接

#include<bits/stdc++.h>
using namespace std;
const int maxn=25;
int vis[maxn],n;
void dfs(int x){
	if(x>n){
		for(int i=1;i<=n;++i){
			cout<<((vis[i]==0)?"N":"Y");
		}
		cout<<endl;
		return ;
	}
	vis[x] = 0;
	dfs(x+1);
	vis[x] = 1;
	dfs(x+1);
}
int main(){
	cin>>n;
	dfs(1);
	return 0;
}

剪枝

剪枝条件

当题目上出现 $w[i]$ 在范围内均匀随机生成

可运用剪枝的例题

洛谷B3624 猫粮规划

#include<bits/stdc++.h>
using namespace std;
int n,l,r,cnt;
int w[50];
bool vis[50];
void dfs(int x,int sum){//表示当前算完n个食物，然后得到的能量 
	if(sum>r){
		//打破可行性
		//后面不管怎么搜，都是不合法
		return; 
	} 
	if(x>n){
		//此时sum最终能获得的能量值
		//sum在[l,r]区间内，说明答案+1，搜出一个可行解
		if(sum>=l&&sum<=r)++cnt;
		return ; 
	}
	dfs(x****um);
	dfs(x****um+w[x]);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>l>>r;
	for(int i=1;i<=n;++i)cin>>w[i];
	dfs(1,0);
	cout<<cnt;
	return 0;
}

八皇后问题

题目描述

一个如下的 $6 \times 6$ 的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。

上面的布局可以用序列 $2\ 4\ 6\ 1\ 3\ 5$ 来描述，第 $i$ 个数字表示在第 $i$ 行的相应位置有一个棋子，如下：

行号 $1\ 2\ 3\ 4\ 5\ 6$

列号 $2\ 4\ 6\ 1\ 3\ 5$

这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出，解按字典顺序排列。
请输出前 $3$ 个解。最后一行是解的总个数。

输入格式

一行一个正整数 $n$ ，表示棋盘是 $n \times n$ 大小的。

输出格式

前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。

样例 #1

样例输入 #1

样例输出 #1

2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4

提示

【数据范围】
对于 $100\%$ 的数据， $6 \le n \le 13$ 。

题目翻译来自NOCOW。

USACO Training Section 1.5

$Answer$

#include<bits/stdc++.h>
using namespace std;
int n,cnt;
int col[15];
bool vis[15];
void dfs(int x){//已经放了x个棋子
	if(x>n){
		if(cnt<3){
			for(int i=1;i<=n;++i){
				cout<<col[i]<<" ";
			}
			puts("");
		}cnt++;
		return;
	}
	 
	for(int i=1;i<=n;++i){//放的是第几列
		if(!vis[i]){//列不冲突 
			bool flag=1;
			for(int j=1;j<x;++j){
				//(x行,i)
				//(j行,col[j])
				if(x-i==j-col[j]||x+i==j+col[j]){
					flag=0;
					break;
				}
			}
			if(flag){
				col[x]=i;
				vis[i]=1;
				dfs(x+1);
				vis[i]=0;
			}
		}
		
	}
	
}
int main(){
	cin>>n;
	dfs(1);
	cout<<cnt;
	return 0;
}