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
相关话题
存在一点的极限值不等于该点的函数值吗？数学和物理中这些符号到底念什么？来源是什么？
为什么古希腊人数学水平远超同时期的其他文明？
你知道哪些让你怀疑智商的数学题？
如何学习几何学（现代微分几何，包括微分流形，黎曼几何等）？
实变函数鲁津定理的疑问？
你最钦佩的数学天才是谁？
被剑桥大学 deferred entry 应该接受吗？
我有一个数学新发现，确定是新发现，确定是正确的，有什么平台可以出售转让变现？
有哪些数学知识概念已经更新或改变，但不为大众所知？
前一个讨论
下一个讨论
相关的话题
除了Weierstrass函数，还有哪些处处连续处处不可导的实变函数的具体例子？如何理解「观点越高，事情越显得简单」这句话？
为什么数列可以用不动点法，到底表示什么意思啊？
如何学好概率论？
是否存在一个复解析函数f(z)，使得对于正整数n，f(n)就是第n个质数？
数学专业出身的口算能力会比其他人强很多吗？
为什么数学中“有且仅有”不可以说成“仅有”？
若1+1=2，则雪是白色的，这是真命题吗？
如果高中生能证明哥德巴赫猜想，会被清华北大数学系保送吗？
如果一个圆的度数是361°世界会有什么影响？
三根表针，两两互为 120° 是几点？
100名囚犯猜红绿灯，最多能保证多少人猜对？
一道初三数学几何题。目前用arctan和tan的无脑计算可以求出来，请问还有其他方法吗？向量？或其它？
π 的数字排列中能否找到 e 的数字排列？
你未必有儿子，从而未必有孙子，未必有一百代世孙。但为何你有父亲，你有爷爷，你有第一百代祖父？
如何看待菲尔兹和阿贝尔奖双料得主 Michael Atiyah 宣称自己证明了黎曼猜想？
如何证明圆上若干点构成的多边形最大面积在正多边形时取到？
什么是「奥利给」不等式？
向量奔驰定理有哪些证明?
有没有证明某函数不存在初等表示的一般思路？
可不可以将所有无理数全都用 有理数·π 来表示？
这道证明题该怎么做？
现在的人工智能是否走上了数学的极端？
为什么有些函数经过二次求导后又回到了原函数？
如何入门 Yamabe 问题？
全国范围内有很多学生在初中或高中初阶就学（完）了高数吗？
复数为什么比较不了大小？
下面这两种情况为什么不一样，x为什么比y少了 ,后面一定要加x,y吗?
有哪些少见却实用的求积分的经验技巧？
你有没有推导过一个复杂的却「贴近生活」的公式？