知识点1：迭代加深DFS

应用情景

如图，当搜索树的深度过大但答案在搜索树的浅层时，根据DFS的搜索顺序，会先枚举左子树的所有内容（图中框出部分），接下来才能够找到答案。

解决办法

所以，如果我们已经知道答案出现出浅层，我们可以借用BFS的搜索顺序（一层一层搜），但用BFS的方法实现：

我们在每一次DFS的时候，限制搜索的层数。
当按照当前限制的层数搜索未搜索到答案，就把搜索限制加1.
当搜索到答案，当前的搜索限制就是答案。

代码：

CPP

#include<bits/stdc++.h>
using namespace std;
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
int n,limit;//DFS搜索限制
int l[10000];//路径记录
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
bool dfs(int dep){
	if(dep>limit) return 0;//超出DFS限制范围 return
	if(找到答案) return 1;
	for(枚举可达状态){
        %%%
		if(dfs(dep+1)) return 1;//如果找到答案，继续return 1
        %%%
	}
	return 0;//未找到答案，return 0
}
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
int main(){
	while(cin>>n && n){
		limit=1,l[1]=1;
		while(!dfs(开始参数)) limit++;
		printf("%d ",limit-1);
		for(int i=1;i<limit;i++) printf("%d ",l[i]);//输出答案路径
		cout<<'\n';
	}
	return 0;
}

知识点2：双向搜索

应用情景

当我们已经知道起点和终点的情况下，我们可以使用双向搜索来使时间复杂度减半:
从起点和终点分别搜索一半，在中间相遇。
如图：

这样时间复杂度减少一半。

例题：

例19.1-2 送礼物
方法：

首先，看见题目我们很容易想到01背包，但一看题目数据范围： $G[i]\leq 2^{31}-1$ ,根本存不下。
但是如果我们直接使用DFS的话，时间复杂度 $O(2^N)$
送一我们想到双向搜索，DFS1搜一般总价格，然后DFS2一一与DFS1的结果比较。

代码:

CPP

#include<bits/stdc++.h>
using namespace std;
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
int W,n,ans;
int tot,l[50],f[1<<24];
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
void dfs1(int cnt,int sum){
	if(cnt==n/2+1){
		f[++tot]=sum;
		return ;
	}
	dfs1(cnt+1,sum);
	if(l[cnt]<=W-sum) dfs1(cnt+1,sum+l[cnt]);
}
void dfs2(int cnt,int sum){
	if(cnt==n+1){
		ans=max(ans,sum+f[upper_bound(f+1,f+tot+1,W-sum)-f-1]);
		return ;
	}
	dfs2(cnt+1,sum);
	if(l[cnt]<=W-sum) dfs2(cnt+1,sum+l[cnt]);
}
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
signed main(){
	cin>>W>>n;
	for(int i=1;i<=n;i++) cin>>l[i];
	sort(l+1,l+n+1);
	dfs1(1,0);sort(f+1,f+tot+1);
	dfs2(n/2+1,0);cout<<ans;
	return 0;
}

DFS

文章操作

知识点1：迭代加深DFS

应用情景

解决办法

代码：

知识点2：双向搜索

应用情景

例题：

相关推荐

评论

DFS