圆排列问题
自己收藏的
觉得很有用
故上传到百度
与大家一起分享！
圆排列问题
一、问题描述
给定N个大小不等的圆C1
C2
...
现将这N个圆排进一个矩形框中
且要求个圆与矩形框的底边相切
圆排列问题要求从N个圆的所有排
二、算法设计
圆排列问题的解空间是一棵排列树
按照回溯法搜索排列树的算法框架
设开始时a=[r1
r2
...
rn]是所给的N个圆的半径
则相应的排列树由a=[1：n]的所有排列构成
解圆的排列问题的回溯算法中circlePerm（n
a）返回找到的最小圆排列长度
初始时
数组a的输入N个圆的半径
计算结束后返回相应于最优解的圆排列
Center用于计算当前所选择的圆在当前排列中圆心的横坐标
compute 用于计算当前圆排列的长度
变量min用于记录当前最小圆排列的长度；数组r表示当前圆排列；数组x则记录当前圆排列中各圆的圆心横坐标
算法中约定在当前圆排列中排在第一个的圆的横坐标为0
在递归算法中bracktrack中
当i >n时
算法搜索至叶结点
得到新的圆方案
此时算法调用compute 计算当前圆排列的长度
适时更新当前最优值
当i
当前扩展结点位于排列树的第I-1层
此时算法选择下一个要排列的圆
并计算相应的下界函数
在满足下界约束的结点处
以深度优先的方法递归地对相应子树搜索
对于不满足结点的结点
则剪去相应的子树
三、程序
/*********************************
*程序名
版本:圆排列问题
*开发日期：2005.10.24
*简要说明：将N个大小不等的圆排进一矩形中
且各圆与矩形框底边相切
从所有
排列中找出最小长度的圆排列
***********************************/
#include "math.h" //预编译
#include "iostream.h"
#define N 100 //宏定义
void Swap ( float &a, float &b ) //交换两个值
{
int t ;
t = a ;
a = b ;
b = t ;
}
class Circle
{
friend float CirclePerm ( int , float * ) ; //定义友好类
public: //定义公共子函数
float Center ( int t ) ;
void Compute ( void ) ;
void Backtrack (int t ) ;
// 定义变量
float min , //当前最优值
*x , //当前圆排列圆心横坐标
*r ; //当前圆排列
int n ; //待排列的圆的个数
} ;
/*******************************************
*函数名: Circle::Center
*传入值:当前要排列圆的半径
*输出值:当前所选圆的圆心横坐标
*简要说
明:计算当前所选圆的圆心横坐标
*******************************************/
float Circle::Center ( int t ) //计算当前所选圆的圆心横坐标
{
float temp = 0 ;
for(int j = 1 ; j
{
float valuex = x [j] + 2*sqrt(r[t]*r[j]) ;
cout
cout
if ( valuex > temp ) temp = valuex ;
}
return temp;
}
/*******************************************
*函数名:Circle::Compute
*传入值:当前搜索圆的横坐标和半径
*输出值:当前搜索圆排列的长度
*简要说明:计算当前圆排列的长度
*******************************************/
void Circle::Compute ( void ) //计算当前圆排列的长度
{
float low = 0 , high = 0 ;
for ( int i = 1 ; i
{
if ( x[i] - r[i]
if ( x[i] + r[i] > low ) high = x [i] + r [i] ;
}
if ( high - low
cout
cout
}
/*******************************************
*函数名:Circle::Backtrack
*传入值: 1
*输出值: 当前圆排列的最优值
*简要说明:查找当前最优值
*******************************************/
void Circle::Backtrack ( int t ) //查找当前最优值
{
if ( t > n ) Compute ( ) ;
else
for ( int j = t ; j
{
Swap ( r [ t ] , r [ j ] ) ;
cout
float centerx=Center ( t ) ;
if ( centerx + r [t] + r[1]
{
x [t] = centerx ;
Backtrack ( t + 1 ) ;
}
Swap ( r [ t ] , r [ j ] ) ;
cout
cout
}
}
/*******************************************
*函数名:CirclePerm
*传入值: n
a
*输出值:当前找到的圆的最小长度
*简要说明:计算找到的最小圆排列长度
*******************************************/
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 ;
}
/*******************************************
*函数名:main
*传入值:无
*输出值:圆排列的最小长度
*简要说明:调用各个子程序
输出所有
排列中找出最小长度
*******************************************/
void main ( void )
{
//定义变量
float a[N] , k ;
int m , n ;
cout
cin >> n ;
for ( m = 1 ; m
cin >> a[m];
k = CirclePerm ( n , a) ;
cout
cout
}
四、与圆排列随机化算法的比较
解圆排列问题的一个随机化算法如下.
void Circle_search(int *x)
{
random_perm(x);
found=true;
while(found){
found=false;
for(int i=1;i
for(int j=1;j
if(swap(x[i],x[j]) reduces length){
swap(x[i],x[j]);
found=true;}
}
}
其中,random_perm(x)产生x 的一个随机排列
定义圆排列类
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::Shuffle(void)
{
static RandomNumber rnd;
for(int i=0;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 for(int j=0;j Swap(r[i],r[j]);
Center();
float length=Compute();
if(length 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 X.x=x;
X.CircleSearch();
X.result=X.min;
for(i=1;iX.min) {
X.result=X.min;
}
}
delete []x;
return X.result;
}
五、算法效率比较
设循环次数为k;圆排列随机化算法函数 Center(void) 计算时间需O(n2); 函数Circle::CircleSearch(void)计算时间需O(n4);整个算法时间复杂度O(Kn4)
圆排列问题的回溯算法在最坏情况下时间复杂度为O((n+1)!)