电路布线.cpp

算法分析部分

/*
将n条连线分布到若干个绝缘层上。在同一层上的连线不相交。
电路布线问题就是要确定将哪些连线安排在第一层上，使得该层上尽可能多的连线。
换句话说，该问题要求确定导线集的最大不相交子集
*/
/*
最优子结构性质：
记N(i,j) = {t|(t,u(t))属于Nets,t<=i,u(t)<=j},N(i,j)的最大不相交
子集为MNS(i,j),Size(i,j) = {MNS(i,j)}
(1)当i==1时
MNS(i,j) = N(1,j) = 空 ,j<u(1)
         = {(1,u(1))}, j>=u(1)
(2) 当i>1时
    1，j<u(i)此时，(i,u(i))不属于N(i,j)。故在此情况下N(i,j) = N(i-1,j),
	从而Size(i,j) = Size(i-1,j)。
	2，j>=u(i)，此时
	若(i,u(i))属于MNS(i,j)，则对任意(t,u(t))属于MNS(i,j)有t<i且u(t)<u(i).
	否则(t,u(t))与(i,u(i))相交。在这种情况下，MNS(i,j) - {(i,u(i))}是N(i-1,u(i)-1)的一个最大不相交子集合。
	否则子集
*/
/*
递归计算最优值：
电路布线问题的最优值是：
（1）当i==1时
Size(i,j) = 0, j < u(1)
          = 1, j >=u(1)
（2）当i>1时
Size(i,j) = Size(i-1,j), j<u(i)
          = max{Size(i-1,j),Size(i-1,u(i)-1)+1},j>=u(i)
*/
/*
算法实现如下:
其中用二维数组单元size[i][j]表示函数Size(i,j)的值
*/
#include<iostream>
using namespace std;

int max( int a, int b )
{
	if ( a > b )
	{
		return a;
	}
	else
	{
		return b;
	}
}

void MNS( int C[], int n, int **size )
{
	for( int j = 0; j < C[1]; ++j )
	{
		size[1][j] = 0;
	}
	for( 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];
		}
		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);
}

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] )
		{
			Net[m++] = i;
			j = C[i] - 1;
		}
	}
	if ( j >= C[1] )
	{
		Net[m++] = 1;
	}
}

int main()
{
	int c[11] = {0,1,2,3,4,5,6,7,8,9,10 };
	int n = 10;
	int **size = new int*[n+1];
	for( int i = 0; i < n+1; ++i )
	{
		size[i] = new int[n+1];
		for( int j = 0; j < n+1; ++j )
		{
			size[i][j] = 0;
		}
	}
	MNS( c, n, size );
	for( i = 0; i < n+1; ++i )
	{
		for( int j = 0; j < n+1; ++j )
		{
			cout<<size[i][j]<<" ";
		}
		cout<<endl;
	}
	return 0;
}