很不幸的是……我还真的做过这个项目。

这个问题叫：packing 圆问题

如果你们认真的去查一下文献资料，就会发现，这个问题早就被研究到了研究不下去了，参考前面的酱紫君和七星之城。Packomania这个网站收录的就是最新的研究成果了，包括数值计算时间排行榜。

本来这个问题在国内外上早就被研究透了，但是为什么我还是有机会去参与了这个项目呢？

因为我现在硕士做的就是圆的排列问题…

科普时间开始吧。

酱紫君是从数学的角度去思考这个问题或者证明的，我不知道在不规则圆的时候是不是还能够证明正方形内的最优结果是多少。

这里，我仅仅从应用和数值计算角度去答题。

1，先展示一下我当时的最优成果：

具体是什么意思我等一下再解释。

2.思路过程

要往一个正方形里面尽可能的放置圆，

（1）最简单粗暴的方法就是，人工一个个试。 从一个到100个肯定是很轻松的放就下的，但是你想放101个的时候，就开始想脑壳撞墙了。

脑子不够用了，还是把电脑拿出来吧

那就随机的给101个点的位置，循环个几天几夜看看？！

看见下面一坨了吗，这就是我第一次数值计算想法的结果..

其实放一百个也是这样的..，我们之所以知道放置一百个的方案，是基于已有的经验，但是计算机没有！

所以这个想法是不适合用计算机来算的。

怎么办。。为什么圆都交叉在一起了。

（3） 弹性圆思路

有人就想了，假如圆有弹性，是不是就不会交叉在一起了？

是的…

酱紫君提到的第一个点就是这个意思

把正方形看做一个框, 把圆看成光滑的小球, 然后你取一个球, 使劲压, 看看能不能压进去.
当然现实中是没有绝对光滑小球的, 你实际没法做这个实验.
但数学上可以定义小球与小球, 小球与方框之间的势能, 然后用各种算法降低势能, 看看最小值能不能降到零即可.

作者：酱紫君

在计算机中，就是一步一步的迭代，模拟球体，不停的让交叉的圆弹开，有空隙的小球相吸，叫拟物策略。

但是酱紫君说的一句话是错的，即便是光滑的小球，有时候再怎么压，也会得不到完美的答案，因为存在局部解。

什么是局部解？去电影院看电影买爆米花，店员第一次装满，你接到手里，上下抖，爆米花马上少四分之一，左右再抖，又少了…这就是局部解，明明还可以装得下，却因为神秘原因被卡住而看起来满了。

Packomania这个网站列出了前人目前能达到的各种最优结果，我们可以通过这个来验证自己的算法。

学过数值计算的都知道，只要有了目标函数，可以通过各种各样的算法去求解，但是从我测试的结果来看，还真没有现成可以用的算法，比如模拟退火，牛顿之类的（不然怎么叫世界难题），无法将势能降低到10^-6。

目前大多数人都是通过一定的策略来实现数值求解的。

在这里我只介绍我做和我了解的工作：现实中可以通过抖动来跳出局部解，算法也可以。

具体实现步骤就是： 把空隙最大的地方某个球抽开，塞进两个球，让球根据势能重新排布，这个叫拟人策略。

计算结果就是这个图了：

正方形边长：3236，

球半径：R=[100,53.589,30.094,30.094,21,20];

因为程序比较久远了，现在做的也不是这个方向了，所以程序找不到，只有这个图。

4，应用方面

很多人觉得，研究这东西有什么用。

其实这个问题真的可以验证那句话，鬼知道这个数学问题哪一天会被用到，几百，几千年以后？

据我所知，这个问题可以用于空间站的物体排布,挤出来一点的空间可能就是几百万呢。

至于为什么要追求计算速度呢？

绘制网格，，保形变换

建筑设计

还有我的课题

非均匀布局液压缸推力模型

知乎上其实有过这个问题的回答，可惜是一位匿名的大神

如何生成多个互不重叠的不同半径圆？circle packing到底是怎样？研究过circle packing的大神或者小神们为完全不懂的小朋友做一个扫盲

顺便提一句，有人从机器学习这方面考虑求解吗？，求讨论

不知道酱紫君这样的大神怎么会有那么多时间上知乎答题，而且还那么严谨…

来源：知乎 www.zhihu.com

作者：蒙言

【知乎日报】千万用户的选择，做朋友圈里的新鲜事分享大牛。
点击下载

此问题还有 34 个回答，查看全部。
延伸阅读：
如何用简单易懂的例子解释隐马尔可夫模型？
国际象棋棋盘是8*8的，假如有一种牌占两个格子，两个格子一黑一白，那么把32块这样的牌填满棋盘有多少填法？