「java怎么回溯」java回溯模板

今天给各位分享java怎么回溯的知识，其中也会对java回溯模板进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！

本文目录一览：

• 1、五大基本算法——回溯法
• 2、Java或者C/C++怎么用回溯法解决最小长度电路板排列问题
• 3、JAVA怎么用回溯法打印出1，2,3,4的所有组合和排列

五大基本算法——回溯法

回溯法是一种选优搜索法（试探法）。

基本思想：将问题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或者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!)。

程序运行结果为：

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怎么回溯和java回溯模板的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。