我有一个网格(不一定是正方形，但我将它画成正方形以简化它)以及与每个较小正方形相关联的某些值。给定一个半径为 x 的圆，我试图找到值之和最大的区域。下图就清楚了:
我的猜测是，如果使用大量小方 block 将平面划分为网格，将圆近似为正方形只会导致过度近似，这对我来说最初是可以的，因为我还没有最终确定如何解决圆与部分正方形重叠的情况(它的值是多少？)。
我能想到的最简单的方法是蛮力法:也许从左下角开始，然后开始沿之字形路径移动，直到我们到达右上角并输出总和最大的区域。我对这种方法没意见，但对于大平面区域，会有大量的正方形，而且在某些情况下，这种方法可能会证明是昂贵的。我不确定是否有更好的方法来解决这个问题，但如果有人对如何解决这个问题有其他想法，我将不胜感激。
最佳答案
除非较小方 block 中的数据有趋势，否则我认为可能确实需要一种蛮力方法，尽管您可能想找出一种不需要我认为的多项式或指数时间的方法天真的蛮力方法将需要。
但是，如果有趋势(例如较高的值倾向于组合在一起，或者您更有可能在一侧遇到比另一侧更高的值)，您可以设置一个算法来预测您的区域更有可能包含较高值的网格。
当然，我可能会遗漏一些东西。
关于algorithm - 解决这个网格搜索问题的更好方法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5197084/