电路板排列问题.cpp

算法分析中

#include<iostream>
using namespace std;

/*
设x表示n块电路板的一个排列，即在机箱的第i个插槽中插入电路板x[i]
x所确定的电路板排列密度density(x)定义为跨越相邻电路板插槽的最大连接数
在设计机箱，插槽一侧的布线间隙由电路板排列的密度所确定
因此电路板排列问题要求对于给定电路板连接条件（连接块），确定电路板的最佳排列，使
其具有最小的密度
    算法中用整型数组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之间的连线密度。

电路板排列问题的解空间树是一棵排列树。我们采用优先队列式分支限界法找出
所给的电路板的最小密度布局。算法中用一个最小堆来表示活结点优先队列。
最小堆中元素类型是BoardNode。每一个BoardNode类型的结点包含域x，用来表示
结点所相应的电路板排列；s表示该结点已确定的电路板排列x[1:s];cd表示当前密度
;now[j]表示x[1:s]中所含连接块j中的电路板数。具体算法描述如下：
*/

class BoardNode
{
	friend int BBArrangement( int**, int, int, int* & );
public:
	operator int() const
	{
		return cd;
	}
	bool operator>( const BoardNode& a ) const
	{
		return cd > a.cd;
	}

	bool operator<( const BoardNode& a ) const
	{
		return cd < a.cd;
	}
private:
	int *x;
	//x[1:n]记录电路板排列
	int s;
	//x[1:s]是当前结点所相应的部分排列
	int cd;
	//x[1:s]的密度
	int* now;
	//now[j]是x[1:s]所含连接块j中电路板数目
};

/*
函数BBArrangement是解电路板排列问题的优先队列式分支限界法的主体。
算法开始的时候，将排列树的根结点置为当前扩展结点。
在初始扩展结点处还没有
选定电路板，故s=0,cd=0,now[i]=0,1<=i<=n。且数组x初始化为单位排列。数组total
初始化为total[i],等于连接块i所含电路板数目。bestd表示当前最小密度，bestx是
相应的最优解。
算法的do-while循环完成对排列树内部结点的有序扩展。在do-while循环体内算法依次从
活结点优先队列中取出具有最小cd值的结点作为当前扩展结点，并加以扩展。
如果当前扩展结点的cd>=bestd,则优先队列中其余活结点都不可能导致最优解，
此时算法结束。
算法将当前扩展结点分为两种情形处理。首先考虑s=n-1的情形，此时已排定n-1块
电路板，故当前扩展结点是排列树中的一个叶结点的父结点。x表示相应于该叶结点的电路板
排列。计算出与x相应的密度并在必要时更新当前最优值bestd和相应的当前最优解bestx。
当s<n-1时，算法依次产生当前扩展结点的所有儿子结点。对于当前扩展结点的每一个
儿子结点N，计算出其相应的密度N.cd。当n.cd<bestd时，将该儿子结点N插入到活结点
优先队列中。而当N.cd>=bestd时，以N为根的子树中不可能有比当前最优解bestx更好的
解，故可将结点N舍去。
*/

template<class Type>
class MinHeap
{
	public:
		Type *H;
		int Capacity;
		int Size;
	public:
		MinHeap(int n)
		{
			H = NULL;
			H = (Type*)malloc( sizeof( Type ) * ( n + 1 ) );
			Capacity = n;
			Size = 0;
		}
		MinHeap( MinHeap& a )
		{
			//要排除自赋值的情况
			if ( this.H != a.H )
			{
				this.H = a.H;
				this.Size = a.Size;
				this.Capacity = a.Capacity;
				for( int i = 0; i < Size; ++i )
				{
					this.H[i] = a.H[size];
				}
			}
		}

		/*
		基本的堆插入操作
		为了将node插入到堆中
		首先在下一个空闲位置++Size处，创建一个空穴，否则该堆将不是完全树
		如果x可以放在该穴中而不破坏堆的序，那么插入完成
		否则我们把空穴的父亲结点上的元素移动到该穴中，这样空穴就朝着根的方向上行一步
		继续该过程直到x能被放入空穴为止
		*/
		void Insert( Type& node )
		{
			int i;
			cout<<"Size = "<<Size<<endl;
			for( i = ++Size; H[i / 2] > node; i /= 2 )
			{
				H[i] = H[i / 2];
				if ( i / 2 == 0 )
				{
					break;
				}
			}
			H[i] = node;
			
		}

		/*
		当删除一个最小元时
		在根结点处产生一个空穴。
		由于现在堆少了一个元素，因此堆中最后一个元素必须移动到该堆的某个地方
		如果x可以放到空穴中，那么DeleteMin完成
		否则应该将两个儿子中较小者移入空穴
		这样空穴就向下推了一层。重复该步骤直到x可以被放入空穴中
		*/
		void DeleteMin( Type& node )
		{
			int i,Child;
			Type MinElement,LastElement;
			MinElement = H[ 1 ];
			LastElement = H[Size--];

			for( i = 1; i * 2 <= Size; i = Child )
			{
				Child = i * 2;
				if ( ( Child != Size && H[ Child + 1 ] < H[ Child ] ) )
				{
					Child++;
				}

				if ( LastElement > H[ Child ] )
				{
					H[ i ] = H[ Child ];      
				}
				else
				{
					break;
				}
			}
			H[i] = LastElement;
			node = MinElement;
		}
};

int max( int a, int b )
{
	int maxint = 0;
	maxint = a > b ? a : b;
	return maxint;
}

int BBArrangement( int** B, int n, int m, int* &bestx )
{
	//解电路板排列问题的优先
	MinHeap< BoardNode > H(1000);
	//活结点最小堆
	BoardNode E;
	E.x = new int[n+1];
	E.s = 0;
	E.cd = 0;
	E.now = new int[m+1];
	int *total = new int[m+1];
	//now[i] = x[1:s]所含连接块i中电路板数
	//total[i]=连接块i中电路板数
	for( int i = 1; i <= m; ++i )
	{
		total[i] = 0;
		E.now[i] = 0;
	}

	for( i = 1; i <= n; ++i )
	{
		E.x[i] = i;
		//初始排列为12345...n
		for( int j = 1; j <= m; ++j )
		{
			total[j] += B[i][j];
			//连接块j中电路板数
			//初始花的时候，如果i在j块，就有B[i][j]=1，所以这里可以做好判定
		}
	}

	int bestd = m + 1;
	//当前最小密度
	bestx = 0;
	//首先初始化一个最小密度结点

	do
	{
		//结点扩展
		if ( E.s == n - 1 )
		{
			//仅一个儿子结点
			int ld = 0;
			//最后一块电路板的密度
			for( int j = 1; j <= m; ++j )
			{
				ld += B[E.x[n]][j];
			}
			//看最后一个结点的密度大小

			if ( ld < bestd )
			{
				//如果最后一个增加后的密度小于获得的最小密度，则求出结果如果大于
				delete []bestx;
				bestx = E.x;
				bestd = max( ld, E.cd );
				//一个组合的最小密度求出，下才不断的找比他小的密度
			}
			else
			{
				//delete []E.x;
			}
			//delete []E.now;
		}
		else
		{
			//产生当前扩展结点的所有儿子结点
			for( int i = E.s + 1; i <= n; ++i )
			{
				BoardNode N;
				N.now = new int[m+1];
				for( int j = 1; j <= m; ++j )
				{
					//新插入的电路板
					N.now[j] = E.now[j] + B[E.x[i]][j];
				}
				int ld = 0;
				//新插入电路板的密度
				for( j = 1; j <= m; ++j )
				{
					if ( N.now[j] > 0 && total[j] != N.now[j] )
					{
						ld++;
					}
					//说明当前结点下还有和其他结点的交叉，也就是密度要加1
				}
				N.cd = max( ld, E.cd );
				if ( N.cd < bestd )
				{
					//可能产生更好的叶子结点
					N.x = new int[n+1];
					N.s = E.s + 1;
					for( int j = 1; j <= n; ++j )
					{
						N.x[j] = E.x[j];
					}
					//初始化新结点，利用E结点进行初始化，将E结点中所选择的
					//所有的结点进行初始化
					N.x[N.s] = E.x[i];
					//先确定N.s结点是哪个
					N.x[i] = E.x[N.s];
					//然后要确定第i个结点应该是
					//实际是实现了两个结点的交换，因为是全排列
					//i,N.s交换信息

					H.Insert( N );
				}
				else
				{
					delete []N.now;
				}
			}
			//delete []E.x;
			//完成当前结点扩展
		}

		/*try
		{
			H.DeleteMin(E);
			//取下一个扩展结点
		}
		catch(OutOfBounds)
		{
			return bestd;
			//无扩展结点
		}*/
		if ( H.Size == 0 )
		{
			return bestd;
		}
		else
		{
			H.DeleteMin(E);
			//取下一个扩展结点
		}
	}
	while(E.cd < bestd );

	//释放最小堆中所有结点
	do
	{
		//delete []E.x;
		//delete []E.now;
		try
		{
			H.DeleteMin(E);
		}
		catch(...)
		{
			break;
		}
	}while(true);

	cout<<"bestd is : "<<bestd<<endl;

	return bestd;
}

int main()
{
	int **B = 0;
	B = new int*[9];
	if ( 0 == B )
	{
		return -1;
	}
	for( int i = 0; i < 9; ++ i )
	{
		B[i] = 0;
		B[i] = new int[6];
		if ( 0 == B[i] )
		{
			return -1;
		}
		for( int j = 0; j < 6; ++j )
		{
			B[i][j] = 0;
		}
	}

	B[4][1] = 1;
	B[5][1] = 1;
	B[6][1] = 1;

	B[2][2] = 1;
	B[3][2] = 1;

	B[1][3] = 1;
	B[3][3] = 1;

	B[3][4] = 1;
	B[6][4] = 1;

	B[7][5] = 1;
	B[8][5] = 1;

	int n = 8;
	int m = 5;

	int *bestx = new int[9];
	for( int s = 0; s < 9; ++s )
	{
		for( int s1 = 0; s1 < 6; ++s1 )
		{
			cout<<B[s][s1]<<" ";
		}
		cout<<endl;
	}
	//Arrangement( B, n, m, bestx );
	BBArrangement( B, n, m, bestx );
	
	return 0;
}