circle.h

回溯法实现最小圆排列问题

#include "iostream.h"
#include "math.h"

class Circle
{
	public:
		Circle(int, double *);
		~Circle();
		void Backtrack(int);
		void Print();
	private:
		double Center(int);
		void Compute(void);
		void Swap(double , double);
		double min,          //当前最优值
			   *x,           //当前圆排列圆心横坐标
			   *r;           //当前圆排列
		int n;               //待排列圆的个数
};

Circle::Circle(int n1, double *r1)
{
	n = n1;
	r = r1;
	min = 100000;
	x = new double [n+1];
	for(int i = 0; i <= n; i++)
	{
		x[i] = 0;
	}
}

Circle::~Circle()
{
	delete [] x;
}

void Circle::Backtrack(int t )
{
	if(t > n)
		Compute();
	else
		for(int j = t; j <= n; j++)
		{
			Swap(r[t], r[j]);
			double centerx = Center(t);
			if(centerx + r[t] + r[1] < min)
			{
				x[t] = centerx;
				Backtrack(t+1);
			}
			Swap(r[t], r[j]);
		}
}

void Circle::Print()
{
	int i;
	cout<<"最优的排列是："<<endl;
	for(i = 1; i <= n; i++)
	{
		cout<<r[i]<<endl;
	}
	cout<<"最优值是："<<endl;
	cout<<min<<endl;
}

double Circle::Center(int t)
{
	double temp = 0;
	for( int j = 1; j < t; j++)
	{
		double valuex = x[j] + 2.0 * sqrt(r[t] * r[j]);
		if(valuex > temp)
			temp = valuex;
	}
	return temp;
}

void Circle::Compute(void)
{
	double low = 0,
		   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::Swap(double a, double b)
{
	double temp = a;
	a = b;
	b = temp;
}