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、回溯法的一般描述 可用回溯法求解的问题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）。

_'>回溯法解决0-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）

网页名称：回溯代码的模版java 回溯法c++代码
标题URL：http://myzitong.com/article/ddgpjjc.html