回溯法之電路闆排列問題

問題描述

     将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}，L=｛N1，N2，N3，N4，N5｝，N1={4, 5, 6}，N2={2, 3}，N3={1, 3}，N4={3, 6}，N5={7, 8};其中可能的排列如圖所示，則該電路闆排列的密度是2。

     上圖中，跨越插槽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 
#include  
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 
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="<    cout<<"N1={4,5,6},N2={2,3},N3={1,3},N4={3,6},N5={7,8}"<    cout<<"二維數組B如下："< 
    //構造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++)
        {
            fin>>B[i][j];
            cout<         }             cout<    }         cout<<"目前最優密度為:"<    cout<<"最優排列為："<    for(int i=1; i<=n; i++)         {             cout<    }         cout<          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(cd>ld)                 {                     ld = cd;                 }                 if(ld            {                     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      inline void Swap(Type &a, Type &b)     {           Type temp=a;          a=b;          b=temp;     }           

View Code

實作結果：