Wil*_*Bur 18 algorithm math optimization search
在编码过程中,我遇到了如下问题:在具有最高粒子密度的2D空间中找到固定大小的区域.可以认为颗粒通常在整个空间上随机分布,但理论上应该存在一些具有更高密度的区域.
例如,100个粒子随机放置在500x500的2D网格中,我需要找到具有最多粒子(最高密度)的50x50区域.
除了对每个可能的区域进行蛮力测试之外,还有其他方法来计算最佳区域(在这种情况下,大约有200000多个区域)吗？对于n长度轴,这将在O(n ^ 2)处向上扩展.
创建500x500 2D阵列,其中每个单元格包含该单元格中粒子数量的计数.然后将该阵列与50x50内核进行卷积,得到的数组将在每个单元格中的50x50区域中具有粒子数.然后找到具有最大值的单元格.
如果您使用50x50的盒子作为区域,则可以将内核分解为两个单独的卷积,每个卷对应一个卷积.得到的算法是O(n ^ 2)空间和时间,其中n是您正在搜索的2D空间的宽度和高度.
作为提醒,具有boxcar功能的一维卷积可以在O(n)时间和空间中完成,并且可以在适当的位置完成.令x(t)为t = 1..n的输入,并让y(t)为输出.对于t <1且t> n,定义x(t)= 0和y(t)= 0.将内核f(t)定义为0为0..d-1为1,其他地方为0.卷积的定义给出了以下公式:
y(t)= sum ix(ti)*f(i)= sum i = 0..d-1 x(ti)
这看起来需要时间O(n*d),但我们可以将其重写为重复:
y(t)= y(t-1)+ x(t) - x(td)
这表明一维卷积是O(n),与d无关.要执行二维卷积,只需对每个轴执行一维卷积.这是因为可以分解boxcar内核:通常,大多数内核都不能被分解.高斯内核是另一个可以分解的内核,这就是图像编辑程序中高斯模糊如此之快的原因.
对于您指定的数字类型,这将非常快.500x500是一个非常小的数据集,您的计算机最多可以在几毫秒内检查202,500个区域.您将不得不问自己是否值得花费额外的时间,数天或数周的时间来进一步优化.
这与justhalf的解决方案相同,除了由于分解卷积,区域大小不会影响算法的速度.
假设至少有一点.不失一般性,将2D空间视为整个平面.设d是该区域的宽度和高度.设N为点数.
引理:存在一个最大密度的区域,其左边有一个点.
证明:设R是最大密度的区域.设R'是相同的区域,右边是R的左边缘和R的最左边点之间的距离.R中的所有点也必须位于R'中,因此R'也是最大密度的区域.
将所有点插入KD树.这可以在O(N log 2 N)时间内完成.
对于每个点,请考虑宽度为d和高度为2 d的区域,其中点位于区域的左边缘的中心.称这个地区为R.
在KD树中查询区域R中的点.调用此组S.这可以在O(N 1/2 + | S |)时间内完成.
找到包含S中最大点数的R的dxd子区域.这可以在O(| S | log | S |)时间内通过用y坐标排序S然后执行线性扫描来完成.
得到的算法的时间为O(N 3/2 + N | S | log | S |).
当密度高时,算法#1优于算法#2.算法#2仅在粒子密度非常低时才优越,并且算法#2优越的密度随着总板尺寸的增加而降低.
注意,连续情况可以被认为是零密度,此时只有算法#2起作用.