回溯法解电路板问题.cpp

算法分析中

/*
回溯法解电路板问题
设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之间的连线密度。
*/
#include<iostream>
using namespace std;

class Board
{
	friend Arrangement(int **,int,int,int[]);
private:
	void Backtrack(int i,int cd);
	//第一个参数搜索第i层，此时密度为cd
	int n;
	//电路板数，决定要搜索的排列树层数
	int m;
	//连接块数
	int *x;
	//当前解
	int *bestx;
	//当前最优解
	int bestd;
	//当前最优密度
	int *total;
	//total[j]=连接块j的电路板数
	int *now;
	//now[j]当前解中所含连接块j的电路板数
	int **B;
	//连接块数组
};

void Board::Backtrack(int i,int cd)
//回溯搜索排列树
{
	if ( i == n )
	{
		cout<<"处理最后部分"<<endl;
		for( int j = 1; j <= n; ++j )
		{
			bestx[j] = x[j];
		}
		bestd = cd;
		//得到所有的序列，并更新表示最小密度的变量
		cout<<"结束处理最后部分"<<endl;
	}
	else
	{
		for( int j = i; j <= n; ++j )
		//选择x[j]为下一块电路板
		{
			cout<<"开始"<<endl;
			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;
			}
			cout<<"结束"<<endl;
			
			cout<<"before"<<endl;
			if ( ld < bestd )
			//搜索子数，搜索前先交换被选中的到当前位置i处
			{
				int temp;
				temp = x[i];
				x[i] = x[j];
				x[j] = temp;
				Backtrack(i+1,ld);
				//返回上层要更新信息
				temp = x[i];
				x[i] = x[j];
				x[j] = temp;
				for( int k = 1; k <= m; ++k )
				{
					now[k] -= B[x[j]][k];
				}

			}
			cout<<"after"<<endl;
			
		}
	}

}

int Arrangement( int **B, int n, int m, int *bestx )
{
	Board X;
	X.x = 0;
	X.x = new int[n+1];
	if ( 0 == X.x )
	{
		return -1;
	}
	X.total = 0;
	X.total = new int[m+1];
	if ( 0 == X.total )
	{
		return -1;
	}
	X.now = 0;
	X.now = new int[m+1];
	if ( 0 == X.now )
	{
		return -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( 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 );
	for( i = 1; i <= n; ++i )
	{
		cout<<bestx[i]<<" ";
	}
	
	if ( 0 != X.x )
	{
		delete []X.x;
	}
	if ( 0 != X.total )
	{
		delete []X.total;
	}
	if ( 0 != X.now )
	{
		delete []X.now;
	}
	cout<<endl;
	cout<<X.bestd<<endl;
	return X.bestd;
}

/*
在电路板排列问题解空间的排列树的每个结点处，函数Backtrack花费O(m)计算时间
为每个儿子结点计算密度。因此，计算密度所耗费的总计算时间为O(mn!)。另外，生成排列树
需要O(n!)时间。更新当前最优解需要O(mn)时间。这是每次更新当前最优解至少使bestd减少1，
而算法运行结束时候bestd>=0。因此最优解被更新的次数为O(m)。
综上可知，解电路板排列问题的回溯算法Backtrack所需要的计算时间为O(mn!)
*/
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 );
	
	return 0;
}