剪枝的由来:
暴力破解中,依靠计算机的强大计算能力时,必须考虑计算性能和计算限度
eg: 100W的双层for循环,计算机就会比较吃力,耗时较长.
如果某个问题考虑情况较多,我们可以尝试在逻辑中排除不可能的情况,或者从循环中找出一些规律来排除循环次数(eg 案例2),减少计算次数,这就是剪枝的由来。
案例如下:
public class pruning { public static void main(String[] args) { example2(); } /** * 剪枝-找钱问题---使用暴力破解(未含有枝剪) * 1 找8元钱 * 2有零钞: 5元,2元,1元,5角 * 问: 所有找钱方案 * * 将角换算成元,避免浮点数运算造成的误差 * 结果: 多个结果 ,此处没有列举 */ public static void example1(){ // x表示5元个数 y表示2元个数 z表示1元个数 m表示0.5元个数 int count = 0; for(int x=0; x<=80/50; x++){ for(int y=0; y<=80/20; y++){ for(int z=0; z<=80/10; z++){ for(int m=0; m<=80/5; m++){ ++count; if(x*50 + y*20 + z*10 + m*5 == 80){ System.out.println("第" +count + "次结果---> 5元为: " + x + "次" + " 2元为: " + y + "次" + " 1元为: " + z + "次" + " 5角为: " + m + "次"); } } } } } } /** * 剪枝: 尽早排除不合逻辑的情况, 在暴力破解情况下优化查询次数 * * 以上计算次数过多,增加过多无意义的计算 eg: 如果有一次5元,那么第二次2元循环中,只能最多出现1次,而没优化情况下,是从1次到4次都执行 */ public static void example2(){ // x表示5元个数 y表示2元个数 z表示1元个数 m表示0.5元个数 int count = 0; for(int x=0; x<=80/50; x++){ for(int y=0; y<=80/20; y++){ if((80 - 50*x - 20*y) < 0 ){break;} // 尽早排除不合逻辑的情况 for(int z=0; z<=80/10; z++){ if((80 - 50*x - 20*y - 10*z) < 0 ){break;} // 尽早排除不合逻辑的情况 ++count; int m = (80 - (x*50 + y*20 + z*10))/5; if(x*50 + y*20 + z*10 + m*5 == 80){ System.out.println("第" +count + "次结果---> 5元为: " + x + "次" + " 2元为: " + y + "次" + " 1元为: " + z + "次" + " 5角为: " + m + "次"); } } } } } }
案例2:
/** * 求n的平方尾数仍为n数本身的数字 */ public class square { public static void main(String[] args) { /*for(int i=0; i<10; i++){ int n = i*i; if(n%10 == i){ System.out.println("平方为: " + n + " 数字为: " + i); } }*/ for(int i=10; i<100; i++){ int n = i*i; int m = i%10; if(m != 0 && m!= 1 && m!= 5 && m!= 6){ // 如果个位数不是左侧这几种的话,那么平方后的结果个位数肯定和原数各位不一致,这情况下直接剪枝 continue; }; if(n%100 == i){ System.out.println("平方为: " + n + " 数字为: " + i); } } } }
相关推荐
Java-Gobang-master五子棋Java_java智能算法_基于剪枝算法的五子棋_javaGobang_源码
Java-Gobang-master_gobang五子棋Java_java智能算法_极大值_基于剪枝算法的五子棋_javaGobang_源码.zip
Apriori算法的剪枝算法
同学些的五子棋,采用了alpha-beta剪枝算法,棋力很强
树的直径问题,采用了剪枝算法,清华大学试题
这是一个带颜色UI界面的棋类游戏实现——tic tac toe(井字游戏) 编程语言:Visual C++ (MFC) 算法:alpha beta 剪枝算法
使用alpha-beta剪枝算法实现中国象棋人机对战,AI具有中级的智能,可以应对一般的象棋爱好者。
阿尔法贝塔剪枝算法五子棋
决策树后剪枝算法的研究,决策树后剪枝算法的研究,决策树后剪枝算法的研究
详细解析α-β剪枝算法过程,并且对原理进行了详细的说明。在最后用matlab代码实践了这个算法在五子棋中的应用。并且特别点名了该算法中容易犯错的地方。
人工智能作业αβ阿尔法贝塔剪枝极大极小算法实现井字棋,人机对战,控制台程序,可以直接运行,非常好用,可以下载参考学习
人工智能小项目,2048棋盘游戏,Alpha-beta剪枝算法, Expectimax搜索 。 人工智能的课程作业,非常简单易懂,纯Javascript实现,运用Alpha-beta剪枝算法,
基于Python剪枝算法的AI五子棋
这是一款智能五子棋游戏,可以用剪枝算法和进行了优化
算法面试通关40讲完整课件 32-34 剪枝 算法面试通关40讲完整课件 32-34 剪枝 算法面试通关40讲完整课件 32-34 剪枝 算法面试通关40讲完整课件 32-34 剪枝 算法面试通关40讲完整课件 32-34 剪枝 算法面试通关40讲完整...
基于多种模型剪枝方法(L1-norm、Slimming、AutoSlim)的模型轻量化和模型压缩实现
对于含有奇异点的系统而言,由于一般的剪枝算法不能成功抑制系统中的奇异点,在借鉴支持向量分类机选择支持向量方法的基础上,提出了改进的剪枝算法. 改进的剪枝算法能成功...
利用αβ剪枝 算法编写出五子棋游戏,可预测未来三步,含游戏界面
机器博弃是人工智能一个传统的研究领城。从机器博弃的基本搜索...绍基于c+十Builde潇言的中国象棋游戏的象棋a一p过程,并对象棋a一p剪枝搜索过程进行改进,提出更加 有效的算法,对改进后的搜索算法的效果进行评价。