10 × 10 的正方形最多可放入多少个直径为 1 的圆？ 第1页
1
GalAster 网友的相关建议:
可以放106个, 你可能会觉得, 一个框只能放一个怎么突破100个呢?
试着突破定势思维.
想想一个硬币最多可以和几个硬币相邻?
六个, 如果一个格子占一个才几个?
四个, 所以有大量的空间被浪费了.
这样, 就一共有105个了.
然后聪明的你发现还有点空隙, 能不能利用起来呢?
当然是可以的
这样安排就又多了个10排的, 神奇的又插了一个进去.
那么, 还能不能再用什么神奇的方法再搞一个进去呢?
不可能了...
但是如何在数学上证明不能放下107个圆呢? 有两种思路
- 1.把正方形看做一个框, 把圆看成光滑的小球, 然后你取一个球, 使劲压, 看看能不能压进去.
当然现实中是没有绝对光滑小球的, 你实际没法做这个实验.
但数学上可以定义小球与小球, 小球与方框之间的势能, 然后用各种算法降低势能, 看看最小值能不能降到零即可.
- 2.取n个小球, 然后放进一个方框, 方框使劲收缩, 收缩到无法再收缩为止.
最终结果就是最优平面圆堆积.这种方法比上一种要复杂一些
但是数学家一般喜欢研究第二个, 因为至少对于正方形等圆嵌入来说, 解决了第二个也就解决了第一个.对于矩形才会用第一种方法.
但这个思路说得轻巧, 可数学上怎么定义使劲收缩呢?
Talk is cheap, Show me the code!
Formulation Space Search for two-dimensional Packing Problems
这本书整理了这方面的研究成果, 第72页讨论了圆塞入正方形, 后面还有更难的不相等图形塞进不规则边框
书中没给结果, 算法都是伪代码, 不用完全看懂公式也能复现.
运算时间要有心理准备, 一次差不多要跑半个小时.
计算结果表明106个直径为1的圆能放进边长9.996960840529825的正方形
但是如果要放置107个直径为1的圆就要边长10.09975184413619的正方形
所以确实10*10的正方形只能塞下106个直径为1的圆.
注意有轻微的形变, 比如右下那个没对齐, 上边框第五个圆脱离了边框, 但是只有0.4%, 整体上和原来差不多.
附全部的绘图代码:
t1 = Flatten [ Table [{ i , j },{ i , 1 , 19 , 2 },{ j , 1 , 19 , 2 }], 1 ]; Append [ Circle /@ t1 , { EdgeForm [ Dashed ], RGBColor [ 0 , 0 , 0 , 0 ], Rectangle [{ 0 , 0 },{ 20 , 20 }]} ] // Graphics f10 = Circle /@ Table [{ i , # },{ i , 1 , 19 , 2 }] & ; f9 = Circle /@ Table [{ i , # },{ i , 2 , 18 , 2 }] & ; Join [ Table [{ f10 [ 1 + ( i -1 ) Sqrt [ 3 ]]},{ i , 1 , 11 , 2 }], Table [{ f9 [ 1 + i Sqrt [ 3 ]]},{ i , 1 , 10 , 2 }], { EdgeForm [ Dashed ], RGBColor [ 0 , 0 , 0 , 0 ], Rectangle [{ 0 , 0 },{ 20 , 20 }]} ] // Graphics Join [ Table [{ f10 [ 1 + ( i -1 ) Sqrt [ 3 ]]},{ i , 1 , 5 , 2 }], Table [{ f9 [ 1 + i Sqrt [ 3 ]]},{ i , 1 , 4 , 2 }], Table [{ f10 [ 4 Sqrt [ 3 ] + 3 + ( i -1 ) Sqrt [ 3 ]]},{ i , 1 , 5 , 2 }], Table [{ f9 [ 4 Sqrt [ 3 ] + 3 + i Sqrt [ 3 ]]},{ i , 1 , 4 , 2 }], { f10 [ 19 ]}, { EdgeForm [ Dashed ], RGBColor [ 0 , 0 , 0 , 0 ], Rectangle [{ 0 , 0 },{ 20 , 20 }]} ] // Graphics pts = { { -8.99696 , -8.99696 },{ -8.99696 , -5.39534 },{ -8.99696 , -1.93124 },{ -8.99696 , 0.0687576 },{ -8.99696 , 3.53286 }, { -8.99696 , 6.99696 },{ -8.99696 , 8.99696 },{ -8.03644 , -7.23071 },{ -7.99696 , -3.66329 },{ -7.99696 , 1.80081 }, { -7.99696 , 5.26491 },{ -7. , -5.50556 },{ -6.99713 , -8.97132 },{ -6.99696 , -1.93124 },{ -6.99696 , 0.0687576 }, { -6.99696 , 3.53286 },{ -6.99696 , 6.99696 },{ -6.99696 , 8.99696 },{ -6. , -7.23761 },{ -6. , -3.77351 },{ -5.99696 , 1.80081 }, { -5.99696 , 5.26491 },{ -5. , -5.50556 },{ -5. , -2.04146 },{ -5. , -0.0414576 },{ -4.99729 , -8.99696 },{ -4.99696 , 3.53286 }, { -4.99696 , 6.99696 },{ -4.99696 , 8.99696 },{ -4. , -7.23961 },{ -4. , -3.77351 },{ -4. , 1.69059 },{ -3.99696 , 5.26491 }, { -3. , -5.50556 },{ -3. , -2.04146 },{ -3. , -0.0414576 },{ -3. , 3.42264 },{ -2.99746 , -8.97113 },{ -2.99696 , 6.99696 }, { -2.99696 , 8.99696 },{ -2. , -7.23761 },{ -2. , -3.77351 },{ -2. , 1.69059 },{ -2. , 5.15469 },{ -1. , -5.50556 },{ -1. , -2.04146 }, { -1. , -0.0414576 },{ -1. , 3.42264 },{ -1. , 6.88675 },{ -1. , 8.88675 },{ -0.997623 , -8.99696 },{ 0. , -7.23961 },{ 0. , -3.77351 }, { 0. , 1.69059 },{ 0. , 5.15469 },{ 0.996961 , 6.99696 },{ 0.996961 , 8.99696 },{ 1. , -5.50556 },{ 1. , -2.04146 },{ 1. , -0.0414576 }, { 1. , 3.42264 },{ 1.00221 , -8.97093 },{ 1.99696 , 5.26491 },{ 2. , -7.23761 },{ 2. , -3.77351 },{ 2. , 1.69059 },{ 2.99696 , 3.53286 }, { 2.99696 , 6.99696 },{ 2.99696 , 8.99696 },{ 3. , -5.50556 },{ 3. , -2.04146 },{ 3. , -0.0414576 },{ 3.00204 , -8.99696 }, { 3.99696 , 1.80081 },{ 3.99696 , 5.26491 },{ 4. , -7.23961 },{ 4. , -3.77351 },{ 4.99696 , -1.93124 },{ 4.99696 , 0.0687576 }, { 4.99696 , 3.53286 },{ 4.99696 , 6.99696 },{ 4.99696 , 8.99696 },{ 5. , -5.50556 },{ 5.00187 , -8.97074 },{ 5.99696 , -3.66329 }, { 5.99696 , 1.80081 },{ 5.99696 , 5.26491 },{ 6. , -7.23761 },{ 6.99696 , -5.39534 },{ 6.99696 , -1.93124 },{ 6.99696 , 0.0687576 }, { 6.99696 , 3.53286 },{ 6.99696 , 6.99696 },{ 6.99696 , 8.99696 },{ 7.00169 , -8.99696 },{ 7.99696 , -7.12739 },{ 7.99696 , -3.66329 }, { 7.99696 , 1.80081 },{ 7.99696 , 5.26491 },{ 8.99696 , -8.85945 },{ 8.99696 , -5.39534 },{ 8.99696 , -1.93124 },{ 8.99696 , 0.0687576 }, { 8.99696 , 3.53286 },{ 8.99696 , 6.99696 },{ 8.99696 , 8.99696 } }; Echo [ m = Max @ First @ Transpose @ pts + 1 , "Min: " ]; Append [ Circle /@ pts , { EdgeForm [ Dashed ], RGBColor [ 0 , 0 , 0 , 0 ], Rectangle [{ - m , - m }, { m , m }]} ] // Graphics vjay 网友的相关建议:
日常工作中我是这么干的，非常适合数学白痴。点链接直通“公式”页面，边长、直径、图形可以任意修改……
movingdune 网友的相关建议:
很不幸的是……我还真的做过这个项目。
这个问题叫：packing 圆问题
如果你们认真的去查一下文献资料，就会发现，这个问题早就被研究到了研究不下去了，参考前面的酱紫君和七星之城。Packomania这个网站收录的就是最新的研究成果了，包括数值计算时间排行榜。
本来这个问题在国内外上早就被研究透了，但是为什么我还是有机会去参与了这个项目呢？
因为我现在硕士做的就是圆的排列问题...
科普时间开始吧。
酱紫君是从数学的角度去思考这个问题或者证明的，我不知道在不规则圆的时候是不是还能够证明正方形内的最优结果是多少。
这里，我仅仅从应用和数值计算角度去答题。
1，先展示一下我当时的最优成果：
具体是什么意思我等一下再解释。
2.思路过程
要往一个正方形里面尽可能的放置圆，
（1）最简单粗暴的方法就是，人工一个个试。 从一个到100个肯定是很轻松的放就下的，但是你想放101个的时候，就开始想脑壳撞墙了。
脑子不够用了，还是把电脑拿出来吧
那就随机的给101个点的位置，循环个几天几夜看看？！
看见下面一坨了吗，这就是我第一次数值计算想法的结果..
其实放一百个也是这样的..，我们之所以知道放置一百个的方案，是基于已有的经验，但是计算机没有！
所以这个想法是不适合用计算机来算的。
怎么办。。为什么圆都交叉在一起了。
（3） 弹性圆思路
有人就想了，假如圆有弹性，是不是就不会交叉在一起了？
是的...
酱紫君提到的第一个点就是这个意思
把正方形看做一个框, 把圆看成光滑的小球, 然后你取一个球, 使劲压, 看看能不能压进去.
当然现实中是没有绝对光滑小球的, 你实际没法做这个实验.
但数学上可以定义小球与小球, 小球与方框之间的势能, 然后用各种算法降低势能, 看看最小值能不能降到零即可.
作者：酱紫君
在计算机中，就是一步一步的迭代，模拟球体，不停的让交叉的圆弹开，有空隙的小球相吸，叫拟物策略。
但是酱紫君说的一句话是错的，即便是光滑的小球，有时候再怎么压，也会得不到完美的答案，因为存在局部解。
什么是局部解？去电影院看电影买爆米花，店员第一次装满，你接到手里，上下抖，爆米花马上少四分之一，左右再抖，又少了...这就是局部解，明明还可以装得下，却因为神秘原因被卡住而看起来满了。
Packomania这个网站列出了前人目前能达到的各种最优结果，我们可以通过这个来验证自己的算法。
学过数值计算的都知道，只要有了目标函数，可以通过各种各样的算法去求解，但是从我测试的结果来看，还真没有现成可以用的算法，比如模拟退火，牛顿之类的（不然怎么叫世界难题），无法将势能降低到10^-6。
目前大多数人都是通过一定的策略来实现数值求解的。
在这里我只介绍我做和我了解的工作：现实中可以通过抖动来跳出局部解，算法也可以。
具体实现步骤就是： 把空隙最大的地方某个球抽开，塞进两个球，让球根据势能重新排布，这个叫拟人策略。
计算结果就是这个图了：
正方形边长：3236，
球半径：R=[100,53.589,30.094,30.094,21,20];
因为程序比较久远了，现在做的也不是这个方向了，所以程序找不到，只有这个图。
4，应用方面
很多人觉得，研究这东西有什么用。
其实这个问题真的可以验证那句话，鬼知道这个数学问题哪一天会被用到，几百，几千年以后？
据我所知，这个问题可以用于空间站的物体排布,挤出来一点的空间可能就是几百万呢。
至于为什么要追求计算速度呢？
绘制网格，，保形变换
建筑设计
还有我的课题
非均匀布局液压缸推力模型
知乎上其实有过这个问题的回答，可惜是一位匿名的大神
顺便提一句，有人从机器学习这方面考虑求解吗？，求讨论
不知道酱紫君这样的大神怎么会有那么多时间上知乎答题，而且还那么严谨...
1
相关话题
当数学家刚想出微积分用细矩形面积的和逼近时，矩形的高选取多少呢？为何不怕无限多个小误差之和为大误差？如何评价穿越古代以数分为实数、虚数为开头写一本数学书？
除了π，e，0.618，还有没有其他一些有特殊意义的数？
学数学的人性格的共性特点有哪些？
「如果昨天是明天的话就好了，这样今天就周五了」这句话为何会产生两种解释？
我喜欢的女生的QQ好友验证问题是8730579，是什么意思？
高中数学解析几何圆锥曲线大题真的是硬解就能解出吗？
请问此拉马努金连分数公式如何证明？
0.8＞ln2 怎么证明？
有哪些有趣、脑洞大开的学术论文？
前一个讨论
下一个讨论
相关的话题
请问B项和D项有什么区别吗？莱布尼兹发明的微积分符号比牛顿的好在啥地方？
哪些看似毫不相干的事物具有相同的数学原理？
有哪些千年以上时间才解决的数学问题?
为什么各个位数之和是3的倍数的数能被三整除？其他的数为什么不行？
如何看待郑爽小号疑似曝光：按前男友顺序编号注册微博小号，每个小号数字还是以 4 递增的等差数列？
如何证明有理数加法群不是有限生成群？
数学论文的作者会意识到自己发表的结果实际上已经有人做出来过吗？
没有阿拉伯数字、拉丁字母和希腊字母，古代中国的数学是什么样的情况？
如何直观地说明为什么前 n 个自然数的立方和等于和的平方？
如何用数学的方法说明极限理论的表现力强于初等数学？
为什么数学每次考完自己在想就能把不会的想出来?
高代，中间这一步是怎么来的呀?
83，63，90，70，100，是什么规律？
有哪些适合失业人士思考的数学问题？
收敛的序列是否存在单调的子序列（不要求严格单调）？
5是一个已知数，设5＝x或者x＝5，这两个表达的意思在数学和语文表达正确吗？
数学真的是一门有意义的学科吗?
下一次数学突破会在哪里？
学习什么知识可以更好地掌握线性代数、概率论与数理统计以及微积分这种较基础的数学工具？
如何证明此不等式呢？
支持热爱数学的女生走纯数学道路吗？
一立方米的物体（类似于活性炭）把它展开后它的表面积最大能有多少？能达到无限吗？
微分流形与黎曼几何有什么关系？
冰雹猜想疑惑，是不是不能被3整除的数必能回到1？
最后放弃研究数学的人，是对数学失去兴趣了，还是找不到教职被迫放弃了？
行列式等于 0，就一定有两行或两列相等吗？
国内是否有教授现代数学(非应付考试)的机构？
如何证明在a，b为正实数，a+b=a＾3+b＾3时，a+b∈（1，2（√3）/3]？
你所在的学科或专业领域中，有哪些方面被数学知识深刻地改变了？