「Java回朔法」java回溯算法
今天给各位分享Java回朔法的知识，其中也会对java回溯算法进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！
本文目录一览：
- 1、java回溯和递归的区别，主要什么回溯怎么用，有代码最好
- 2、Java或者C/C++怎么用回溯法解决最小长度电路板排列问题
- 3、五大基本算法——回溯法
- 4、java 深度优先搜索（回溯法）求集合的幂集
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或者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。
左上图中，跨越插槽2和3,4和5，以及插槽5和6的连线数均为2。插槽6和7之间无跨越连线。其余插槽之间只有1条跨越连线。在设计机箱时，插槽一侧的布线间隙由电路板的排列的密度确定。因此，电路板排列问题要求对于给定的电路板连接条件(连接块)，确定电路板的最佳排列，使其具有最小密度。
问题分析
电路板排列问题是NP难问题，因此不大可能找到解此问题的多项式时间算法。考虑采用回溯法系统的搜索问题解空间的排列树，找出电路板的最佳排列。设用数组B表示输入。B[i][j]的值为1当且仅当电路板i在连接块Nj中。设total[j]是连接块Nj中的电路板数。对于电路板的部分排列x[1:i]，设now[j]是x[1:i]中所包含的Nj中的电路板数。由此可知，连接块Nj的连线跨越插槽i和i+1当且仅当now[j]0且now[j]！=total[j]。用这个条件来计算插槽i和i+1间的连线密度。
重点难点
算法具体实现如下：
//电路板排列问题 回溯法求解
#include "stdafx.h"
#include iostream
#include fstream
using namespace std;
ifstream fin("5d11.txt");
class Board
{
friend int Arrangement(int **B, int n, int m, int bestx[]);
private:
void Backtrack(int i,int cd);
int n, //电路板数
m, //连接板数
*x, //当前解
*bestx,//当前最优解
bestd, //当前最优密度
*total, //total[j]=连接块j的电路板数
*now, //now[j]=当前解中所含连接块j的电路板数
**B; //连接块数组
};
template class Type
inline void Swap(Type a, Type b);
int Arrangement(int **B, int n, int m, int bestx[]);
int main()
{
int m = 5,n = 8;
int bestx[9];
//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}
cout"m="m",n="nendl;
cout"N1={4,5,6},N2={2,3},N3={1,3},N4={3,6},N5={7,8}"endl;
cout"二维数组B如下："endl;
//构造B
int **B = new int*[n+1];
for(int i=1; i=n; i++)
{
B[i] = new int[m+1];
}
for(int i=1; i=n; i++)
{
for(int j=1; j=m ;j++)
{
finB[i][j];
coutB[i][j]" ";
}
coutendl;
}
cout"当前最优密度为:"Arrangement(B,n,m,bestx)endl;
cout"最优排列为："endl;
for(int i=1; i=n; i++)
{
coutbestx[i]" ";
}
coutendl;
for(int i=1; i=n; i++)
{
delete[] B[i];
}
delete[] B;
return 0;
}
//核心代码
void Board::Backtrack(int i,int cd)//回溯法搜索排列树
{
if(i == n)
{
for(int j=1; j=n; j++)
{
bestx[j] = x[j];
}
bestd = cd;
}
else
{
for(int j=i; j=n; j++)
{
//选择x[j]为下一块电路板
int ld = 0;
for(int k=1; k=m; k++)
{
now[k] += B[x[j]][k];
if(now[k]0 total[k]!=now[k])
{
ld ++;
}
}
//更新ld
if(cdld)
{
ld = cd;
}
if(ldbestd)//搜索子树
{
Swap(x[i],x[j]);
Backtrack(i+1,ld);
Swap(x[i],x[j]);
//恢复状态
for(int k=1; k=m; k++)
{
now[k] -= B[x[j]][k];
}
}
}
}
}
int Arrangement(int **B, int n, int m, int bestx[])
{
Board X;
//初始化X
X.x = new int[n+1];
X.total = new int[m+1];
X.now = new int[m+1];
X.B = B;
X.n = n;
X.m = m;
X.bestx = bestx;
X.bestd = m+1;
//初始化total和now
for(int i=1; i=m; i++)
{
X.total[i] = 0;
X.now[i] = 0;
}
//初始化x为单位排列并计算total
for(int i=1; i=n; i++)
{
X.x[i] = i;
for(int j=1; j=m; j++)
{
X.total[j] += B[i][j];
}
}
//回溯搜索
X.Backtrack(1,0);
delete []X.x;
delete []X.total;
delete []X.now;
return X.bestd;
}
template class Type
inline void Swap(Type a, Type b)
{
Type temp=a;
a=b;
b=temp;
}
算法效率
在解空间排列树的每个节点处，算法Backtrack花费O(m)计算时间为每个儿子节点计算密度。因此计算密度所消耗的总计算时间为O(mn!)。另外，生成排列树需要O(n!)时间。每次更新当前最优解至少使bestd减少1，而算法运行结束时bestd=0。因此最优解被更新的额次数为O(m)。更新最优解需要O(mn)时间。综上，解电路板排列问题的回溯算法Backtrack所需要的计算时间为O(mn!)。
程序运行结果为：
五大基本算法——回溯法
回溯法是一种选优搜索法（试探法）。
基本思想：将问题P的状态空间E表示成一棵高为n的带全有序树T，把求解问题简化为搜索树T。搜索过程采用 深度优先搜索 。搜索到某一结点时判断该结点是否包含原问题的解，如果包含则继续往下搜索，如果不包含则向祖先回溯。
通俗来说，就是利用一个树结构来表示解空间,然后从树的根开始深度优先遍历该树，到不满足要求的叶子结点时向上回溯继续遍历。
几个结点：
扩展结点：一个正在产生子结点的结点称为扩展结点
活结点：一个自身已生成但未全部生成子结点的结点
死结点：一个所有子结点已全部生成的结点
1、分析问题，定义问题解空间。
2、根据解空间，确定解空间结构，得 搜索树 。
3、从根节点开始深度优先搜索解空间（利用 剪枝 避免无效搜索）。
4、递归搜索，直到找到所要求的的解。
1、子集树
当问题是：从n个元素的集合S中找出满足某种性质的子集时，用子集树。
子集树必然是一个二叉树。常见问题：0/1背包问题、装载问题。
遍历子集树时间复杂度：O（2^n）
2、排列树
当问题是：确定n个元素满足某种排列时，用排列数。常见问题：TSP旅行商问题，N皇后问题。
遍历排列树时间复杂度：O（n!）
通俗地讲，结合Java集合的概念，选择哪种树其实就是看最后所得结果是放入一个List（有序）里，还是放入一个Set（无序）里。
剪枝函数能极大提高搜索效率，遍历解空间树时，对于不满足条件的分支进行剪枝，因为这些分支一定不会在最后所求解中。
常见剪枝函数：
约束函数（对解加入约束条件）、限界函数（对解进行上界或下界的限定）
满足约束函数的解才是可行解。
1、0/1背包问题
2、TSP旅行商问题
3、最优装载问题
4、N-皇后问题
具体问题可百度详细内容。
java 深度优先搜索（回溯法）求集合的幂集
import java.util.ArrayList;
import java.util.List;
public class BackTrack {
public static void main(String[] args) {
//初始化一个集合，放在list里面
ListString list=new ArrayListString();
list.add("1");
list.add("2");
list.add("3");
list.add("f");
ListString li=new ArrayListString();
PowerSet(0,list,li);
}
//回溯法求幂集
public static void PowerSet(int i,ListString list,ListString li){
if(ilist.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]
[]
关于Java回朔法和java回溯算法的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。
发布于：2022-12-21，除非注明，否则均为原创文章，转载请注明出处。