扫二维码与项目经理沟通
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解；倘若当前候选解除了还不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，以继续试探的过程称为向前试探。 1、回溯法的一般描述 可用回溯法求解的问题P，通常要能表达为：对于已知的由n元组（x1，x2，…，xn）组成的一个状态空间E={（x1，x2，…，xn）∣xi∈Si ，i=1，2，…，n}，给定关于n元组中的一个分量的一个约束集D，要求E中满足D的全部约束条件的所有n元组。其中Si是分量xi的定义域，且 |Si| 有限，i=1，2，…，n。我们称E中满足D的全部约束条件的任一n元组为问题P的一个解。 解问题P的最朴素的方法就是枚举法，即对E中的所有n元组逐一地检测其是否满足D的全部约束，若满足，则为问题P的一个解。但显然，其计算量是相当大的。 我们发现，对于许多问题，所给定的约束集D具有完备性，即i元组（x1，x2，…，xi）满足D中仅涉及到x1，x2，…，xi的所有约束意味着j（ji）元组（x1，x2，…，xj）一定也满足D中仅涉及到x1，x2，…，xj的所有约束，i=1，2，…，n。换句话说，只要存在0≤j≤n-1，使得（x1，x2，…，xj）违反D中仅涉及到x1，x2，…，xj的约束之一，则以（x1，x2，…，xj）为前缀的任何n元组（x1，x2，…，xj，xj+1，…，xn）一定也违反D中仅涉及到x1，x2，…，xi的一个约束，n≥ij。因此，对于约束集D具有完备性的问题P，一旦检测断定某个j元组（x1，x2，…，xj）违反D中仅涉及x1，x2，…，xj的一个约束，就可以肯定，以（x1，x2，…，xj）为前缀的任何n元组（x1，x2，…，xj，xj+1，…，xn）都不会是问题P的解，因而就不必去搜索它们、检测它们。回溯法正是针对这类问题，利用这类问题的上述性质而提出来的比枚举法效率更高的算法。 回溯法首先将问题P的n元组的状态空间E表示成一棵高为n的带权有序树T，把在E中求问题P的所有解转化为在T中搜索问题P的所有解。树T类似于检索树，它可以这样构造： 设Si中的元素可排成xi(1) ，xi(2) ，…，xi(mi-1) ，|Si| =mi，i=1，2，…，n。从根开始，让T的第I层的每一个结点都有mi个儿子。这mi个儿子到它们的双亲的边，按从左到右的次序，分别带权xi+1(1) ，xi+1(2) ，…，xi+1(mi) ，i=0，1，2，…，n-1。照这种构造方式，E中的一个n元组（x1，x2，…，xn）对应于T中的一个叶子结点，T的根到这个叶子结点的路径上依次的n条边的权分别为x1，x2，…，xn，反之亦然。另外，对于任意的0≤i≤n-1，E中n元组（x1，x2，…，xn）的一个前缀I元组（x1，x2，…，xi）对应于T中的一个非叶子结点，T的根到这个非叶子结点的路径上依次的I条边的权分别为x1，x2，…，xi，反之亦然。特别，E中的任意一个n元组的空前缀（），对应于T的根。 因而，在E中寻找问题P的一个解等价于在T中搜索一个叶子结点，要求从T的根到该叶子结点的路径上依次的n条边相应带的n个权x1，x2，…，xn满足约束集D的全部约束。在T中搜索所要求的叶子结点，很自然的一种方式是从根出发，按深度优先的策略逐步深入，即依次搜索满足约束条件的前缀1元组（x1i）、前缀2元组（x1，x2）、…，前缀I元组（x1，x2，…，xi），…，直到i=n为止。 在回溯法中，上述引入的树被称为问题P的状态空间树；树T上任意一个结点被称为问题P的状态结点；树T上的任意一个叶子结点被称为问题P的一个解状态结点；树T上满足约束集D的全部约束的任意一个叶子结点被称为问题P的一个回答状态结点，它对应于问题P的一个解。 【问题】 组合问题 问题描述：找出从自然数1、2、……、n中任取r个数的所有组合。 例如n=5，r=3的所有组合为： （1）1、2、3 （2）1、2、4 （3）1、2、5 （4）1、3、4 （5）1、3、5 （6）1、4、5 （7）2、3、4 （8）2、3、5 （9）2、4、5 （10）3、4、5 则该问题的状态空间为： E={（x1，x2，x3）∣xi∈S ，i=1，2，3 } 其中：S={1，2，3，4，5} 约束集为： x1x2x3 显然该约束集具有完备性。 问题的状态空间树T： 2、回溯法的方法 对于具有完备约束集D的一般问题P及其相应的状态空间树T，利用T的层次结构和D的完备性，在T中搜索问题P的所有解的回溯法可以形象地描述为： 从T的根出发，按深度优先的策略，系统地搜索以其为根的子树中可能包含着回答结点的所有状态结点，而跳过对肯定不含回答结点的所有子树的搜索，以提高搜索效率。具体地说，当搜索按深度优先策略到达一个满足D中所有有关约束的状态结点时，即“激活”该状态结点，以便继续往深层搜索；否则跳过对以该状态结点为根的子树的搜索，而一边逐层地向该状态结点的祖先结点回溯，一边“杀死”其儿子结点已被搜索遍的祖先结点，直到遇到其儿子结点未被搜索遍的祖先结点，即转向其未被搜索的一个儿子结点继续搜索。 在搜索过程中，只要所激活的状态结点又满足终结条件，那么它就是回答结点，应该把它输出或保存。由于在回溯法求解问题时，一般要求出问题的所有解，因此在得到回答结点后，同时也要进行回溯，以便得到问题的其他解，直至回溯到T的根且根的所有儿子结点均已被搜索过为止。 例如在组合问题中，从T的根出发深度优先遍历该树。当遍历到结点（1，2）时，虽然它满足约束条件，但还不是回答结点，则应继续深度遍历；当遍历到叶子结点（1，2，5）时，由于它已是一个回答结点，则保存（或输出）该结点，并回溯到其双亲结点，继续深度遍历；当遍历到结点（1，5）时，由于它已是叶子结点，但不满足约束条件，故也需回溯。 3、回溯法的一般流程和技术 在用回溯法求解有关问题的过程中，一般是一边建树，一边遍历该树。在回溯法中我们一般采用非递归方法。下面，我们给出回溯法的非递归算法的一般流程： 在用回溯法求解问题，也即在遍历状态空间树的过程中，如果采用非递归方法，则我们一般要用到栈的数据结构。这时，不仅可以用栈来表示正在遍历的树的结点，而且可以很方便地表示建立孩子结点和回溯过程。 例如在组合问题中，我们用一个一维数组Stack[ ]表示栈。开始栈空，则表示了树的根结点。如果元素1进栈，则表示建立并遍历（1）结点；这时如果元素2进栈，则表示建立并遍历（1，2）结点；元素3再进栈，则表示建立并遍历（1，2，3）结点。这时可以判断它满足所有约束条件，是问题的一个解，输出（或保存）。这时只要栈顶元素（3）出栈，即表示从结点（1，2，3）回溯到结点（1，2）。
成都创新互联公司是专业的东区网站建设公司，东区接单;提供成都网站设计、成都网站制作,网页设计,网站设计,建网站,PHP网站建设等专业做网站服务;采用PHP框架,可快速的进行东区网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,专业的做网站团队,希望更多企业前来合作!
N皇后问题的非递归迭代回溯法java代码实现
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class NQueen {
static int n; // 皇后个数
static int[] x; // 当前解如{0，2，4，1，3}分别代表第1、2、3、4列的行值
static int totle; // 可行方案个数
public static void main(String[] args) {
int input = 0; //输入n值
int sum = 0; //可行方案个数
String temp; //临时存储输入值
System.out.println("请输入N后问题的N值：");
try {
BufferedReader br = new BufferedReader(new InputStreamReader(
System.in));
temp = br.readLine();
input = Integer.parseInt(temp); //将输入值转换为int保存
if(input=0){
throw new IOException("别输负数好不？");
}
System.out.println("输入的数是：" + input);
sum = nQueen(input); //调用nqueen方法
System.out.println("可行方案个数为：" + sum); //输出sum
} catch (IOException e) {
System.out.println(e.getMessage());
}catch (NumberFormatException e){
System.out.println("请输入数字。。。");
}
}
private static int nQueen(int input) {
n = input; //把输入给全局变量n
totle = 0; //初始化totle
x = new int[n + 1];
for (int i = 0; i = n; i++)
x[i] = 0; //初始化x
backtrack(); //调用回溯算法
return totle;
}
private static void backtrack() {
int k = 1;
while (k 0) {
x[k] += 1; //第k列皇后向下移一行
while ((x[k] = n) !(place(k))){ //如果当前第k列皇后未出界或者和其他皇后冲突
x[k] += 1; //第k列皇后向下移一行继续寻找
System.out.println("在第"+k+"行 "+"第"+x[k]+"列放置皇后");
System.out.print("当前方案为 ");
for(int i=1;i=k;i++) //打印寻找策略
System.out.print(x[i]+" ");
System.out.println();
}
if (x[k] = n) //找到一个值并且未出界
if (k == n) { //已是最后一列说明已找到一个方案
totle++;
System.out.print("可行方案为： ");
for (int i = 1; i = n; i++)
System.out.print(x[i] + " ");
System.out.println();
} else { //不是最后一列故寻找下一列
k++;
x[k] = 0;
}
else //找到的值已经出界，回退到上一列
k--;
}
}
//判断皇后是否冲突
private static boolean place(int k) {
for (int j = 1; j k; j++)
if ((Math.abs(k - j) == Math.abs(x[j] - x[k])) || (x[j] == x[k]))
return false;
return true;
}
}
递归的精华就在于大问题的分解，要学会宏观的去看问题，如果这个大问题可以分解为若干个性质相同的规模更小的问题，那么我们只要不断地去做分解，当这些小问题分解到我们能够轻易解决的时候，大问题也就能迎刃而解了。如果你能独立写完递归创建二叉树，前序、中序、后序递归遍历以及递归计算二叉树的最大深度，递归就基本能掌握了。回溯本人用得很少，仅限于八皇后问题，所以帮不上啥了。
你main方法也没有加上，这样吧，我给你看代码，这个比较容易理解。
package com.aice.queen;
public class Queen{
//同栏是否有皇后，1表示有
private int[]column;
//右上至左下是否有皇后
private int[]rup;
//左上至右下是否有皇后
private int[]lup;
//解答
private int[]queen;
//解答编号
private int num;
public Queen(){
column = new int[8+1];
rup =new int[(2*8)+1];
lup = new int[(2*8)+1];
for(int i = 1;i=8;i++)
column[i]=1;
for(int i = 1;i=(2*8);i++)
rup[i] = lup[i] = 1;
queen = new int[8+1];
}
public void backtrack(int i){
if(i8){
showAnswer();
}else{
for(int j=1;j=8;j++){
if((column[j]==1)(rup[i+j]==1)
(lup[i-j+8]==1)){
queen[i]=j;
//设定为占用
column[j]=rup[i+j]=lup[i-j+8]=0;
backtrack(i+1);
column[j]=rup[i+j]=lup[i-j+8]=1;
}
}
}
}
protected void showAnswer(){
num++;
System.out.println("\n解答"+num);
for(int y=1;y=8;y++){
for(int x=1;x=8;x++){
if(queen[y]==x){
System.out.print("Q");
}else{
System.out.print(".");
}
}
System.out.println();
}
}
public static void main(String[]args){
Queen queen = new Queen();
queen.backtrack(1);
}
}
Java回溯没接触过。这题是刚开始下一状态为不可使用状态，想要实现如何从绿-》红-》黑的变换吗？方向是单向的
因为你把n和c 定义为static ,而且初始化为0,。数组也为静态的,一个类中静态的变量在这个类加载的时候就会执行，所以当你这类加载的时候，你的数组static int[] v = new int[n];
static int[] w = new int[n];
就已经初始化完毕，而且数组大小为0。在main方法里动态改变n的值是改变不了已经初始化完毕的数组的大小的，因为组已经加载完毕。
我建议你可以在定义n,c是就为其赋初值。比如（static int n=2 static int c=3）
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
微信二维码
移动版官网