图文并茂详尽剖析圆排列问题

2023-07-18 18:05| 来源: 网络整理| 查看: 265

参考资料 https://blog.csdn.net/liufeng_king/article/details/8890603https://blog.csdn.net/qq_32400847/article/details/51474105https://blog.csdn.net/yzmck/article/details/4302554 原理解释的很赞http://www.doc88.com/p-079198350775.html http://www.docin.com/p-802993408.html 看算法效率部分问题描述

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

问题大方向分析

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

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

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

3. 在递归算法Backtrack中，当i>n时，算法搜索至叶节点，得到新的圆排列方案。此时算法调用Compute计算当前圆排列的长度，适时更新当前最优值。当i

【本文地址】

公司简介

联系我们