所以,这不是我的家庭工作问题,而是取自关于算法和数据结构(现已完成)课程的未分级作业.
您将获得一个n×n个不同数字的网格.如果数字小于其所有邻居,则该数字是局部最小值.(一个数字的邻居是紧靠上方,下方,左侧或右侧的一个.大多数数字有四个邻居;侧面的数字有三个;四个角有两个.)使用分而治之的算法设计用于计算局部最小值的范例,仅对数字对进行O(n)比较.(注意:由于输入中有n 2个数字,因此您无法查看所有数字.提示:考虑哪种类型的重复会为您提供所需的上限.)
由于数字不是任何顺序,我不知道除了O(n 2)比较之外我们怎么能逃脱任何事情.
Nem*_*emo 33
我们可以通过查看它可能出错的方式来调整像Jared的答案.
答案中的想法 - 这是一个很好的 - 是"滚下山".这只是意味着,如果您在元素上,请检查它是否是局部最小值.如果是这样,你就完成了; 否则,步入最近的邻居.最终这必须终止,因为每个步骤都是一个较小的元素,并且不能永久地在有限数组中继续.
这种方法的问题在于"滚动"可以在所有地方蜿蜒:
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
如果从左上角开始并"滚动下坡",您将访问阵列中大约一半的元素.这太多了,所以我们不得不限制它.
首先检查中间列和中间行.找到所有这些中最小的元素并从那里开始.
从那里"下坡"一步,进入四个象限中的一个.您将输入其中一个象限,因为中间列和/或行中的相邻元素较大,因此两个相邻象限中只有一个可能是"下坡".
现在考虑如果你从那里"滚下山"会发生什么.显然,你最终会达到当地最低标准.(我们实际上不会这样做因为它需要太长时间.)但是,在滚动的过程中,你永远不会离开那个象限......因为这样做,你将不得不越过中间列或中间行,这些元素都不比你开始时小.因此,该象限在某处包含局部最小值.
因此,在线性时间内,我们确定了一个必须包含局部最小值的象限,并且我们将n减半.现在只是递归.
该算法需要时间2n + 2n/2 + 2n/4 + ...,等于4n,即O(n),所以我们完成了.
有趣的是,除了关键部分之外,我们根本没有使用"滚下坡":证明算法有效.
[更新]
正如Incassator所指出的那样,这个答案并不完全正确,因为在你"只是递归"之后你可能会再次滚出象限......
最简单的解决方法是在"下坡"之前找到中间行,中间列和边界中的最小元素.
Inc*_*tor 14
Nemo接受的答案很好但不完全正确:
因此,在线性时间内,我们确定了一个必须包含局部最小值的象限,并且我们将n减半.现在只是递归.
我指的是"只是递归"一点.问题是我们不能直接这样做,因为在下一次迭代中我们可能会找到一个局部最小值,它不是原始网格的局部最小值(x下面表示一些任意大的数字):
x x 39 x x 50 x x x x x
x x 38 x x 49 x x x x x
37 36 33 34 35 48 x x x x x
x x 32 x 1 10 x x x x x
x x 31 x x 47 x x x x x
46 45 30 44 43 60 51 52 53 54 55
x x 2 x x 56 x x x x x
x x x x x 57 x x x x x
x x x x x 58 x x x x x
x x x x x 59 x x x x x
在第一次迭代中,我们发现10是中间行和中间列的最小值.我们向左走(1小于10).所以我们的下一次迭代是左上象限.但现在中间行和列的最小值将为31(如果象限的边界被认为是其中的一部分,则为30).然后,您将得出结论,这是当地的最低要求.但它并不适用于整个电网.
我们可以通过各种方式纠正这一不幸的缺陷.我这样解决了:
在除了网格本身之外的每次迭代中,我们跟踪当前最小候选者(在第一次迭代之后是上述示例中的1;在初始状态中,我们可以说最小候选者是加上无穷大).我们计算中间行和列的最小值并将其与最小候选者进行比较.如果后者较小,我们会进入包含最小候选者的象限.否则我们会忘记先前的候选人,然后检查新的中间行/列最小值是否实际上是局部最小值.如果没有,那么像往常一样递归到我们向下倾斜的任何象限(并跟踪新的最小候选者).
或者,您可以按照MIT讲座中的描述修改过程:在每次迭代中,不是查看中间行/列,您可以查看中间行/列和网格边界.然后算法再一次是正确的.
你选择你喜欢的方式.
我认为这其实很容易.
将问题转换为3-D,以了解算法的工作原理.将矩阵放在桌子上.假装柱子延伸出每个单元格,并且柱子的高度与其值成正比.把球放在任何支柱上.让球始终落在最低高度的相邻支柱上,直到达到局部最小值.