圆排列问题.txt

圆排列问题 圆排列问题 &laquo 问题描述： n个半径不等的圆紧密排成一行

圆排列问题
                                      

圆排列问题
?问题描述：
n个半径不等的圆紧密排成一行，设计一个算法，使得这n个圆所排的长度最短。
?编程任务：
对于给定的n和圆半径a[1：n]，输出一个最优的圆排列方案。
方法：回溯法





class Circle
{
friend float CirclePerm(int,float*);
private:
float Center(int t);
void Compute(void);
void Backtrack(int t);
float min,//当前最优值
*x,//当前圆排列圆心横坐标
*r;//当前圆排列
int n;//待排列圆的个数
}；



float Circle::Center(int t)
{//计算当前所选择圆的圆心横坐标
float temp = 0;
for (int j = 1;j
{
float valuex = x[j] + 2.0*sqrt(r[t]*r[j]);
if (valuex > temp) temp = valuex;
}
return temp;
}




void Circle::Compute(void)
{//计算当前圆排列的长度
float 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::Backtrack(int t)
{
if (t > n) Compute();
else
for(int j = t;j<= n;j++)
{
Swap(r[t],r[j]);
float centerx = Center(t);
if (centerx + r[t] + r[1] < min)
{//下界约束
x[t] = centerx;
Backtrack(t+1);
}
Swap(r[t],r[j]);
}
}




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;
return X.min;
}

//圆排列的随机化算法

#include <fstream.h>
#include <iostream.h>
#include <math.h>
#include <time.h>

//==================随机数类===========================

const unsigned long maxshort=65536L;
const unsigned long multiplier=1194211693L;
const unsigned long adder=12345L;

class RandomNumber{
public:
 RandomNumber(unsigned long s=0);  //构造函数，缺省值0表示由系统自动产生种子
 unsigned short Random(unsigned long n);  //产生0：n-1之间的随机整数
 double fRandom(void); //产生[0,1)之间的随机实数
private:
 unsigned long randSeed;
};

RandomNumber::RandomNumber(unsigned long s)
{
 if(s==0)
  randSeed=time(0);
 else
  randSeed=s;
}

unsigned short RandomNumber::Random(unsigned long n)
{
 randSeed=multiplier*randSeed+adder;
 return(unsigned short)((randSeed>>16)%n);
}

double RandomNumber::fRandom(void)
{
 return Random(maxshort)/double(maxshort);
}

//===================圆排列类===========================


void Swap(float& x,float& y)
{
 float temp;
 temp=x;
 x=y;
 y=temp;
}

class Circle{
 friend float CirclePerm(int,float*);//返回找到的最小圆排列长度
private:
 void Center(void);//计算当前所有的圆在当前圆排列中圆心的横坐标
 float Compute(void);//计算当前圆排列的长度
 void Shuffle(void); //随机洗牌算法
 void CircleSearch(void); //解圆排列随机算法

 float min,//当前最优值
  result, //最优值
  *x,//当前圆排列圆心横坐标
  *r;//当前圆排列
 int n;//等排列圆的个数
};


void Circle::Center(void)
{
 for(int i=0;i<n;i++){
  float temp=0;
  for(int j=0;j<i;j++){
   float valuex=x[j]+(float)(2.0*sqrt(r[i]*r[j]));
   if(valuex>temp) temp=valuex;
  }
  x[i]=temp;
 }
}

float Circle::Compute(void)
{
 float low=0;
 float high=0;
 for(int i=0;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];
 }
 
 return (high-low);
}

void Circle::Shuffle(void)
{
 static RandomNumber rnd;
 
 for(int i=0;i<n;i++){
  int j=rnd.Random(n-i)+i;
  Swap(r[i],r[j]);
 }
}

void Circle::CircleSearch(void)
{
 Shuffle();
 Center();
 min=Compute();
 
 bool found=true;
 while(found){
  found=false;
  for(int i=0;i<n;i++)
   for(int j=0;j<n;j++){
    Swap(r[i],r[j]);
    Center();
    float length=Compute();
    if(length<min){
     min=length;
     found=true;
    }
    else Swap(r[i],r[j]);
   }
 }
 
}

    


float CirclePerm(int n,float* a)
{
 Circle X;
 X.n=n;
 X.r=a;
 
 float *x=new float[n];
 for(int i=0;i<n;i++) x[i]=0;
 X.x=x;
    X.CircleSearch();
 X.result=X.min;
 
   for(i=1;i<=50;i++){
  X.CircleSearch();
  if(X.result>X.min) {
    X.result=X.min;
  }

  }