POJ2248-Addition Chains-经典搜索题详解优化

Addition Chains

http://poj.org/problem?id=2248

解题思路

首先我们能够明显看出这题的范围在10以内，于是乎，迭代加深就是理所应当的了；
然后就是剪枝问题：

1.为了使序列快速逼近n，应该把从大到小地枚举 Num[i]与Num[j];
2.因为X[i]+X[j]=X[j]+X[i]，所以需要加一个记录，避免重复搜索某一个和；
	需要注意的是，因为查重针对每个分支生成的序列，故应该在DFS内部

总结

当一个问题的节点分支数很多，且我们能判断出它的层数不大，这时候就可以采用迭代加深的方法进行搜索；
迭代加深 思想的使用场景：
1.搜索树的规模随着层次的深入增长很快；
2.能够确保答案在较浅的节点时；

代码展示

#include<bits/stdc++.h>
using namespace std;
/*

*/
int num[15];int n;
int m; 

bool DFS(int lev){//bool类型的返回不能再像void 那样随意了，不必要就不用 
	if(lev>m){
		if(num[m]==n)
			return true;
		else 
			return false;//!!!!
	}
	bool vis[110]={false};
	for(int i=lev-1;i>=1;i--){
		for(int j=lev-1;j>=1;j--){
			if(num[i]+num[j]<=n&&!vis[num[i]+num[j]]&&num[lev-1]<num[i]+num[j]){
				num[lev]=num[i]+num[j];
				vis[num[i]+num[j]]=1;
				if(DFS(lev+1))return true;
				vis[num[i]+num[j]]=0;
			}
		}
	}
	return false;
}
int main(){
	while(cin>>n){
		num[1]=1;
		if(n==1)
			cout<<1<<endl;
		else {
			for(int i=2;i<=10;i++){
				m=i;
				//memset(vis,0,sizeof(vis));
				if(DFS(2)){
					for(int i=1;i<=m;i++)
						cout<<num[i]<<" ";
					cout<<endl;
					break;
				}
			}
		}
	}
	return 0;
}

最后

以上就是自由酸奶为你收集整理的POJ2248-Addition Chains-经典搜索题详解优化的全部内容，希望文章能够帮你解决POJ2248-Addition Chains-经典搜索题详解优化所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。