我已经有这个问题好几年了。不久前,这是我镇上的一场信息学竞赛。我没能解决,我的老师也没能解决。我还没有遇到能够解决这个问题的人。我认识的人都不知道给出答案的正确方法,所以我决定将其发布在这里:
泽问题
给定一个 X × Y 的矩形,找到具有固定给定半径 R 的最小圆数 N,以完全覆盖矩形的每个部分。
我想过解决的办法,但没有什么确定的。如果每个圆定义一个内部矩形,那么R^2 = Wi^2 + Hi^2
, where Wi
and Hi
是每个圆所覆盖的实际区域的宽度和高度i
。起初我想我应该做Wi
等于Wj
对于任何i
=j
,同样对于H
。这样,我可以通过使宽度/高度比等于主矩形(Wi/Hi
= X/Y
)。那样,N=X/Wi
。但这个解决方案肯定是错误的,以防万一X
大大超过Y
或相反亦然。
第二个想法是Wi
=Hi
对于任何给定的i
。这样,正方形就能最有效地填充空间。但是,如果仍然存在非常窄的条带,则使用矩形来填充它会更理想,或者更好 - 也对之前的最后一行使用矩形。
然后我意识到这些想法都不是最佳的,因为我总能找到更好的方法来做到这一点。它总是接近最终,但不是最终。
Edit
在某些情况下(大矩形),连接六边形似乎是比连接正方形更好的解决方案。
Further Edit
Here's a comparison of 2 methods: clover vs hexagonal. Hexagonal is, obviously, better, for large surfaces. I do think however that when the rectangle is small enough, rectangular method may be more efficient. It's a hunch. Now, in the picture you see 14 circles on the left, and 13 circles on the right. Though the surface differs much greater (double) than one circle. It's because on the left they overlap less, thus waste less surface.
问题仍然存在:
- 正六边形图案本身是最佳的吗?或者应该对主矩形的某些部分进行某些调整。
- 有理由不使用规则形状作为“最终解决方案”吗?
- 这个问题还有答案吗? :)
对于与 R 相比较大的 X 和 Y,六边形(蜂窝)图案接近最佳。 X 方向圆心之间的距离为sqrt(3)*R
。 Y 方向上的行间距为3*R/2
,所以你大约需要X*Y/R^2 * 2*/(3*sqrt(3))
界。
如果使用方形图案,水平距离会更大(2*R
),但垂直距离要小得多(R
),所以你需要X*Y/R^2 * 1/2
界。自从2/(3*sqrt(3) < 1/2
,六边形图案是更好的选择。
请注意,这只是一个近似值。通常可以稍微调整一下常规图案,以使某些东西适合标准图案不适合的地方。如果 X 和 Y 与 R 相比较小,则尤其如此。
就您的具体问题而言:
六边形图案是整个平面的最佳覆盖。当 X 和 Y 有限时,我认为通常可以获得更好的结果。一个简单的例子是当高度小于半径时。在这种情况下,您可以将一行中的圆进一步移开,直到每对圆的交点之间的距离等于 Y。
具有规则模式会对解决方案施加额外的限制,因此在这些限制下的最佳解决方案在删除这些限制后可能不是最佳的。一般来说,稍微不规则的图案可能会更好(请参阅 mbeckish 链接到的页面)。
同一页面上的示例都是具体的解决方案。具有更多圆圈的解决方案有点类似于六边形图案。尽管如此,似乎还没有一个封闭式的解决方案。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)