回溯算法 --- 例题10.电路板排列问题

一.问题描述

电路板排列问题是大规模电子系统设计中提出的实际问题.
该问题是: 将n块电路板以最佳排列方案插入带有n个插槽的机箱中. n块电路板的不同的排列方式对应于不同的电路板插入方案.

将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，5。
比如:
对于第一幅图,可以看到跨越插槽2,3的有N2,N3两根导线(注意:一个连接块上的电路板由一根导线连接而成)
跨越插槽4,5的有N4,N1两根导线,同理可得跨越插槽5,6的也是N4,N1两根导线.
其余所有的相邻两个插槽都只跨越了一根导线,
故最终得到的密度就为2.

对于第二幅图,跨越插槽4,5的有N1,N2,N3,N4,N5五条导线.
跨越插槽3,4的有N3,N4,N1,N5四条导线,其它的就不举例了.最终密度为5
这样大家对于密度的定义是不是有了清晰的理解.

二.解题思路

电路板排列问题是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间的连线密度。

划重点!!!
对于这个条件的理解至关重要,我想了很久.
我们可以拿上面第一幅图来看:
先看now[j]>0,(now[j]表示的是x[1:i]中所包含的Nj的电路板数),now[j]大于零表示前面的i个插槽中有连接块j的电路板存在,很好理解.
now[j] != total[j]这里,如果当前面的i个插槽中已经用去了连接块j中的所有电路板,那么就是说剩下的插槽不可能再有连接块j的电路板了,也就不可能再被跨越!

同样的,一个插槽最多被一条导线跨越一次,比如上图1中,对于5,6号插槽来说,N1只跨越5,6插槽一次!故最大我们能够得到的密度为m,也就是每根导线都跨越了某个相邻槽,比如图2.

代码如下:

// 电路板排列问题
#include
using namespace std;
class Board
{
    friend int Arrangement(int **, int, int, int*);
    private:
        void Backtrack(int i, int cd);
        int n,      //电路板数
            m,      //连接块数
            *x,     //当前解
            *bestx, //当前最优解
            bestd,  //当前最优密度
            *total, //total[j]为连接块j的电路板数
            *now,   //now[j]为当前解中所含连接块j的电路板数
            **B;    //连接块数组
};
void Board::Backtrack(int i, int cd)        //回溯搜索排列树,cd表示已经确定的x[1:i]个插槽中相邻两个插槽被跨越数最大的(就是密度)
{
    static int k = 1;
    if(i == n)  //由于算法仅完成那些比当前最优解更好的排列,故cd肯定优于bestd,直接更新
    {
        cout<<"当前已经确定下来最后一个插槽,我们选择"<0 && total[k]!=now[k])  //判断是否发生了跨越(左边有,右边也有)
                    ld++;
            }
            cout<<"当前位于第"< ld)     //更新ld,cd为原来的最大密度,ld为当前的最大密度,哪个大取哪个  为什么要这么做?因为每一层我们只可以算出跨越插槽i和i+1的导线数,所以我们必须要和之前的最大值进行比较,取较大者(这是密度的定义)
            {    
                ld = cd;
                cout<<"ld>n>>m && n && m)
    {
        cout<<"输入连接块矩阵"<>B[i][j];
        int *bestx = new int[n+1];
        for(int i=1; i<=n; i++) bestx[i] = 0;
        int ans = Arrangement(B, n, m, bestx);
        cout<<"得到的最小密度为:"<

针对第一个图演示所得的结果:

运行结果:

我想清楚这题,人没了家人们,/(ㄒoㄒ)/~~
上课没听懂,放了好久才回来写题解.排列树我就不画了,画出来人要没了.
这题也可以将cd作为类的数据成员,从而减少Backtrack函数的传入参数,不过对效率并没有什么优化.
大伙应该能够看懂吧...

欢迎大家访问我的个人博客 --- 乔治的编程小屋,和我一起努力进步吧!