在 O(n) 时间内找到 n x n 矩阵中的局部最小值 [英] Find local minimum in n x n matrix in O(n) time

问题描述

所以，这不是我的家庭作业问题，而是取自关于算法和数据结构的coursera课程(现已完成)的未分级作业.

So, this is not my home work question, but it is taken from an ungraded homework of the coursera course on algorithms and data structures (which is now complete).

您将获得一个由不同数字组成的 n x n 网格.如果一个数小于其所有邻居，则该数是局部最小值.(数字的邻居是紧靠上方、下方、左侧或右侧的一个.大多数数字有四个邻居；旁边的数字有三个；四个角有两个.)使用分而治之的算法设计计算局部最小值的范式，仅在数字对之间进行 O(n) 次比较.(注意:由于输入中有 n² 个数字，您无法查看所有数字.提示:考虑哪种类型的重复会给您带来所需的上限.)

You are given an n by n grid of distinct numbers. A number is a local minimum if it is smaller than all of its neighbors. (A neighbor of a number is one immediately above, below, to the left, or the right. Most numbers have four neighbors; numbers on the side have three; the four corners have two.) Use the divide-and-conquer algorithm design paradigm to compute a local minimum with only O(n) comparisons between pairs of numbers. (Note: since there are n² numbers in the input, you cannot afford to look at all of them. Hint: Think about what types of recurrences would give you the desired upper bound.)

由于数字不按任何顺序排列，我不知道除了 O(n²) 比较之外，我们还能怎么办.

Since the numbers are not in any order, I don't see how we can get away with any thing but O(n²) comparisons.

推荐答案

我们可以调整 Words Like Jared 的答案，看看它是如何出错的.

We can adapt Words Like Jared's answer, by looking at how it can go wrong.

那个答案中的想法 - 这是一个很好的 - 是滚下坡".这只是意味着，如果您在一个元素上，请检查它是否是局部最小值.如果是这样，你就完成了；否则，步进到最小的最近邻居.最终这必须终止，因为每一步都是针对一个更小的元素，而这不能在有限数组中永远持续下去.

The idea in that answer -- which is a good one -- is to "roll downhill". This just means, if you are on an element, check if it is a local minimum. If so, you are done; otherwise, step to the smallest of its nearest neighbors. Eventually this must terminate because every step is to a smaller element, and that cannot go on forever in a finite array.

这种方法的问题在于滚动"可能会在整个地方蜿蜒:

The problem with this approach is that the "rolling" can meander all over the place:

20 100 12  11 10 100  2
19 100 13 100  9 100  3
18 100 14 100  8 100  4
17  16 15 100  7   6  5

如果从左上角开始滚下坡"，您将访问数组中大约一半的元素.这太多了，所以我们必须限制一下.

If you start at the upper left and "roll downhill", you will visit around half of the elements in the array. That is too many, so we have to constrain it a bit.

首先检查中间的列和中间的行.在所有这些元素中找到最小的元素并从那里开始.

Start by examining the middle column and middle row. Find the smallest element among all of those and start there.

从那里下坡"一步，进入四个象限之一.您将输入其中一个象限，因为中间列和/或行中的相邻元素较大，因此只有两个相邻象限中的一个可能是下坡".

Roll one step "downhill" from there to enter one of the four quadrants. You will enter one of the quadrants, because the adjacent elements in the middle column and/or row are larger, so only one of the two adjacent quadrants could be "downhill".

现在考虑如果你从那里滚下坡"会发生什么.显然，您最终会达到局部最小值.(我们实际上不会这样做，因为这会花费太长时间.)但是，在滚动的过程中，您永远不会离开那个象限......因为要这样做，您将不得不穿越中间列或中间行，并且这些元素中没有一个小于您开始的位置.因此，该象限在某处包含局部最小值.

Now consider what would happen if you "rolled downhill" from there. Obviously, you would eventually reach a local minimum. (We will not actually do this because it would take too long.) But, in the course of rolling around, you would never leave that quadrant... Because to do so, you would have to cross either the middle column or middle row, and none of those elements are smaller than where you started. Therefore that quadrant contains a local minimum somewhere.

因此，在线性时间内，我们确定了一个必须包含局部最小值的象限，并将 n 减半.现在只是递归.

Thus, in linear time, we have identified a quadrant that must contain a local minimum, and we have cut n in half. Now just recurse.

这个算法需要时间 2n + 2n/2 + 2n/4 + ...，等于 4n，这是 O(n) 所以我们完成了.

This algorithm takes time 2n + 2n/2 + 2n/4 + ..., which equals 4n, which is O(n) so we are done.

有趣的是，除了关键部分:证明算法有效.

Interestingly, we did not use "rolling downhill" very much at all, except for the critical part: Proving that the algorithm works.

[更新]

正如 Incassator 指出的，这个答案并不完全正确，因为在你只是递归"之后你可能会推出再次进入象限...

As Incassator points out, this answer is not entirely correct, because after you "just recurse" you might roll out of the quadrant again...

最简单的解决方法是在滚下坡"之前找到中间行、中间列、和边界中最小的元素.

The simplest fix is to find the smallest element among the middle row, middle column, and boundary before you "roll downhill".

这篇关于在 O(n) 时间内找到 n x n 矩阵中的局部最小值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！