POJ 3134：Power Calculus ← IDA*

【题目来源】
http://poj.org/problem?id=3134
https://www.luogu.com.cn/problem/UVA1374

【问题描述】
求最少用多少次乘法或除法，可以从x得到x^n。（每次只能从已经得到的数字里选择两个进行操作）
例如，x^31可以通过最少6次操作得到（5次乘，1次除）
x^2 = x*x
x^4 = (x^2)*(x^2)
x^8 = (x^4)*(x^4)
x^16 = (x^8)*(x^8)
x^32 = (x^16)*(x^16)
x^31 = (x^32)÷x

【算法分析】
BFS的遍历方式是按层进行的，所以BFS具有最短路的特性，而DFS不具有最短路的特性。由此可见，能用BFS解决的问题，DFS不一定可行。

本题Power Calculus，拟求最少次数，即求有最短路特性的指标，所以直觉上会选择BFS。但是，本题要求在求解x^n时，只能使用之前已经计算出的结果，但是BFS的最短路特性不能保证此结果已经算出。所以，在BFS和DFS之间做选择时，只能选择DFS来求解了。但是，本题事先无法确定搜索上界，若盲目选择DFS一搜到底的话，时间开销太大。因此，本题选择优化的DFS算法，即IDA*算法来求解。

IDA*=IDDFS+估价函数。其中，IDDFS 是 Iterative Deepening DFS 的缩写，意思是迭代加深搜索。由名字易知，IDDFS 是一种 DFS。估价函数 h() 的作用是预测从当前深度至少经过多少步才能到达目标状态。假设当前在第cur 层，则当 cur+h(cur)>maxd 时候，就说明不论怎么走，都不可能在 maxd 的限制之内找到目标状态，此时就可以进行“剪枝”操作。
IDA*算法的思路为：首先设定搜索深度 maxd=1，然后利用 DFS 在状态树的 maxd=1 深度之内进行搜索。如果没有找到解，就以搜索深度 maxd=2 进行搜索，……，直到成功找到解为止。其相应的标志性代码为：while(!dfs(maxd)) maxd++;

【算法代码】

#include 
using namespace std;
 
const int maxn=1005;
int a[maxn];
int maxd,n;
 
bool IDA(int pos) {
	if(pos>maxd) return 0; //IDDFS
	if(a[pos]==n) return 1;
	if(a[pos]<<(maxd-pos)return 0; //Pruning operation
	for(int i=0; i<=pos; i++) {
		a[pos+1]=a[pos]+a[i]; //add operation
		if(IDA(pos+1)) return 1;
		a[pos+1]=abs(a[pos]-a[i]); //subtract operation
		if(IDA(pos+1)) return 1;
	}
	return 0;
}
 
int main() {
	while(cin>>n) {
		if(n==0) break;
		a[0]=1;
		maxd=0;
		while(!IDA(0)) maxd++;
		printf("%d\n",maxd);
	}
	return 0;
}
 
 
 
/*
in:
1
31
70
91
473
512
811
953
0
out:
0
6
8
9
11
9
13
12
*/

【参考文献】
https://www.it610.com/article/4188067.htm
https://blog.csdn.net/qq_51392086/article/details/119426634