2D网格问题的算法？

Question

我会诚实地告诉你，这是一个作业问题，但我就是找不到解决方案。请记住，我不是要答案，只是需要一些指导。

问题： 设计一个算法，以O(n)时间（线性）运行，可以在2D网格上定位单个可疑房屋（点）。如果它消耗了等于或大于其两个垂直和两个水平邻居的电力消耗，则它是可疑的。注意：只需返回一个可疑的房子。

解决方案： 甚至不确定如何实现这样的解决方案。如果您检查n个房屋，还可以检查其四个周围的邻居。4n/n ^ 2，简化为4 / n。这意味着随着网格的扩展，很少能找到可疑的房屋。

我尝试过的： - 不同的数据结构（大多数是nlogn） - 折叠网格（再次nlogn）

提前致谢。

编辑： 我的错误，网格是（n x n），使房屋数量为n ^ 2，对此混淆感到抱歉。

编辑2： 这正是问题，也许我读错了吗？

警察正在寻找特别高的电力消耗的房屋。为了简化问题，想象他们正在调查布置在n×n网格上的房屋。网格上的每个房子都有一些电力消耗，e（i，j）。如果它的电力消耗等于或大于其垂直和水平邻居中的每一个，则警察认为该房屋可疑。设计一个算法，在O（n）时间内返回可疑房屋的位置。

- rvk

---

我认为这是一个简单的O(n)问题（其中n = 行数 * 列数）。 - H H

输入是什么样子的？你只是得到一个值的网格还是其他什么东西？ - Winston Ewert

好的，现在请更具体地说明一下“可疑”的部分。当一栋房子的消耗量仅比每个邻居多或比2|4个邻居的总和更多时，它是否就是可疑的？ - H H

读取数据只需要O(N^2)的时间。当你有N^2个房子时，我认为你无法在O(N)的时间内完成。 - Leonid

@meriton，是的，这很可疑。正是察觉到这种可疑行为，我才想出了如何解决它的方法。他们只会有那种奇怪的行为有其原因。 - Winston Ewert

Answer 1

你要做的就是寻找用电量最高的房子。你可以从任意一所房子开始，如果相邻的房子用电量更高，则向其步进（重复此过程，直到没有相邻的房子用电量更高）。

这将在n x n网格上花费O（n）的时间。

编辑：评论者是正确的，最坏情况下可能需要O（n ^ 2）的时间。

- Keith Randall

---

我认为那样做不行。你可能会找到一个低于阈值的局部最大值，但另一个局部最大值可能会高于它。 - Winston Ewert

@Winston：这个问题是关于一个局部最大值，而不是最佳值。 - H H

有道理。非常感谢大家。@Henk Holterman他的回答并不是一个证明，只是一个算法描述。我现在正在自己进行证明，因为我有了方向。 - rvk

@Henk Holterman，我明白了，我对问题的理解不同。我认为它是邻居的总和。然而，我并不认为找到局部最大值一定能在O(n)步骤内成功。举两个例子：第一个例子，除了一个房子以外，所有房子都没有使用，而剩下的房子使用了1。我们将不得不扫描n^2个单元格才能找到它。第二个例子，可以构建一个网格，在图形上呈锯齿状缓慢增加，导致我认为必须访问n^2/2个单元格。 - Winston Ewert

为什么升序路径的长度是O(n)？ - meriton

Answer 2

Keith提出的局部最优解并不能在线性时间内运行。问题在于它无法保证路径长度为O(n)。

然而，考虑一下如果你查看中间行和列中的所有房屋会发生什么。特别是考虑如何利用这个来帮助你的局部最优解。

（未提供完整解决方案，因为它是一个作业）尽管如此，这是一个非常棒的问题。向它的创造者致敬。

[编辑：一个提示]

之前提供的解决方案在这种情况下会失败：

X.XXX.XXX.X
X.X.X.X.X.X
X.X.X.X.X.X
X.X.X.X.X.X
XXX.XXX.XXX

这里的 "." 代表非常小的电力使用量，而 "x" 代表逐渐增加的电力使用量。

如果我们查询中间行会发生什么？

X.XXX.XXX.X
X.X.X.X.X.X
&&&&&&&&&&&
X.X.X.X.X.X
XXX.XXX.XXX

我们看过的房子在哪里？我们已经成功地穿过了这条路。如果我们从找到的最佳点开始爬山，我们就能避免走长路。（但我们仍然不能保证路径足够短）

[编辑：第二个提示]

按照上面提到的方法扫描中间行。取最大值。向上或向下移动到更大的值（如果无法移动，则该网格单元是局部最优解，您可以停止）。现在考虑一个递增值的路径。这条路径不可能再次穿过中间行，因为该行中所有值必须小于当前单元格的值。（因为当前单元格必须大于该行中的最大值）。这意味着我们基本上将问题减半了。

- Winston Ewert

---

@user492986，我有点犹豫要给多少帮助。你们班有关于外部协助的政策吗？ - Winston Ewert

让我来澄清一下。'失败'的情况不是nn，而是kn，其中k是某个正常数。因为我们仍然没有检查所有的空格。 - rvk

@user492986，k不是一个常数，因为它随着n的增加而增加。特别地，这种情况要求我必须访问每一列的其他元素。因此，k大约是n/2，复杂度为O(n^2)。 - Winston Ewert

显然这与分治有关，一个级别，有什么想法吗？ - rvk

@user492986，哦，我知道答案，只是在给提示，因为这是一项任务。文本已更新，又加了一个提示。 - Winston Ewert