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
相关话题
我感觉我对数学的求知欲在下降，怎么办？这道定积分题目如何解？
为什么偏序集里的哈斯图不能有三角形呢？求证明过程？
高代，中间这一步是怎么来的呀?
请问2^2^2^2+3^3^3^3是否为素数呢？
数学史上有哪些看似成立的算式形式猜想，最终被某个大数证明不成立？
请问下面这个命题成立吗？
你做过的最难的题是什么？
傅里叶变换、拉普拉斯变换、Z 变换的联系是什么？为什么要进行这些变换？
有什么游戏精巧地利用了数学？
前一个讨论
下一个讨论
相关的话题
数学不好是否低人一等或者不配上大学？如何计算 sqrt(tan x) 在 0 到 π/2 的定积分？
有没有这样一条公理，如果一旦不成立，所有学术体系（如物理学、化学、生物学）都会崩溃？
1000桶水，其中一桶有毒，猪喝毒水后会在15分钟内死去，想用一个小时找到这桶毒水，至少需要几头猪？
如何理解主成分分析中的协方差矩阵的特征值的几何含义？
请问贝祖定理（裴蜀定理）除了用辗转相除法还能怎么证?
如何证明一下等式?
麻将中一个搭子的听牌张数与构成搭子本身的张数有数学联系吗？
2022 这个数字在数学意义上有什么特别的，为什么？
凉宫动画里的这些公式都是什么？
e 是怎么算的？
多元复合函数求导与一元复合函数求导的联系与区别是什么？
数学的符号系统有没有缺陷？
请问姜文华的学术水平在统计圈属于什么位置？
「克莱因瓶」是什么，如何借助「克莱因瓶」来理解四维空间？
√3 大约是多少？该如何计算？
有哪些具有特殊性质的数字？
为什么不存在最小的正有理数？
最后放弃研究数学的人，是对数学失去兴趣了，还是找不到教职被迫放弃了？
数学史上有哪些比较著名的猜想因为有反例的存在而没有成为定理？
无法理解高等数学怎么办？
有哪些自己发现并证明的并自以为得意的初等数学定理？
学数学是什么感觉？
有什么参考书对大一学习高数有帮助的吗 求推荐 谢谢？
如何评价2021年第三届阿里巴巴全球数学竞赛？
有什么有趣的数学题？
怎么形象清晰地解释「周期 3 意味着混沌」?
为什么度量空间中聚点等同于极限点？
x+y+z=1 与x2+y2+z2=4 的交线 圆的半径怎么求？
经济学到底需不需要引入数学？