问题描述:
在一块电路板的上、下两端分别有n个接线柱。根据电路设计,要求用导线(i,π(i))将上端接线柱i与下端接线柱π(i)相连,如下图。其中,π(i),1≤i <≤n,是{1,2,…,n}的一个排列。导线(I,π(i))称为该电路板上的第i条连线。对于任何1≤i≤j≤n,第i条连线和第j条连线相交的充要条件是π(i)>π(j).
在制作电路板时,要求将这n条线分布到若干个绝缘层上,在同一层上的连线不能相交。电路布线问题要确定将哪些连线安排在第一层上,使得该层上有尽可能多的连线。换句话说,该问题要求确定导线集Nets ={i,π(i),1≤i≤n}的最大不想交子集。
问题分析:
1.最优子结构性质
记N(i,j) = {t|(t,π(i))∈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,π(i))∈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<i。从而MNS(i,j)包含于N(i-1,j),因此,Size(i,j)≤Size(i-1,j).
另一方面,MNS(i-1,j)包含于N(i,j),故又有Size(i,j)≥Size(i-1,j),从而Size(i,j)= Size(i-1,j).
2.递归计算最优值
经以上后分,可电路布线问题的最优值为Size(n,n)。由该问题的最优子结构性质可知:
C++程序:
//CircuitLayout.h
#ifndef CIRCUITLAYOUT_H
#define CIRCUITLAYOUT_H
class CircuitLayout{
private:
int count;//最大连线柱
int *c;//int **Size;//最大连线数目
int *net;//存储连线
bool Input();
int max(int,int);
void mnset(int *c,int **Size);//计算最优值
int traceback(int *c,int **Size,int *net);//构造最优解
public:
CircuitLayout();
~CircuitLayout();
bool Run();//运行接口函数
};
#endif
//CircuitLayout.cpp
#include "CircuitLayout.h"
#include <iostream>
#include <math.h>
using namespace std;
#define MAX(a,b) (((a)>(b)?(a):(b)))
#define M 50
//
CircuitLayout::CircuitLayout(){
int N = 0;
c = new int[M];
net = new int[M];
Size = new int*[M];
for(int i=0;i<M;++i)
Size[i] = new int[M];
}
//
CircuitLayout::~CircuitLayout(){
for(int i=0;i<M;++i)
delete []Size[i];
delete []Size;
delete []c;
delete []net;
}
//
bool CircuitLayout::Input(){
int n;
cout << "请输入接线柱的个数: ";
cin >> n;
count = n;
cout << "请依次输入被连接数: " << endl;
for(int i=0;i<n;++i)
cin >> c[i];
if(c) return true;
else return false;
}
int CircuitLayout::max(int a,int b){
if(a >= b) return a;else return b;
}
void CircuitLayout::mnset(int *c,int **Size){
int i=0;
int j=0;
int n = count-1;
for(j=0;j<c[1];j++)
Size[1][j] = 0;
for(j=c[1];j<=n;j++)
Size[1][j] = 1;
for (i=2;i<n;i++){
for (j=0; j<c[i] ; j++)
Size[i][j] = Size[i-1][j];
for (j=c[i];j<=n;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);
cout << "s[n][n]: " << Size[n][n] << endl;
}
//
int CircuitLayout::traceback(int *c,int **Size,int *net){
int n = count-1;
int j = n;
int m = 0;
for (int i=n;i>0;i--){
if (Size[i][j] != Size[i-1][j]){
net[m++] = i;j = c[i] - 1;
}
}
if(j>=c[0])
net[m++] = 0;
for(int k=0;k<m;++k)
cout << "net: " << net[k] << " ";
cout << endl;
return m;
}
///
bool CircuitLayout::Run(){
int msize = 0;
if(Input()){
mnset(c,Size);
msize = traceback(c,Size,net);
cout << "msize: "<< msize;
cout << endl;return true;
}
else return false;}
//
int main(){
CircuitLayout xiaoli;
xiaoli.Run();
return 0;
}
如果觉得《电路布线(动态规划C++实现)》对你有帮助,请点赞、收藏,并留下你的观点哦!