百度网站排名,做钓鱼网站原理,电子版邀请函制作软件免费,重庆电子商务网站目录
闲聊
前言 DFS算法的无效搜索 BFS算法的空间浪费 IDDFS A*算法 IDA*
Power Calculus 问题描述 输入 输出
问题分析
代码 闲聊 前几周在忙着数学竞赛#xff0c;所以就没时间更新#xff0c;高等数学#xff0c;一生之敌#xff0c;真不知道报名的时候我是怎么想…目录
闲聊
前言 DFS算法的无效搜索 BFS算法的空间浪费 IDDFS A*算法 IDA*
Power Calculus 问题描述 输入 输出
问题分析
代码 闲聊 前几周在忙着数学竞赛所以就没时间更新高等数学一生之敌真不知道报名的时候我是怎么想的看了几个星期宋浩就跑的去丢人现眼了_),没几题会做的。就算是捐款了。
前言 这次讲的是IDA*算法有关IDA*算法我想先聊聊IDFS,BFSIDDFSA*这些图算法。 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 1n1000) 输出 对于每个测试输出最小的步数
问题分析 两个幂函数相乘除指数相加减那么这个问题就可以简化为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都无法到达那么说明这个深度不行这个深度以上都没有答案需要到更深的地方搜索答案
代码
#includeiostream
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输出还是31return 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 depth1;; 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;
}
大学生数学竞赛我能力还是不行下次再战说什么都要入一次决赛
