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;
}

大学生数学竞赛我能力还是不行，下次再战，说什么都要入一次决赛！