回溯法解圆排列问题.cpp

算法分析中

/*
圆排列问题：
1.问题描述
给定n个大小不等的圆c1,c2,...,cn，现在将这n个圆排进一个矩形框中
要求各个圆与矩形框的底边相切。
圆排列问题要求从n个圆的所有排列找出有最小长度的圆排列。
2.算法设计
圆排列的解空间是一棵排列树。按照回溯法搜索排列树的算法框架，设开始
时a = r1,r2,...,rn是所给的n个圆的半径，则相应的排列树由a[1:n]的所有排列组成
*/
#include<iostream>
#include<math.h>
using namespace std;
class Circle
{
	friend float CirclePerm(int,float*);
private:
	float Center(int t);
	void Compute(void);
	void Backtrack(int t);
	float min;
	//当前最优值
	float *x;
	//当前圆排列圆心坐标
	float *r;
	//当前圆排列
	int n;
	//待排列圆的个数
};

float Circle::Center(int t)
{
	//计算当前所选择圆的圆心横坐标
	float temp = 0;
	for( int j = 1; j < t; ++j )
	{
		float valuex = x[j] + 2.0 * sqrt( r[t] * r[j] );
		//因为各个圆并没有排序，所以不确定是从哪个开始排列的
		//通过公式(r[t] + r[j])^2 - (r[j] - r[t])^2 = (x[j][t])^2，所以最大的值
		//应该是t与相邻的圆所求得的
		if ( valuex > temp )
		{
			temp = valuex;
		}
	}
	return temp;
}

void Circle::Compute(void)
{
	//计算当前圆排列的长度
	float low = 0;
	float high = 0;
	for ( int i = 1; i <= n; ++i )
	{
		if ( x[i] - r[i] < low )
		{
			low = x[i] - r[i];
		}
		//横坐标最小位置
		if ( x[i] + r[i] > high )
		{
			high = x[i] + r[i];
		}
		//横坐标最大位置，之所以这么做，是因为数组里面的圆并没有经过排序
	}
	if ( high - low < min )
	{
		min = high - low;
	}
}

void Circle::Backtrack(int t)
{
	if ( t > n )
	{
		Compute();
	}
	else
	{
		for( int j = t; j <= n; ++j )
		{
			int temp;
			temp = r[t];
			r[t] = r[j];
			r[j] = temp;
			//求全排列的话，在t位置选中哪个就把哪个交换到
			//r[t]处，然后不选的r[t]交换到那个位置去
			//通过交换可以把已经选种的和未选中的区分开
			float centerx = Center(t);
			if ( centerx + r[t] + r[1] < min )
				//当前总的长度
			{
				x[t] = centerx;
				Backtrack(t+1);
			}
			//返回到上层时要恢复状态
			temp = r[t];
			r[t] = r[j];
			r[j] = temp;
		}
	}
}

float CirclePerm(int n,float *a)
{
	Circle X;
	X.n = n;
	X.r = a;
	X.min = 100000;
	float *x = new float[n+1];
	X.x = x;
	X.Backtrack(1);
	delete []x;
	cout<<X.min<<endl;
	return X.min;
}

int main()
{
	float a[4] = { 0,1,1,2};
	int n = 3;
	CirclePerm(3,a);
	return 0;
}
/*
算法效率：
由于Backtrack在最坏情况下可能需要计算O(n!)次当前排列长度，
每次计算需要O(n)计算时间，从而整个算法的计算时间复杂性为
O((n+1)!)。
上述算法上有改进的余地，例如，像1，2，。。。，n-1,n和n,n-1,...,2,1这种互为镜像的排列具有相同的圆排列长度，只计算一次就够了。这样一来，可减少节约一半的计算量。另一方面，如果所给的n个圆中有K个圆有相同的半径，则这K个圆产生的K!个完全相同的圆排列，只计算一个就够了。
*/