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
相关话题
直线可不可以看做是半径无限大的圆？如何分析 2021 亚太杯数学建模ABC题？思路代码是什么？
如何评价一些数学大佬在推导过程中的「我们不难发现…」、「显然有…」、「易得…」等语言?
为什么特征值之和会等于矩阵的迹？
矩阵论什么好的书籍推荐？
每个长度无限的字符串里面一定有某个连续重复3次的字符串吗？
有哪些分析的恒等式有很深刻的数学背景？
这个问题怎么做?最后怎么解出多项式？
如何理解主成分分析中的协方差矩阵的特征值的几何含义？
洗澡的时候突然论证出了1等于0，2等于0，所有数等于0，这个论证哪里错了呢？
前一个讨论
下一个讨论
相关的话题
为什么黎曼ζ函数能够如此表示？（第二个等号）?有哪些数学上的定理让你感觉「这不显然吗，这还用证明」？
有一个数学很好的男朋友是一种怎样的体验?
1^k+2^k+3^k+…+n^k 的公式是什么（n，k 均为自然数）？
北大数学系田刚的学问到底怎么样？
怎么证明关于素数的米尔斯常数A是存在的?
(不用答了）这个证明中的这两个红圈中的结论是怎么得出来的？
如何证明对任意给定的正数e，存在M上的矩阵范数||A||，满足不等式||A||<=谱半径+e?
你有没有推导过一个复杂的却「贴近生活」的公式？
虚数 i 是真实存在的吗？还是被人们创造出的数学工具？
行列式等于 0，就一定有两行或两列相等吗？
做计算PhD的研究是否如丁仲礼所说的那么不靠谱？
阶乘的概念能否推广到全体实数，甚至是全体复数？
如何找到一个10项的非负整数数列，使该数列的任意不超过3项的和不重复，并使数列的最大项最小，并证明?
「泛函」究竟是什么意思？
高斯作出正 17 边形的依据是什么？
有一函数F(x)，其导数为F`(x)，现在它们共同出现在同一等式里，是否能计算出F(x)的表达式？
4≤5，这个不等式是否正确？
假如我每次连续攻击目标所造伤害是上次次攻击的105%，我连续出拳一千次，能不能打穿坦克护甲？
如何求出图中数列的通项公式？
如何求解 e^x=x^e 这个方程？
制药工程女生就业真的不好吗，不喜欢化学而喜欢数学？
如何将一张A4纸快速折出完美的五等份？
弧的长度与弦的长度之比的极限为1，能严格证明吗？
假设，宇宙万物起源于“道”（现有理论中称之为奇点）那么这个“道”是否产生一最基本的规律或为一规律？
柯西审敛原理是证得收敛还是一致收敛?
只有三维向量有向量积吗？
一个空间中勾股定理不存在，而变成了 c^4=a^4+b^4，甚至有更高的指数，那么这是一种什么空间？
如何这道计算绝对值不等式的题目？
以数学史的观点来看，集合论是如何成为数学基础的？