java回溯
‘壹’ java或者C/C++怎么用回溯法解决最小长度电路板排列问题
以java为例，希望能够帮到你。
电路板排列问题
问题描述
将n块电路板以最佳排列方式插入带有n个插槽的机箱中。n块电路板的不同排列方式对应于不同的电路板插入方案。设B={1, 2, …, n}是n块电路板的集合，L={N1, N2, …, Nm}是连接这n块电路板中若干电路板的m个连接块。Ni是B的一个子集，且Ni中的电路板用同一条导线连接在一起。设x表示n块电路板的一个排列，即在机箱的第i个插槽中插入的电路板编号是x[i]。x所确定的电路板排列Density (x)密度定义为跨越相邻电路板插槽的最大连线数。
例：如图，设n=8, m=5，给定n块电路板及其m个连接块：B={1, 2, 3, 4, 5, 6, 7, 8}，N1={4, 5, 6}，N2={2, 3}，N3={1, 3}，N4={3, 6}，N5={7, 8};其中两个可能的排列如图所示，则该电路板排列的密度分别是2，3。
‘贰’ JAVA怎么用回溯法打印出1，2,3,4的所有组合和排列
/*
*组合 回溯
*a为源数据，调用时用f(a,0,"")
*/
void f(int[] a,int n,String v){
if(n==a.length){
System.out.println(v);
}else{
f(a,n+1,v);
f(a,n+1,v+","+a[n]);
}
}
‘叁’ java 八皇后问题 递归 回溯
你main方法也没有加上，这样吧，我给你看代码，这个比较容易理解。
packagecom.aice.queen;
publicclassQueen{
//同栏是否有皇后，1表示有
privateint[]column;
//右上至左下是否有皇后
privateint[]rup;
//左上至右下是否有皇后
privateint[]lup;
//解答
privateint[]queen;
//解答编号
privateintnum;
publicQueen(){
column=newint[8+1];
rup=newint[(2*8)+1];
lup=newint[(2*8)+1];
for(inti=1;i<=8;i++)
column[i]=1;
for(inti=1;i<=(2*8);i++)
rup[i]=lup[i]=1;
queen=newint[8+1];
}
publicvoidbacktrack(inti){
if(i>8){
showAnswer();
}else{
for(intj=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;
}
}
}
}
protectedvoidshowAnswer(){
num++;
System.out.println(" 解答"+num);
for(inty=1;y<=8;y++){
for(intx=1;x<=8;x++){
if(queen[y]==x){
System.out.print("Q");
}else{
System.out.print(".");
}
}
System.out.println();
}
}
publicstaticvoidmain(String[]args){
Queenqueen=newQueen();
queen.backtrack(1);
}
}
‘肆’ java回溯法如何执行
回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解；倘若当前候选解除了还不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，以继续试探的过程称为向前试探。 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（j<i）元组（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≥i>j。因此，对于约束集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} 约束集为： x1<x2<x3 显然该约束集具有完备性。 问题的状态空间树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）。
‘伍’ java异常处理的机制有哪几种
Java语言提供两种异常处理机制：捕获异常和声明抛弃异常；
1）捕获异常：在Java程序运行过程中系统得到一个异常对象是，它将会沿着方法的调用栈逐层回溯，寻找处理这一异常的代码。找到能够处理这种类型异常的方法后，运行时系统把当前异常交给这个方法处理；如果找不到可以捕获异常的方法，则运行时系统将终止，相应的Java程序也将退出。捕获异常是通过try-catch-finally语句实现的。语法为：
try{
...
}catch(ExceptionName1 e){
...
}catch(ExceptionName2 e){
...
}
...
}finally{
...
}
‘陆’ java回溯和递归的区别，主要什么回溯怎么用，有代码最好
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;
}
}
‘柒’ JAVA中八皇后问题算法和流程图。要求用回溯法，求大神解答，在线等如果有代码就完美了
[cpp] view plainprint?
//--------------------------------------
//利用函数递归，解决八皇后问题
//
// zssure 2014-03-12
//--------------------------------------
#include <stdio.h>
#include <cmath>
int count=0;//全局计数变量
/*--------------------四个皇后----------------------*/
//#define QUEEN_NUM 4
//int label[QUEEN_NUM][QUEEN_NUM]={ 0,0,0,0,
// 0,0,0,0,
// 0,0,0,0,
// 0,0,0,0 };
/*--------------------五个皇后----------------------*/
//#define QUEEN_NUM 5
//int label[QUEEN_NUM][QUEEN_NUM]={ 0,0,0,0,0,
// 0,0,0,0,0,
// 0,0,0,0,0,
// 0,0,0,0,0,
// 0,0,0,0,0 };
/*--------------------六个皇后----------------------*/
//#define QUEEN_NUM 6
//int label[QUEEN_NUM][QUEEN_NUM]={ 0,0,0,0,0,0,
// 0,0,0,0,0,0,
// 0,0,0,0,0,0,
// 0,0,0,0,0,0,
// 0,0,0,0,0,0,
// 0,0,0,0,0,0
// };
/*--------------------七个皇后----------------------*/
//#define QUEEN_NUM 7
//int label[QUEEN_NUM][QUEEN_NUM]={ 0,0,0,0,0,0,0,
// 0,0,0,0,0,0,0,
// 0,0,0,0,0,0,0,
// 0,0,0,0,0,0,0,
// 0,0,0,0,0,0,0,
// 0,0,0,0,0,0,0,
// 0,0,0,0,0,0,0
// };
/*--------------------八个皇后----------------------*/
#define QUEEN_NUM 8
int label[QUEEN_NUM][QUEEN_NUM]={0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0};
void FillChessbox(int m,int n,int num)
{
for(int i=0;i<QUEEN_NUM;++i)
for(int j=0;j<QUEEN_NUM;++j)
if(abs(i-m)==abs(j-n))//对角区域填充
{
if(label[i][j]==0)
label[i][j]=num;
}
int i=0,j=0;
while(i<QUEEN_NUM)//行填充
{
if(label[i][n]==0)
label[i][n]=num;
++i;
}
while(j<QUEEN_NUM)//列填充
{
if(label[m][j]==0)
label[m][j]=num;
++j;
}
}
void ClearChessBox(int m,int n,int num)
{
for(int i=0;i<QUEEN_NUM;++i)
for(int j=0;j<QUEEN_NUM;++j)
if(abs(i-m)==abs(j-n) && label[i][j]==num)
label[i][j]=0;
int i=0,j=0;
while(i<QUEEN_NUM)
{
if(label[i][n]==num)
label[i][n]=0;
++i;
}
while(j<QUEEN_NUM)
{
if(label[m][j]==num)
label[m][j]=0;
++j;
}
}
void AllClear()
{
for(int i=0;i<QUEEN_NUM;++i)
for(int j=0;j<QUEEN_NUM;++j)
label[i][j]=0;
}
void PrintResult()
{
for(int i=0;i<QUEEN_NUM;++i)
{
for(int j=0;j<QUEEN_NUM;++j)
printf("%d ",label[i][j]);
printf("\n");
}
}
bool EightQueen(int n/*皇后个数*/,int c/*已经放置的皇后个数*/)
{
//static int count=0;
//小于3x3的棋盘是无解的
if(n<4)
return false;
for(int i=0;i<n;++i)
{
if(label[c-1][i]==0)//存在可以放置第c个皇后的位置
{
label[c-1][i]=c+1;
if(c==n)/*已经放置完毕所有的皇后*/
{
++count;
PrintResult();
printf("**************************\n");
ClearChessBox(c-1,i,c+1);
//AllClear();
return true;
}
FillChessbox(c-1,i,c+1);
EightQueen(n,c+1);
ClearChessBox(c-1,i,c+1);
/*-------------------------------------------------------------------------------------------------------------------------
// 现场恢复，无论下一个皇后是否顺利放置，都应该恢复现场。原因是
//
// 如果下一个皇后放置失败，那么自然应该将本次放置的皇后去除，重新放置，所以需要进行现场恢复（即回溯）；
// 如果下一个皇后放置成功，意味着本次放置已经满足条件，是一个解，此时需要恢复现场，进行下一次的重新放置，寻找下一个解。
//
//------------------------------------------------------------------------------------------------------------------------*/
//if(!EightQueen(n,c+1))
// ClearChessBox(c-1,i,c+1);
}
}
return false;
}
int main()
{
EightQueen(QUEEN_NUM,1);
printf("%d\n",count);
return 0;
}
‘捌’ java 深度优先搜索（回溯法）求集合的幂集
import java.util.ArrayList;
import java.util.List;
public class BackTrack {
public static void main(String[] args) {
//初始化一个集合，放在list里面
List<String> list=new ArrayList<String>();
list.add("1");
list.add("2");
list.add("3");
list.add("f");
List<String> li=new ArrayList<String>();
PowerSet(0,list,li);
}
//回溯法求幂集
public static void PowerSet(int i,List<String> list,List<String> li){
if(i>list.size()-1){System.out.println(li);}
else{
li.add(list.get(i));//左加
PowerSet(i+1,list,li); //递归方法
li.remove(list.get(i)); //右去
PowerSet(i+1, list, li);
}
}
}
注：该方法采用中序遍历二叉树（实际这棵树是不存在的）。对于第一个元素，左节点加进去，右节点去掉。对于第i一个节点，左加，右去。直到i大于元素的总个数。
输出结果：
[1, 2, 3, 4]
[1, 2, 3]
[1, 2, 4]
[1, 2]
[1, 3, 4]
[1, 3]
[1, 4]
[1]
[2, 3, 4]
[2, 3]
[2, 4]
[2]
[3, 4]
[3]
[4]
[]
‘玖’ 20 java回溯和递归的区别，主要什么回溯怎么用，有代码最好
递归的精华就在于大问题的分解，要学会宏观的去看问题，如果这个大问题可以分解为若干个性质相同的规模更小的问题，那么我们只要不断地去做分解，当这些小问题分解到我们能够轻易解决的时候，大问题也就能迎刃而解了。如果你能独立写完递归创建二叉树，前序、中序、后序递归遍历以及递归计算二叉树的最大深度，递归就基本能掌握了。回溯本人用得很少，仅限于八皇后问题，所以帮不上啥了。