算法：圆盘盖米问题（圆的密铺？）

[caneman]

原问题为：

在一棋盘撒米，米粒落点不一，有口径大小不一的若干圆盘，问如何尽可能少的尝试，用圆盘覆盖尽可能多的米粒？（即：尽可能少的米粒裸露在外。）

条件：

1.黑盒系统，米粒位置信息均不可知。

2.仅当圆盘放下方可知其覆盖米粒数量，，每个圆盘覆盖的米粒不得超过 50 粒。

3.圆盘之间可以互相堆叠，已被下层圆盘覆盖的米粒不计入上层圆盘覆盖米粒的数量。

下面是我想到的一种解决方案，感觉还有很多地方可以优化，请问大伙有没有什么好的办法或者对这个算法的改进？

[caneman]

大伙给点思路啊

[fzy0728]

图裂了

[widewing]

那不是只要重叠面积尽量小不就好了

[caneman]

@fzy0728

我这里看没有啊

链接：




[ipwx]

@caneman imgur 是被墙的域名。。。

[CEBBCAT]

楼主你没说一共多少粒米。这怎么解？要是他把所有米都放到一个点上那一准爆掉
@fzy0728 科学上网

[weizhen199]

= -端起来抖一抖

[caneman]

@widewi 这个你试试
http://www.caneman.cn/wp-content/uploads/2019/05/dock.jpg

[caneman]

@CEBBCAT 随机掉落，单个点重叠数量<50

[caneman]

@CEBBCAT 用足够大的圆盘盖一下就知道了，所以可以理解为知道总数。

[fzy0728]

@CEBBCAT @caneman https://www.v2ex.com/t/559330 有梯子也不好用

[CEBBCAT]

@fzy0728 #11 哦嚯，这 Imgur 也是有意思 http://discuss.flarum.org.cn/d/359 我该嫖哪个图床啊，哭

[necomancer]

我觉得就是怎么用圆有效填充方形面积的问题。
1.圆盘大小限定死了吗？如果圆盘大小是限定的，则用六方堆积圆盘，你用了立方堆积，很浪费空间。
2.如果有大有小，则尽可能用最大圆盘进行六方堆积，用尽以后空白处用次一号的圆进行六方堆积。
米粒随机意味着我可以认为米粒是均匀分布，米粒密度 x 圆盘大小为圆盘下覆盖米粒数的期望；圆下米粒数服从二项分布，假设 p=圆盘面积(A)/底面积，则 P(n; N, A) NCn p^n(1-p)^(N-n) 为总 N 粒米，圆盘下 n 粒米的概率，所以期望是 Np, 方差是 Np(1-p)，你可以用来估计某面积圆盘下大过 50 粒米的概率，最后对大圆盘进行加强覆盖。

所以，我觉得一个很简单的方案是选一个 p(50; N, A) 比较小的某个大小的圆盘进行六方堆叠，判定一下如果有超过 50 个粒子的在上面直接覆盖一个圆盘完事。因为当圆直径 /平面边长比较小(<0.3)的时候，数密度大概是 0.25 ，也就是方形面积 x0.25 个圆，能够达到 0.91 的覆盖率。平均每个圆大概覆盖 22% 左右的米粒。

参考：
https://en.wikipedia.org/wiki/Circle_packing
https://en.wikipedia.org/wiki/Circle_packing_in_a_square

[necomancer]

抱歉，最后写得有点脑残：
方形面积 x 0.25 个圆，覆盖 0.91 的面积，平均每个圆覆盖 3.64% 的面积，或者在均匀分布下，3.64%的米粒……

[necomancer]

如果涉及大圆超过 50 个粒子，需要在大圆上覆盖其他圆的时候，参考：
https://en.wikipedia.org/wiki/Circle_packing_in_a_circle
圆里继续做堆积……

我感觉你问的问题还是有点 bug 的……其实如果每个圆选取时个数时无限的，大小随意，需求是覆盖所有米粒，那么是不是一直拿能盖住所有粒子的圆往上堆，到 米粒总数 /50 个圆完事……

[caneman]

@necomancer

米粒落点并不是均匀的，有的地方稀疏有的地方稠密，有的地放可能很大一块面积没有任何米粒，有的地方可能挤的满满的，甚至一个米粒上面堆叠了另一个米粒（但是单点堆积数<50 ），不知道棋盘上米粒的密度分布情况（黑盒），只有当圆盘落下才会知道圆盘盖到了多少米粒，仅有此一项数据输出。

圆盘可以任意大小，圆盘可以撤掉 /更换（撤掉不计入次数），我上面那个圆上堆小圆的思路是把大圆撤掉用小圆去覆盖原来大圆的位置。

另外，尽可能少的尝试次数（这个次数不是到最后的使用盘子数，而是整个过程中用过盘子的总次数（撤掉盘子不计入总次数），例如放了个大盘，其覆盖米粒大于 50，撤掉大盘，改成 5 个小盘，每个小盘覆盖<50，满足条件，总的尝试次数为 1+5=6 次）。

可以不覆盖全部粒子，尽可能少的圆盘总使用次数去覆盖尽可能多的米粒，寻找一个平衡吧。

这个问题应该是没有 BUG 的，有的话欢迎再一起讨论，天体物理学中粒子密度分布计算，好像有涉及到类似的问题。

PS：圆里面做堆积的资料很有用，谢谢！

[caneman]

@fzy0728
这个可以打开吗？
http 冒号 //www 点 caneman.cn/wp-content/uploads/2019/05/dock.jpg

[caneman]

图裂的试试这个：
http://www.caneman.cn/wp-content/uploads/2019/05/2019-05-09-10-13-09.png
（ http 冒号 //www 点 caneman 点 cn/wp-content/uploads/2019/05/2019-05-09-10-13-09 点 png ）

[fzy0728]

尽可能少的尝试...如果是我的话会先预测米粒的分布，最少的尝试找到米粒的分布情况用圆进行分割。说一下我的想法哈，如果可以的话用（尽可能少，心里可以承受的一个值） k 个圆随机分布棋盘，类似于蒙特卡洛方法去预测棋盘上米粒分布，例如整个棋盘面积和覆盖圆面积下的米粒个数，计算大致棋盘米粒数，再根据圆盘下的米粒个数大致划分棋盘，为子棋盘，再对子棋盘用圆去划分。"近似估计+分割+覆盖"

[necomancer]

嗯……既然米粒空间分布不可知，那么第一次，比如我选择大过底面的圆覆盖，算不算我已经知道了米粒的空间分布信息？还是只返回一个米粒个数？如果只返回米粒个数，假设粒子数也比较多，那么可不可以这样尝试：
1. 使用一个大圆求出总粒子数；>50 撤掉，<50 问题解决；
2. 四等分底面，用四个圆分别覆盖，<50 保留并跳过此 1/4 的区间，>50 撤掉并将这个区间继续四等分
重复以上步骤，直到所有圆下面粒子<50，是不是 O(Log(A)) 次尝试？

[necomancer]

所用的圆是大于这个四等分区间的，所以不存在漏掉粒子的问题。

[necomancer]

好像不是 O(Log(A))……算了，熬夜脑袋不太对。
或者第一步使用六方堆积，用 ~0.25 A 次尝试求出空间分布，再根据空间分布一次性解决问题？

[caneman]

@necomancer
盖上只能知道数量，这种一直往下迭代的方法是可行的，就是不知道这是不是最好的算法了。
如果问题再延申一下，如果上层的圆盘盖米数会计入下层圆盘覆盖的米粒数量呢？就是每个圆盘覆盖的米粒数是这个圆盘下所有的米粒数而不是 这个圆盘下未被其他下层圆盘覆盖过的米粒数。

[necomancer]

@caneman 没太理解，因为如果一个位置上叠加 1000 粒米，如果圆盘可以叠加，则需要 20 个。如果圆盘是上层会计入下层，那么无论怎么覆盖都覆盖不了啊，因为 1000 粒米在同一个位置，选多小的圆都会有交叠。

迭代法可能要考虑到最好和最差，我现在脑袋有点残，有时间我算一下。但是原则上六方堆积那个很好算，第一次使用大约 0.25A 次尝试求出粒子空间分布，第二次直接用大概 N/50 个圆进行覆盖。总尝试次数很稳定。当然，因为是保留用来探测粒子分布且覆盖小于 50 粒子的圆，总测试次数要很大程度上小过 0.25A + N/50 的，最差情况就是所有粒子堆叠，分布均匀应该会省力很多。

[adamwong]

不是图遍历吗就行吗，类似 n 个最大岛?