精华内容
下载资源
问答
  • 圆排列问题

    2014-01-10 10:33:52
    圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列。例如,当n=3,且所给的3 个圆的半径分别为1,1,2时,这3个圆的最小长度的圆排列如图所示。其最小长度为2 + 4 2 。 编程任务: 对于给定的n个圆,...
  • 圆排列问题,用回溯法,采用Python语言进行编写。给定n个大小不等的圆c1,c2,…,cn,现要将这n个圆排进一个矩形框中,且要求各圆与矩形框的底边相切。圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列。例如...
  • 圆排列问题:给定n个圆的半径序列,将它们放到矩形框中,各圆与矩形底边相切, 求具有最小排列长度的圆排列。
  • 采用java编写的圆排列问题,参考:算法设计与分析
  • 这是解决圆排列问题的详细课件 里边有纤细的算法以及问题的解决方案
  • 圆排列问题(回溯)

    千次阅读 2020-05-13 09:20:26
    圆排列问题(回溯) 1.问题描述 给定n个大小不等的圆C1,C2, ……,Cn,现要将这n个圆排进一个矩形框中,且要求各 圆与矩形框的底边相切。圆排列问题要求从n个圆的所有排列中找出有最小长度的圆 排列。例如,当n=3,且...

    圆排列问题(回溯)

    1.问题描述

    给定n个大小不等的圆C1,C2, ……,Cn,现要将这n个圆排进一个矩形框中,且要求各
    圆与矩形框的底边相切。圆排列问题要求从n个圆的所有排列中找出有最小长度的圆
    排列。例如,当n=3,且所给的3个圆的半径分别为112时,这3个圆的最小长度
    的圆排列如图5-8所示,其最小长度为2+sqrt(2)
    

    在这里插入图片描述
    2.问题分析
    ①解的表示
    解向量(r1,r2,……rn)为圆的一个排列对应的圆半径,(x1,x2,……,xn)是对应的圆心坐标的排列。
    ②解空间
    排列树
    ③约束函数
    当前的圆的序列的可能的最大长度
    要注意的是,相对靠右的圆的右边界并不一定是该部分序列的长度,如下图。

    • 计算第t个圆的圆心坐标的时候,要遍历前面所有的t-1个圆,假设i个圆与t相切,计算坐标,取其中最大的值。
    • 计算序列的长度时,最左端的坐标low是xi-ri最小的,最右端的坐标high是xi+ri最大的,长度 L=high-low。( 其中low可能<0)
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
    void Backtrack(int t){
    	if(t>n) Compute();//计算第t个圆的圆心横坐标
    	else{
    		for(int i=t;i<=n;i++){
    			swap(r[t],r[i]);//r[i]是第i个圆的半径
    			float centerx=Center(t);
    			if(centerx+r[t]+r[1]<min){//下界约束
    				x[t]=centerx;//x[t]是第t个圆的圆心横坐标
    				Backtrack(t+1);
    			}	
    			swap(r[t],r[i]);	
    		}
    	}
    }
    
    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<t; j++) {
    		float valuex = x[j] + 2.0*sqrt(r[t]*r[J]);
    		if (valuex > temp)
    			temp = valuex;
    	}
    	return temp;
    }
    void Circle::Compute(void) {//计算当前圆排列的长度
    	float 1ow =, high = 0;
    	for (int i=1; i <= n; i++) {
    		if (x[i]-r[i] < 1ow)
    			1ow =x[i]-r[1];
    		if (x[i]+r[i] > high)
    			high = x[i]+r[i];
    	}
    	if (high-low < min)
    		min = high-low;
    }
    
    展开全文
  • 圆排列问题 1. 问题 给定n个大小不等的圆c1,c2,…,cn,现要将这n个圆排进一个矩形框中,且要求各圆与矩形框的底边相切。圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列。 例如,当n=3,且所给的3个圆的...

    圆排列问题

    1. 问题

    给定n个大小不等的圆c1,c2,…,cn,现要将这n个圆排进一个矩形框中,且要求各圆与矩形框的底边相切。圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列。
    例如,当n=3,且所给的3个圆的半径分别为1,1,2时,这3个圆的最小长度的圆排列如图所示。其最小长度为2+4√2。
    在这里插入图片描述

    2.解析

    圆排列问题的主要思路是排列问题,通过建立排列树,再进行回溯剪枝,得出最优排列。
    每次修改一个圆的排列位置,若修改后的排列长度变小,则在当前排列的前提下继续排列,否则回溯。
    每次排列后,相切情况下圆的X坐标计算公式:x2 =(r+ri)2 + (r-ri)2,推出x = 2*sqrt(r+ri);r为自身半径,ri为相切圆半径。
    考虑最坏情况,即x最大时,x+r0+r为当前最小圆排列长度。当遍历完所有排列后,留下的就是最优圆排列。
    用回溯法先构造出排列,再根据每种排列计算其对应的长度。如何计算长度?根据排列计算每个圆的圆心坐标,然后再找出整个圆排列最左边的坐标和最右边的坐标,相减即可得出该种情况的长度。由于计算一个圆的圆心时不知道这个圆到底和之前的哪个圆相切,所以需要遍历之前所有的圆,求出符合所有条件的圆心坐标。

    在这里插入图片描述
    在这里插入图片描述

    3. 设计

    
    
    double center(int t)//得到每个圆的圆心坐标
    {
           double temp = 0;
           for(int j = 1; j < t; ++j)//因为目标圆有可能与排在它之前的任一圆相切,故需一一判断
           {
                  //计算圆横坐标
                  double xvalue = x[j] + 2.0 * sqrt(r[t] * r[j]);
                  if(xvalue > temp)
                         temp = xvalue;
           }
           return temp;
    }
    void compute() //根据每种排列计算其对应的长度
    {
           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 < minlen) {
                  minlen = high - low; //记录最小长度
                  for(int i = 1; i < N; ++i)
                         bestr[i] = r[i]; //记录最小半径下的圆排列
           }
    }
    void 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] < minlen)
                         { 
                                x[t] = centerx;
                                backtrack(t + 1);
                         }
                         //回溯,开始下一种排列
                         swap(r[t], r[j]);
                  }
           }
    }

    4. 分析

    最坏的情况,有n个顶点,每个顶点有m种颜色,其有n-1个子节点

    O(n) = n*mn-1/m-1=O(nmn)

    5.源码

    https://github.com/Bacsonlx/Algorithm-analysis

    展开全文
  • 圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列。例如,当n=3,且所给的3个圆的半径分别为1,1,2时,这3个圆的最小长度的圆排列如图所示。其最小长度为2+4sqrt(2) center函数:center计算圆在当前圆...

    给定n个大小不等的圆c1,c2,…,cn,现要将这n个圆排进一个矩形框中,且要求各圆与矩形框的底边相切。圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列。例如,当n=3,且所给的3个圆的半径分别为1,1,2时,这3个圆的最小长度的圆排列如图所示。其最小长度为2+4sqrt(2)

    image-20200325133716157

    image-20200325135817004

    center函数:center计算圆在当前圆排列中的横坐标,由x^2 = sqrt((r1+r2)^2-(r1-r2)^2)推导出x = 2 * sqrt(r1 * r2)。为啥要把计算圆心坐标的公式放在一个for循环里面呢?我们很容易会有一个先入为主的思想,那就是后一个圆必然与排在它前一个位置的圆相切,其实排在任意位置的圆与其前或后的任意一个圆都有可能相切的,画个图就很清晰了。只要大小合适,目标圆就有可能与排列中的任意一个圆相切。

    image-20200325135653425

    compute函数:可以想象其中任意的一个圆无限大或无限小,无限大的话那其余的圆就可以统统忽略了。因为已知所有圆的x[]和r[],很容易求出每个圆的左右坐标,通过比较找出最小的左部坐标和最大的右部坐标,一减就是该圆排列的长度,然后把每次不同的排列长度相比较,找到更小的minlen就更新。

    image-20200325133826887

    #include<iostream>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    const int MAXN = 100;
    int n;//圆的个数
    double minlen=1000000,x[MAXN],r[MAXN];//分别为最小圆排列长度,每个圆心横坐标数组,每个圆半径数组
    double bestv[MAXN];//最小圆排列的半径顺序
    double center(int t){//得到第t个圆的圆心横坐标
        double tmp = 0;
        for (int i = 1; i < t; ++i) {//计算第t个圆与前面(序号为1~t-1)已排列圆相切时的距离,求最大距离
            double xvalue = x[i] + 2.0 * sqrt(r[i]*r[t]);//计算第t个圆与第i个圆相切时的距离
            if (xvalue > tmp) {//最大的距离就是圆心坐标
                tmp = xvalue;
            }
        }
        return tmp;
    }
    void compute(){//计算圆排列长度
        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 < minlen) {
            minlen = high - low;
            for (int i = 1; i <= n; ++i) {
                bestv[i] = r[i];
            }
        }
    }
    void Backtrack(int t){
        if (t > n)
            compute();
        else{
            for (int i = t; i <= n; ++i) {
    //确保全排列:一开始按顺序的时候没交换,第一次排列后,回溯时i与t不同
                swap(r[t], r[i]);
                double centerx = center(t);//计算第t个圆的横坐标
                if (centerx + r[1] + r[t] < minlen) {//剪枝
                    x[t] = centerx;//确定了加入第t个圆的圆排列长度
                    Backtrack(t + 1);//搜索下一个圆
                }
                swap(r[t], r[i]);//回溯,将前面全排列结束后复原,再接着从更前一个元素开始排列
            }
        }
    }
    int main()
    {
        cout << "圆的个数 n:";
        cin >> n;
        cout << "每个圆的半径分别为:";
        for (int i = 1; i <= n; ++i) {
            cin >> r[i];
        }
        Backtrack(1);
        cout << "最小圆排列长度为:" << minlen <<endl;
        cout << "最优圆排列的顺序对应的半径分别为:";
        for (int i = 1; i <= n; ++i) {
            cout << bestv[i] << " ";
        }
        return 0;
    }
    
    
    展开全文
  • 回溯法之圆排列问题

    2020-05-13 13:10:13
    圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列。例如,当n=3时,且所给的3个圆的半径分别为1、1、2时,这3个圆的最小长度的圆排列如图所示,其最小长度为2+4*√2. 算法设计 这个问题的解空间应该是一棵...

    问题描述

    给定n个大小不等的圆c1,c2,…,cn,先要将这n个圆排进一个矩形框中,且要求各圆与矩形框的底边相切。圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列。例如,当n=3时,且所给的3个圆的半径分别为1、1、2时,这3个圆的最小长度的圆排列如图所示,其最小长度为2+4*√2.
    在这里插入图片描述

    算法设计

    这个问题的解空间应该是一棵排列树。因为圆就是按照一定的顺序排在矩形框中的,这里面我们将圆的半径进行排序,从而代表圆排序。其中a=[r1,r2,…,rn]就是我们的序列。
    CirclePerm(n,a)返回找到的最小圆排列长度。初始时,数组a是输入的n个圆的半径,计算结束后返回相应于最优解的圆排列。Center计算当前所选择的圆在当前圆排列中圆心的横坐标,Compute计算当前圆排列的长度,变量min记录当前最小圆排列的长度,数组r表示当前圆排列,数组x则记录当前圆排列中各圆的圆心横坐标。算法中约定在当前圆排列中排在第一个的圆的圆心横坐标为0.
    在递归算法中,当i>n时,算法搜索至叶结点,得到新的圆排列方案。此时算法调用Compute计算当前圆排列的长度,适时更新当前最优值。
    当i<n时,当前扩展结点位于排列树的第i-1层。此时算法选择下一个要排列的圆,并计算相应的下界函数。在满足下界约束的结点处,以深度优先的方式递归地对相应子树搜索(此结点为扩展结点)。对于不满足下界约束的结点,剪去相应的子树。
    至于下界约束如何计算呢?我们用一个图来说明:
    在这里插入图片描述

    代码

    #include <math.h>
    #include <iostream>
    using namespace std;
    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 valuex,temp = 0;
                //之所以从1-t判断是因为防止第t个圆和第t-1个圆不相切
                for(int j = 1;j < t;j++)
                {
                    valuex = x[j] + 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[t] < 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)
                {
                    //到达叶子节点,我们计算high与low的差距
                    Compute();
                }
                else
                {
                    //排列树解空间
                    for(int j = 1;j <= t;j++)
                    {
                        //圆的排列其实就是就是半径的排列,因为相同半径的圆是相同的
                        //交换半径顺序,可以进一步优化,如果半径相等不交换
                        //镜像序列只算一次,例如1,2,3和3,2,1
                        swap(r[t],r[j]);
                        if(Center(t)+r[1]+r[t] < min)//下界约束,我们取第一个圆的圆心为原点,所以计算距离的时候要加上r[1]和r[t]
                        {
                            x[t] = Center(t);
                            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;
            }
    };

    这里我想说明的一点是,我们之所以一直从头寻找一个圆来更新当前圆的圆心位置,是因为相邻的圆与当前圆t不一定相切,我们应该找到一个相切的。选出最大值就对应了当前圆中心坐标

    总结

    Backtrack需要O(n!)的计算时间(排列树),计算当前圆排列长度需要从头遍历到尾,需要O(n)计算时间,从而整个算法的时间复杂度为O((n+1)!)
    优化:1.排序存在镜像,我们算一次即可
    2.不交换相同半径圆的位置

    展开全文
  • 利用分支限界法解决圆排列问题,求得圆的最小圆排列(每一步均含详细解释),编程语言:C++
  • 圆排列问题 问题描述: 给定n个圆的半径序列,将它们放到矩形框中,各圆与矩形底边相切,求具有最小排列长度的圆排列。 算法 假设三个圆的半径分别为1,1,2。那么这种情况的圆排列长度为2+4sqrt(2)。计算r1=1,r2=2...
  • 圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列。例如,当n=3,且所给的3 个圆的半径分别为1,1,2时,这3个圆的最小长度为2 + 4sqrt(2) 。 算法设计:对于给定的n个圆,设计一个优先队列式分支限界法,...
  • 算法设计与分析: 6-8 圆排列问题

    千次阅读 2018-07-23 23:13:06
    6-8 圆排列问题 问题描述 给定 n 个大小不等的圆 c1,c2,...,cnc1,c2,...,cnc_1 , c_2 , ... , c_n ,现要将这 n 个圆排进一个矩形框中,且要求各圆与矩形框的底边相切。圆排列问题要求从 n 个圆的所有排列中找出...
  • 圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列。例如,当n=3,且所给的3个圆的半径分别为1,1,2时,这3个圆的最小长度的圆排列如图所示。其最小长度为 。 算法设计 设计一个随机化算法,对于给定的n个...
  • 圆排列问题:给定n个圆的半径序列,将它们放到矩形框中,各圆与矩形底边相切,求具有最小排列长度的圆排列。首先,对于n个圆的半径序列,我们将其全排列,并以树的形式展现。 这个树是多叉树,它满足:根节点的子结...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 73,209
精华内容 29,283
关键字:

圆排列问题