java版迭代回溯算法和递归回溯算法
上完回溯法的算法后,为了避免以后忘记了这些算法,自己实现了一遍,仅供大家学习参考,以下是代码:
package ctong; import java.util.Random; public class NQueen { /** * ctong */ //可行解数组,从X[1]开始使用 private static int[] X ; //X数组的长度 private static int nn ; //记录可行解数目 private static int sum=0; /** * 迭代算法 */ public void iteration(int n){ int k=1; while(k>0){ X[k]++; while(X[k]<n&&!place(k)){ X[k]++; } if(X[k]<n){ if(k==n-1){ print(); } else{ k++; X[k]=0; } }else k--; } } /** * 递归算法 */ public void recursion(int p){ for(X[p]=1;X[p]<nn;X[p]++){ if(place(p)){ if(p==nn-1){ print(); }else{ //递归调用 recursion(1+p); } } } } //是否可以放置? public boolean place(int t){ for(int i=1;i<t;i++){ if(Math.abs(i-t)==Math.abs(X[i]-X[t])||X[i]==X[t]) return false; } return true; } //创建一个随机长度(5~8)的数组 public static int[] createArray(){ nn =new Random().nextInt(3)+5; int[] a = new int[nn]; for(int i =0;i<nn;i++) a[i]=0; return a; } //打印函数 public void print(){ sum++; System.out.println("可行解"+sum); for(int j=1;j<X.length;j++) System.out.print(X[j]+" "); System.out.println(); } /** * 主函数 * @param args */ public static void main(String[] args) { X=createArray(); System.out.println("迭代回溯算法求得"+(X.length-1)+"皇后的可行解为:"); new NQueen().iteration(X.length); System.out.println("可行解的个数是:"+sum); sum=0; System.out.println("递归算法求得"+(X.length-1)+"皇后的可行解为:"); new NQueen().recursion(1); System.out.println("可行解的个数是:"+sum); } }
相关推荐
n后问题--非递归迭代回溯.rar n后问题--非递归迭代回溯.rar n后问题--非递归迭代回溯.rar n后问题--非递归迭代回溯.rar n后问题--非递归迭代回溯.rar n后问题--非递归迭代回溯.rar
n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---...
全都是自己写的,都能跑出来 实打实写的哦~ 仅供参考 最重要的还是自己理解 1.学习并掌握回溯法 2.利用迭代回溯和递归回溯两种方法解决01背包问题。 预览地址:
这是一个用Java实现的关于N皇后问题的算法 其中包括回溯和迭代两种算法
递归回溯,像8皇后问题,本质上和多重for 循环是一样的
确定了解空间的组织结构后,回溯法就从开始结点(根结点)出发,以深度优先的方式搜索整个解空间。...回溯法即以这种工作方式递归地在解空间中搜索,直至找到所要求的解或解空间中已没有活结点时为止。
0-1背包问题(包括递归版和两种迭代版,以及一个回溯算法版本) 最优矩阵链相乘问题(包括递归版和迭代版) 最大公共子序列问题(递归和迭代版) 最优二叉查找树(递归和迭代版) 生产作业装配线问题(递归,迭代) 活动...
算法分析与设计 回溯法 背包问题 递归与迭代
迭代法、穷举搜索法、递推法、递归、回溯法、贪婪法、分治法、动态规划法
第8章 回溯法学习要点:理解回溯法的深度优先搜索策略理解剪枝函数(约束函数和限界函数)的作用掌握回溯法解题的算法框架(1)递归回溯的算法框架(2)迭代回溯的算法
(1)递归回溯 (2)子集树算法框架 (3)迭代回溯 (4)排列树算法框架 二、实验内容: 问题描述 用排列树实现8皇后问题 算法主要思路 约束条件: ①不同列:x[i]!=x[k] ②不在各对角线上:abs(i-k)!=abs(x[i]...
另外,为了更简洁的形式设计和藐视算法,在算法设计时又常常采用递归技术,用递归描述算法。 一、迭代法 二、穷举搜索法 三、递推法 四、递归 五、回溯法 六、贪婪法 七、分治法 八、动态规划法
经典算法 1. 什么是迭代法 2. 什么是穷举搜索法 3. 什么是递推法 4. 什么是递归 5. 什么是回溯法 6. 什么是贪婪法 7. 什么是分治法 8. 什么是动态规划法
simple-sat, 在 python 中,编写了简单的递归和迭代SAT求解器 简单 SAT: 简单 python SAT求解器这个项目是一个简单的递归和迭代实现的回溯,基于观察的,SAT求解器。 代码基本上是基于knuth程序的,可以在这里找到 ...
算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解。如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向其祖先结点回溯;否则,进入该子树,继续按深度优先策略搜索。 回溯法指导思想——走不通...
今天小编就为大家分享一篇python 使用递归回溯完美解决八皇后的问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
算法设计技巧10.1 贪婪算法10.1.1 一个简单的调度问题10.1.2 哈夫曼编码...递归10.3.2 矩阵乘法的顺序安排10.3.3 最优二叉查找树10.3.4 所有点对最短路径10.4 随机化算法10.4.1 随机数发生器10.4.2 跳跃表10.4.3 素性...
算法设计技巧10.1 贪婪算法10.1.1 一个简单的调度问题10.1.2 哈夫曼编码...递归10.3.2 矩阵乘法的顺序安排10.3.3 最优二叉查找树10.3.4 所有点对最短路径10.4 随机化算法10.4.1 随机数发生器10.4.2 跳跃表10.4.3 素性...
第3章算法基本工具和优化技巧3.1循环与递归 3.1.1循环设计要点 3.1.2递归设计要点 3.1.3循环与递归的比较 3.2算法与数据结构 3.2.1原始信息与处理结果的对应存储 3.2.2数组使信息有序化 3.2.3数组记录状态信息 3.2.4...
10.5 回溯算法 10.5.1 收费公路重建问题 10.5.2 博弈 小结 练习 参考文献 第11章 摊还分析 11.1 一个无关的智力问题 11.2 二项队列 11.3 斜堆 11.4 斐波那契堆 11.4.1 切除左式堆中的节点 11.4.2 二项队列的懒惰...