IDA*算法 Power Calculus————poj 3134
目录
闲聊
前言
DFS算法的无效搜索
BFS算法的空间浪费
IDDFS
A*算法
IDA*
Power Calculus
问题描述
输入
输出
问题分析
代码
闲聊
前几周在忙着数学竞赛，所以就没时间更新，高等数学，一生之敌，真不知道报名的时候我是怎么想的，看了几个星期宋浩，就跑的去丢人现眼了（@_@),没几题会做的。就算是捐款了。
前言
这次讲的是IDA*算法，有关IDA*算法，我想先聊聊IDFS,BFS，IDDFS，A*这些图算法。
DFS算法的无效搜索
dfs算法又叫深度优先算法，就是对一个图搜索时，这个算法是一条完整路径一条完整路径搜索，怎么算一条完整路径呢，简单数对于一棵树从他的根节点到叶子节点，对于一个复杂的图，就是他搜索的最后一个节点没办法再衍生出其他路径的时候，假设我吗要对一棵树使用dfs进行遍历，就会发现如果这棵树很深，但是答案又在非常浅的地方，就会导致大量的无效搜索。
BFS算法的空间浪费
bfs算法又叫广度优先搜索，简单说就是一层一层的进行搜索，但写过bfs算法的都知道，对于每一层，我们一般都需要开出一定的空间来存储当前层的信息，以便进行下一层的搜索，如果这棵树比较复杂，那么这个空间消耗也是非常大的。
IDDFS
前面说明了BFS算法和DFS算法的缺点，我们现在来说说他们的优点，BFS算法的优点就是对于答案再很浅的层级时，这个算法很高效，没有过多的无效搜索，DFS算法的优点就是空间消耗非常少，因为它只需要开出一条路径的内存即可，而这条路径的深度绝对不会超过树的深度，可以发现，这两个算法其实是互补的，如果我们可以将两个算法适当结合，那么将极大提高算法的时间，空间效率，这就是IDDFS算法。
IDDFS算法是一个限制深度的DFS算法，不是说人家dfs总是一股脑往一条路走吗，那么我们给他加一个限制让他不要一直走下去不就行了吗。在代码上体现就是再原本dfs的基础上增加一个剪枝，如果当前搜索深度大于我所设定的深度，就return
A*算法
我觉得这应该不算一种算法，应该算一种思想，就是如果我可以根据现有的条件推断将来我一定完不成这个任务，那么就及时止损。形象点就是给算法加上一对预知未来的眼睛，具体有关A*算法设计可以看看我前面的文章A*算法
IDA*
如果说IDDFS算法还有可以优化的空间，我想结合A*算法一定是不二之选，所有搜索算法其实都有一个通病，就是搜索的盲目性，这也就是大部分搜索算法大家都习惯叫暴力法，如果结合A*算法使得搜索算法具有一定的目的性，那么将极大地摆脱“暴力”的标签。（由于A*算法其实是一种思想，所以没有具体的算法模板，需要大量的练习强化）。
Power Calculus
问题描述
问x经过最少经过到少次乘除运算可以到达x的n次方
输入
有多个测试每个测试输入一个整数n （1<=n<=1000)
输出
对于每个测试输出最小的步数
问题分析
两个幂函数相乘（除），指数相加（减），那么这个问题就可以简化为1经过多少次加减运算可以到达n。一开始我其实是想用动态规划计算的，因为后一个状态需要用到前一步的条件，然后打表，只用x，然后x平方，等等，但是我发现这个其实还有个除的过程，而且其实每一个子问题是用前一个子问题的解解决的，这不是动态规划，反而更像是分治法的思想，最后只好老老实实用分治做，其实dfs本质上也是个分治，怎么说呢，就是搜索到一个节点的路径可以由到与他有关系的节点的路径推得，而这两个问题又是两个独立的问题，好了扯远了，本题使用dfs算法
确实这题用dfs好像能过，但我们也可以想一想能不能玩出点花样来，用刚刚讲的IDA*算法
- 首先是IDDFS的核心——限制深度
if (now > depth) return false; //IDDFS剪枝 - 之后就是A*算法思想———预测
if (sum << (depth - now) < n) return false; //A_star算法剪枝这个代码讲一下，首先这里使用了移位符号，相当于sum×2的（depth-now）次方，就是如果以sum增长最快的方式接近n都无法到达，那么说明这个深度不行，这个深度以上都没有答案，需要到更深的地方搜索答案
代码
#include<iostream>
using namespace std;
int da[15]; //路径数组
bool IDA_star(int n,int sum,int now,int depth) {
if (now > depth) return false; //IDDFS剪枝
da[now] = sum; //记录深度为depth路径上各个点的信息
if (sum << (depth - now) < n) return false; //A_star算法剪枝
if (sum == n) return true; //找到答案结束
for (int i = 1; i <= now;i++) {
//代码中必须保证两个IDA_star都被执行，才可以保证所有情况都被搜索
/*
像这样的写法就是错的，它会导致程序在没找到答案之前提前终止，导致下面的IDA_star没办法执行
（一开始我就是这样写的，结果输入31输出还是31）
return IDA_star(n, sum + da[i], now + 1, depth);
return IDA_star(n, sum - da[i], now + 1, depth);
*/
//两种情概况
if(IDA_star(n, sum + da[i], now + 1, depth)) return true;
if(IDA_star(n, sum - da[i], now + 1, depth)) return true;
}
//最好还是在这里也return一下，保证程序的完整性
return false;
}
int main() {
int n;
while (~scanf_s("%d", &n) && n) {
//逐渐增加深度
for (int depth=1;; depth++) {
if (IDA_star(n,1,1,depth)) {
//注意这里的depth是从1开始的代表的是路径深度，及路径上节点个数，但是要输出路径长度需要数路径上的边，数值上等于节点数减一
cout << depth-1 << endl;
//打印路径代码
/*for (int i = 1; i <= depth; i++) {
cout << da[i] << " ";
}*/
break;
}
}
}
return 0;
}大学生数学竞赛我能力还是不行，下次再战，说什么都要入一次决赛！