圆排列问题_小张的java日记的博客-程序员宅基地_圆排列java

问题

给定n个圆的半径序列,将它们放到矩形框中,各圆与矩形底边相切,

求具有最小排列长度的圆排列。

解析

圆排列问题的解空间是一棵排列树。按照回溯法搜索排列树的算法框架,设开始时a=[r1,r2,……rn]是所给的n个元的半径,则相应的排列树由a[1:n]的所有排列构成。

    首先计算圆在当前圆排列中的横坐标,由x^2 = sqrt((r1+r2)^2-(r1-r2)^2)推导出x = 2 * sqrt(r1 * r2)。

然后计算当前圆排列的长度。变量lenmin记录当前最小圆排列长度。数组r存储所有圆的半径。数组x则记录当前圆排列中各圆的圆心横坐标。

最后在回溯法Backtrack中,当i>n时,算法搜索至叶节点,得到新的圆排列方案。此时算法调用Compute计算当前圆排列的长度,适时更新当前最优值。当i<n时,当前扩展节点位于排列树的i-1层。此时算法选择下一个要排列的圆,并计算相应的下界函数。

设计

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]);//回溯,将前面全排列结束后复原,再接着从更前一个元素开始排列
        }
    }
}

分析

时间复杂度:O((n+1)!)

源码

#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;
}

 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_47230213/article/details/106725706

智能推荐

react-router4_虚年的博客-程序员宅基地

React-router41. 基础使用安装yarn add react-router-dom -S基本使用BrowserRouter 包裹整个应用Router路由对应渲染的组件,可嵌套Link跳转专用import { BrowserRouter, Route, Link } from 'react-router-dom'ReactDOM.render( <BrowserRouter>

【Hue】大数据WEB工具Hue_魏晓蕾的博客-程序员宅基地_hue是什么工具

Hue的安装及结合HDFS、Hive、RDBMS、Oozie的配置运行。

vue中封装svg-icon组件并使用_爱上口袋的天空的博客-程序员宅基地

新建的vue项目结构 components文件下新建SvgIcon组件 index.vue文件中代码 &lt;template&gt; &lt;svg :class="svgClass" aria-hidden="true"&gt; &lt;use :xlink:href="iconName"&gt;&lt;/use&gt; &lt;/svg&gt;&...

1分钟教你完美解决地图开发中WebGL着色器32位浮点数精度损失问题_腾讯位置服务的博客-程序员宅基地

以下内容转载自木的树的文章《WebGL着色器32位浮点数精度损失问题》作者:木的树链接:https://www.cnblogs.com/dojo-lzz/p/11250327.html来源:博客园著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。前言Javascript API GL是基于WebGL技术打造的3D版地图API,3D化的视野更为自由,交互更加流畅。提供丰富的功能接口,包括点、线、面绘制,自定义图层、个性化样式及绘图、测距工具等,使开发者更加容易的实现产品构思.

hive 计算两个时间相差的分钟_轻风细雨的博客-程序员宅基地_hive计算两个时间差

select unix_timestamp(checktime,'yyyy-MM-dd HH:mm')- unix_timestamp(applytime,'yyyy-MM-dd HH:mm')/60,checkuser from tableau.home_person_check_time limit 10;

Day28图形界文本框、密码框、文本域以及监听器_颜悦扬的博客-程序员宅基地

学习目标1:文本框和密码框(文本域)2:动作监听3:监听器(Listener)学习内容1:文本框和密码框(文本域)文本框(JTextField)构造方法摘要JTextField()构造一个新的 TextField。JTextField(Document doc, String text, int columns)构造一个新的 JTextField,它使用给定文本存储模型和给定的列数。JTextField(int columns)构造一个具有指定列数的新的空 TextField。J

随便推点

Google Colab Free GPU Tutorial实践教程_owenbb的博客-程序员宅基地

原文薅资本主义羊毛,用Google免费GPU前面的步骤参考第二个链接补充后面的6、改变工作目录通常当你运行这段代码时,你会看到因此,您必须在定义每个文件名之前添加drive/app,为了摆脱这个问题,你可以简单地改变工作目录。 (在本教程中,我更改app)你会看到app文件夹的内容,并不需要一直添加drive/app。其他问题再看原文吧,有点懒得翻译了...

java 6 update 3_Java SE 6 Update 23 正式发布_weixin_39652154的博客-程序员宅基地

Java SE 6 Update 23The full internal version number for this update release is 1.6.0_23-b05 (where "b" means "build"). The external version number is 6u23.HighlightsJava SE 6u23 contains enhancements ...

ae渲染出现错误是什么问题_ae渲染提示渲染错误,渲染出现偏移解决方案_Lucy-Fintech社区的博客-程序员宅基地

AE输出序列时,提示渲染出现偏移,编译影片时出错,渲染错误,然后用ME渲染AE文件的时候也是一直出现错误代码 1609629695,编码失败。出问题的那几段单独输出,最后用pr接在一起输出,是没问题的,但是很繁琐啊。请看下面。看了网上的很多方法,也都是没有解决。首先最常见的第一个,关闭项目设置里的cuda--gpu加速,如下图所示,我试了没有解决。第二个,首选项里的磁盘缓存和加速改大,大于50g,...

PCB设计学习笔记(四)PCB电源系统_Davidysw的博客-程序员宅基地

一、PCB电源系统(1)反激式开关电源模块(&lt;100W),AC(110V-265V)转DC(12V)(2)DCDC降压输出5V,3.3V,电流至少2A(3)DCDC升压输出9V,电流至少500mA(特别18650电池产品)(4)LDO降压输出5V, 4V, 3.3V, 2.5V, 1.8V ,电流至少100mA1、反激式开关电源模块选择时考虑(1)输入输出电压,功率(2)模块尺寸(3)灌胶式还是PCBA的(4)与底板连接方式(5)成本淘宝搜索 12V 2A开关电源模块2、

vue 实现分钟倒计时_a small tree的博客-程序员宅基地

实现首先,是两个div用来显示我们的剩余支付时间然后,是倒计时函数countdown//倒计时countdown () { const end = Date.parse(new Date('2020-05-05 03:59:23')) const now = Date.parse(new Date()) const msec = end - n...

EXCEL中公式如何保护,防止别人误删或者修改_qq_22600163的博客-程序员宅基地

选中整个表格--》右键选择--》【设置单元格格式】选择--》【保护】选项卡--》取消【锁定】前的对号--》选择【确定】回到菜单栏选择--》【查找和选择】--》选择【公式】这时含有公式的单元格被选中鼠标放在点选的单元格上(这点很重要)!!!--》右键选择--》【设置单元格格式】选择--》【保护】选项卡--》选择【锁定】和【隐藏】前的对号--》选择【确定】...