问题
给定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;
}
文章浏览阅读842次。在Android app开发过程中,用fastjson获取后台数据,后台返回的数据:[{"doseFrequencyList":[{"FrequencyCode":"ed","name":"每天","ordinal":"1"},{"FrequencyCode":"iod","name":"隔天","ordinal":"2"},{"FrequencyCode":"iow","name":"隔周","_android网络请求大小写问题
文章浏览阅读235次。原文链接:Bougie的博客 制作目录索引这种东西当然是放在前端方便。选择放在后端一是为了了解Node后端生态,掌握更多后端技术;二是因为公司实行前后端分离的方式开发,睾贵的JAVA后端经常啥也不做处理就返回一个row数据(甚至有时时间戳都不处理),对此有些无语。最终目标 1. 点击索引单项跳转到相应标题 2. 大号标题包含小号标题,小号标题向右缩进 3. 滚动页面时自..._toc-wrapper
文章浏览阅读151次。介绍:In the first RESTEasy tutorial we have learnt the basics about REST Web services and we have tested a simple RESTful Web service. In this tutorial we willshow how to inject web application eleme..._@headerparam@queryparam
文章浏览阅读594次。小米移动3G版本,救砖手册,移动叔叔_移动叔叔小米卡米
文章浏览阅读2.6k次。目前流行几种备份方式:逻辑备份、物理备份、双机热备份、备份脚本的编写等,本文分别从这些方面总结了MYSQL自动备份策略的经验和技巧,一起来看看。_数据库没有链接工具怎么备份
文章浏览阅读54次。1.背景介绍近年来人工智能领域火爆,新时代需求驱动着AI技术的发展。在NLP、CV等领域,基于大量数据的深度学习模型近几年已经成为各大领域最热门的研究方向。语言模型作为一种基础性产物,用于生成高质量的自然语言,如自动翻译、文本摘要、情感分析等,已经成为各大公司的重点关注之一。语言模型往往需要部署到业务系统中,对系统整体性能进行持续的关注与改进,以保证_开发与优化大语言模型算法,提升大语言模型效果2.理解业务需求,设计并实施大语言模
文章浏览阅读9k次,点赞3次,收藏6次。查看防火墙状态$ service iptables status关闭防火墙$ service iptables stop查看防火墙状态$ service iptables status停止hbase$ stop-hbase.sh启动hbase$ start-hbase.sh_can't get connection to zookeeper: keepererrorcode = connectionloss for /hba
文章浏览阅读324次。进一步切入全屋智能、大屏、车机等全场景。2020年,华为消费者业务的产品线纵深正进一步拓展。12月21日,华为面向家庭、出行场景正式发布了三大系列产品。其一是华为智能家居战略及全屋智能解决方案,顾名思义,是提升家居生活智能化的软硬件体系;其二是华为智慧屏S系列,搭载了鸿蒙OS最新版本,该系列是华为智慧屏家族的新成员,产品定位中低端市场,拥有55、65、75寸三种屏幕尺寸共6款机型;其三是车载智慧屏...
文章浏览阅读322次。CMenu::EnableMenuItem启用、 禁用,或变暗的菜单项。UINT EnableMenuItem(UINT nIDEnableItem, UINT nEnable);参数nIDEnableItem根据所指定的菜单项,若要启用,nEnable。 弹出菜单项,以及标准菜单项,可以指定此参数。nEnable指定要执行的操作。 它可以是组合的M..._cmenu 菜单项置灰
文章浏览阅读167次。php连接memcached缓存服务器的客户端有两个,一个是memcache是比较底层的开发库,memcached是比较新的开发库,php安装这两个扩展中的任意一个后就可以在编写php代码时使用的memcached缓存数据,达到缓存php执行的结果1、安装memcachetar -zxvfmemcache-2.2.7.tgzcdmemcache-2.2.7/usr/loc..._群晖添加phpredis扩展
文章浏览阅读510次。Lambda是Java 8引入的新特性,在Java语法层面,Lambda表达式允许函数作为一个方法的参数(函数作为参数传递到方法中);在具体实现上主要依靠了JVM底层提供的 Lambda相关API (现有语法的封装 )注:部分代码示例和说明是转载使用Lambda表达式语法:(参数列表)箭头操作符 Lambda体( (int) arg1, (String) arg2) -> {..}参数类型可..._lambda语法糖
文章浏览阅读984次。#include /* DTSmyled{compatible = "led";/* led2-5: gpx2_7 gpx1_0 gpf3_4 gpf3_5 *//*gpios = , , , ;};*/MODULE_LICENSE("Dual BSD/GPL");MODULE_DESCRIPTION("a simple driver example!");//create a platform ..._linux中获取设备树gpio口