【動態(tài)規(guī)劃】電路布線問題

1、問題描述：

在一塊電路板的上、下兩端分別有n個接線柱。根據(jù)電路設(shè)計，要求用導(dǎo)線(i,π(i)) 將上端接線柱i與下端接線柱π(i)相連，如下圖。其中，π(i),1≤ i ≤n,是{1,2,…,n｝的一個排列。導(dǎo)線(I, π(i))稱為該電路板上的第i條連線。對于任何1 ≤ i ≤ j ≤n,第i條連線和第j條連線相交的充要條件是π(i)> π(j).

π(i)={8，7，4，2，5，1，9，3，10，6｝

在制作電路板時，要求將這n條連線分布到若干絕緣層上。在同一層上的連線不相交。電路布線問題要確定將哪些連線安排在第一層上，使得該層上有盡可能多的連線。換句話說，該問題要求確定導(dǎo)線集Nets = {i，π(i)，1 ≤ i ≤ n｝的最大不相交子集。

2、最優(yōu)子結(jié)構(gòu)性質(zhì)：

記N(i,j) = {t|(t, π(t)) ∈ Nets,t ≤ i, π(t) ≤ j }. N(i,j)的最大不相交子集為MNS(i,j)Size(i,j)=|MNS(i,j)|。

(1)當i = 1時

(2)當i >1時

① j <π(i)。此時，(i,π(i)) 不屬于N(i,j)。故在這種情況下，N(i,j) = N(i-1,j)，從而Size(i,j)=Size(i-1,j)。

② j ≥π(i)。此時，若(i, π(i))∈MNS(i,j)，則對任意(t, π(t))∈MNS(i,j)有t < i且π(t)< π(i);否則，(t, π(t))與(i, π(i))相交。在這種情況下MNS(i,j)-{(i, π(i))}是N(i-1, π(i)-1)的最大不相交子集。否則，子集MNS(i-1, π(i)-1)∪{(i, π(i))}包含于N(i,j)是比MNS(i,j)更大的N(i,j)的不相交子集。這與MNS(i,j)的定義相矛盾。

若(i, π(i))不屬于MNS(i,j)，則對任意(t, π(t))∈MNS(i,j)，有t

另一方面，MNS(i-1,j)包含于N(i,j),故又有Size(i,j) ≥Size(i-1,j)，從而Size(i,j)= Size(i-1,j)。

3、遞推關(guān)系

電路布線問題的最優(yōu)值為Size(n,n)。由該問題的最優(yōu)子結(jié)構(gòu)性質(zhì)可知，子問題最優(yōu)值的遞歸關(guān)系如下：

自底向上，先算上排接線柱只有1個，2個的最優(yōu)布線，然后求上排接線柱有多個的最優(yōu)布線。具體代碼如下：

//3d8 動態(tài)規(guī)劃 電路布線問題
#include "stdafx.h"
#include <iostream>
using namespace std;

const int N = 10;

void MNS(int C[],int n,int **size);
void Traceback(int C[],int **size,int n,int Net[],int& m);

int main()
{
 int c[] = {0,8,7,4,2,5,1,9,3,10,6};//下標從1開始
 int **size = new int *[N+1];

 for(int i=0; i<=N; i++)
 {
  size[i] = new int[N+1];
 }

 MNS(c,N,size);

 cout<<"電路布線最大不相交連線數(shù)目為："<<size[N][N]<<endl;

 int Net[N],m;
 Traceback(c,size,N,Net,m);

 cout<<"最大不相交連線分別為："<<endl;
 for(int i=m-1; i>=0; i--)
 {
  cout<<"("<<Net[i]<<","<<c[Net[i]]<<") ";
 }
 cout<<endl;
 return 0;
}

void MNS(int C[],int n,int **size)
{
 for(int j=0;j<C[1];j++)
 {
  size[1][j]=0;
 }

 for(int j=C[1]; j<=n; j++)
 {
  size[1][j]=1;
 }

 for(int i=2; i<n; i++)
 {
  for(int j=0; j<C[i]; j++)
  {
   size[i][j]=size[i-1][j];//當i<c[i]的情形
  }
  for(int j=C[i]; j<=n; j++)
  {
   //當j>=c[i]時，考慮(i，c[i])是否屬于MNS(i,j)的兩種情況
   size[i][j]=max(size[i-1][j],size[i-1][C[i]-1]+1);
  }
 }
 size[n][n]=max(size[n-1][n],size[n-1][C[n]-1]+1);
}

void Traceback(int C[],int **size,int n,int Net[],int& m)
{
 int j=n;
 m=0;
 for(int i=n;i>1;i--)
 {
  if(size[i][j]!=size[i-1][j])//此時，（i,c[i])是最大不相交子集的一條邊
  {
   Net[m++]=i;
   j=C[i]-1;//更新擴展連線柱區(qū)間
  }
 }
 if(j>=C[1])//處理i=1的情形
 {
  Net[m++]=1;
 }
}

算法MNS時間和空間復(fù)雜度為O(n^2)。Traceback時間復(fù)雜度為O(n)。程序運行結(jié)果如下：