前言

最開始搞 \(OI\) 的時候接觸了搜索演算法，后面基本上沒有在練過了，若本文有誤，請在討論區指出，

本文例題鏈接

思想

有時，答案不只一組，可能有多個，有些情況下需要找到有特殊情況的答案，

如上圖，需要找到的答案為 \(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;
}

標籤：其他

上一篇：前后端日常吵架——介面檔案誰來定義呢？

下一篇：第4章 二次同余式與平方剩余 -《資訊安全數學基礎》