算法:圆盘盖米问题(圆的密铺?)

2019 年 5 月 8 日
 caneman

原问题为:

在一棋盘撒米,米粒落点不一,有口径大小不一的若干圆盘,问如何尽可能少的尝试,用圆盘覆盖尽可能多的米粒?(即:尽可能少的米粒裸露在外。)

条件:

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

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

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

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

3984 次点击
所在节点    Python
25 条回复
necomancer
2019 年 5 月 10 日
所用的圆是大于这个四等分区间的,所以不存在漏掉粒子的问题。
necomancer
2019 年 5 月 10 日
好像不是 O(Log(A))……算了,熬夜脑袋不太对。
或者第一步使用六方堆积,用 ~0.25 A 次尝试求出空间分布,再根据空间分布一次性解决问题?
caneman
2019 年 5 月 10 日
@necomancer
盖上只能知道数量,这种一直往下迭代的方法是可行的,就是不知道这是不是最好的算法了。
如果问题再延申一下,如果上层的圆盘盖米数会计入下层圆盘覆盖的米粒数量呢?就是每个圆盘覆盖的米粒数是这个圆盘下所有的米粒数而不是 这个圆盘下未被其他下层圆盘覆盖过的米粒数。
necomancer
2019 年 5 月 10 日
@caneman 没太理解,因为如果一个位置上叠加 1000 粒米,如果圆盘可以叠加,则需要 20 个。如果圆盘是上层会计入下层,那么无论怎么覆盖都覆盖不了啊,因为 1000 粒米在同一个位置,选多小的圆都会有交叠。

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

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://v2ex.ih06.com/t/562157

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX