• 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

[算法] 高级搜索算法之迭代加深

其他 Last_Breath 3039次浏览 0个评论

前言

最开始搞 \(OI\) 的时候接触了搜索算法,后面基本上没有在练过了。若本文有误,请在讨论区指出。

本文例题链接

思想

假设一张图, \(ans1\) 在很深的地方, \(ans2\) 离搜索树的根节点最近,但是需要找到的答案为 \(ans3\)

首先考虑 \(DFS\) ,一般是一搜搜到底,很有可能找到 \(ans1\) 。若继续查找,很有可能花费太多时间。时间效率低。

再来考虑 \(BFS\) ,它可以找到最近的答案 \(ans2\) 。若继续查找,很有可能存储状态的队列会浪费巨大空间。空间效率低

现在引出 \(IDDFS\) ,它通常适用于有两个条件的问题:一是它是个最优解问题,二是最优的答案深度最小。且能够快速地找到答案。

假设在搜索树中,每层树都有 \(3\) 个方案,即是搜索树为一颗 \(3\) 叉树,共 \(2\) 层, \(ans\)\(3\)

先来对比 \(DFS\) ,搜索路径为 \(1-2-5-2-6-2-7-2-1-3\) ,找到答案。有最坏情况,即每一个分支都是一个无底洞,若永远搜索不到答案,就会卡在里面。

再来对比 \(BFS\) ,搜索路径为 \(1-2-3\) ,看起来比较短,但是队列中有 \(1,2,5,6,7,3\) 的信息,若答案更深一些,那么就会炸空间。

通过上述两个例子,可以知道 \(DFS\)\(BFS\) 的局限性,但也各有千秋。结合两种算法,就有了迭代加深。首先限定一个层数,对于搜索树进行深度优先搜索。假设这个层数为 \(1\) ,那么深搜只会搜索到 \(2\) ,不会继续加深。首先试探性地来找答案,直到找到答案位置。很明显,上面几层的点会搜到很多遍,但时间复杂度对于 \(DFS\) 来说比较优,而在空间复杂度上比 \(BFS\) 上略胜一筹。

很容易就写出模板:

int max_depth = min_depth;
Id_Dfs( int current_depth  ,  int max_depth ) {
	if( current_depth > max_depth ) return ;
	if( 找到答案 ){ 输出答案 ; (exit(0) ;  ||  return ;) }
	for each ( 当前节点的儿子节点 )
	Id_Dfs(current_depth + 1, max_depth) ;
}
for(; ; max_depth++ ) {
	Id_Dfs( 0 , i ) ;
}

结合例题理解。

题目

一个与 \(n\) 有关的整数加成序列 \(<a_0,a_1,a_2,…,a_m>\) 满足以下四个条件:

  1. \(a_0=1\)
  2. \(a_m=n\)
  3. \(a_0<a_1<a_2<…<a_{m-1}<a_m\)
  4. 对于每一个 \(k(1≤k≤m)\) 都存在有两个整数 \(i\)\(j(0≤i,j≤k-1\)\(i\)\(j\) 可以相等 )) ,使得 \(a_k=a_i+a_j\)

你的任务是:给定一个整数 \(n\) ,找出符合上述四个条件的长度最小的整数加成序列。如果有多个满足要求的答案,只需要输出任意一个解即可。

思路

按照 \(1,2,4,8…\) 这样来排列,找出最少需要的次数那么最少的层数就找到了,就减少了之前做的无用功。

树上的子节点也较为好找,只需要将之前搜索到的数字,按照题意两两搭配找到下一项。

只需要按照 \(IDDFS\) 的规则搜索就行了。但重点在于剪枝,写在注释里的。

for(int i = nowdepth; i >= 1; i--) {
	for(int j = nowdepth; j >= i; j--) {//两两搭配,且答案越大越容易找到解,故而到着找
		if(ans[i] + ans[j] <= n && ans[i] + ans[j] > ans[nowdepth]) {//满足题意1,2两点的搜索
			int now;//找到下一项
			ans[nowdepth + 1] = now = ans[i] + ans[j];	
			for(int k = nowdepth + 2; k <= limit; k++)
//从nowdepth + 1这一项开始,后面最大时也就是now不停扩大2倍,若最大都达不到n,舍去不求
				now <<= 1;
			if(now < n)
				continue;
			Id_Dfs(nowdepth + 1);//搜索下一层
			if(flag)//找到答案
				return;
		}
	}
}

C++代码

#include <cstdio>
#include <cstring> 
bool Quick_Read(int &N) {
	N = 0;
	int op = 1;
	char c = getchar();
	while(c < '0' || c > '9') {
		if(c == '-')
			op = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9') {
		N = (N << 1) + (N << 3) + (c ^ 48);
		c = getchar();
	}
	N *= op;
	return N != 0;
}
void Quick_Write(int N) {
	if(N < 0) {
		putchar('-');
		N = -N;
	}
	if(N >= 10)
		Quick_Write(N / 10);
	putchar(N % 10 + 48);
}
const int MAXN = 1e5 + 5;
int ans[MAXN];
int limit;
bool flag;
int n;
void Id_Dfs(int nowdepth) {
	if(nowdepth > limit || flag)//达到层数不在恋战或找到答案,直接跳出
		return;
	if(ans[nowdepth] == n) {//满足题意
		flag = true;
		return;
	}
	for(int i = nowdepth; i >= 1; i--) {
		for(int j = nowdepth; j >= i; j--) {//两两搭配,且答案越大越容易找到解,故而到着找
			if(ans[i] + ans[j] <= n && ans[i] + ans[j] > ans[nowdepth]) {//满足题意1,2两点的搜索
				int now;//找到下一项
				ans[nowdepth + 1] = now = ans[i] + ans[j];	
				for(int k = nowdepth + 2; k <= limit; k++)
	//从nowdepth + 1这一项开始,后面最大时也就是now不停扩大2倍,若最大都达不到n,舍去不求
					now <<= 1;
				if(now < n)
					continue;
				Id_Dfs(nowdepth + 1);//搜索下一层
				if(flag)//找到答案
					return;
			}
		}
	}
}
void Work() {
	for(; !flag; limit++)//直到找到答案时停止搜索
		Id_Dfs(1);
	for(int i = 1; i < limit; i++) {//输出
		Quick_Write(ans[i]);
		putchar(' ');
	}
	putchar('\n');
}
void Init() {
	limit = 1;
	int test = 1;
	while(test < n) {//找到最小层数
		test <<= 1;
		limit++;
	}
	ans[1] = 1;
	flag = false;
}
int main() {
	while(Quick_Read(n)) {//多组输入输出,到0为止
		Init();
		Work();
	}
	return 0;
}


开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明[算法] 高级搜索算法之迭代加深
喜欢 (0)

您必须 登录 才能发表评论!

加载中……