2D贪心上升搜索算法澄清说明

Question

我正在进行一些算法方面的补习，因为我将在秋季修读研究生课程，并且我是物理学本科生。观看视频，在第38:00分钟，他介绍了一个二维数组的贪心上升算法。我很困惑，因为他将峰定义为 a <= b,c,d,e（其中b、c、d和e是当前元素'a'左侧、右侧、上方、下方的元素）。然后他接着说，要找到峰值，可以跟随'a'上最大的元素边界，但如果你有以下未排序的2D数组：

20 15 13
12 10 10
40 40 40

并从13开始，贪心上升算法不会错误地将20认定为峰值吗？如何在不查看每个元素的情况下搜索未排序的数组呢？

非常感谢您的帮助，如果这是一个愚蠢的问题，请提前道歉。

- Erich Robinson-Tillenburg

Answer 1

请注意定义，因为它们与您直觉所期望的不同。

他将峰定义为<= b,c,d,e (其中b、c、d和e是当前元素'a'左、右、上、下的元素)。

所以你有了一个定义为本地最大值(比所有相邻元素都大的元素)，而不是全局最大值(比所有其他元素都大的元素)的峰。根据这个定义，很明显，虽然20不是最大的元素，但它是一个峰。

(正如评论中所指出的那样，该定义可能应该是>= b,c,d,e，这可能只是原始帖子中的一个笔误)

- Flight Odyssey

---

难道不是 a >= b，c，d，e 吗？ - pramesh

Answer 2

我已经观看了视频，问题陈述如下：如果存在峰值，则找到峰值。根据定义，保证总会有一个峰值。峰值不一定是全局最大值。接下来的问题是：如何在不查看每个元素的情况下搜索未排序的数组？如果未排序，那么您无法做到这一点，因为潜在地每个元素都可能是您要查找的元素。但是，当我将您的问题与峰值查找问题相关联时，他正在使用贪心方法查找满足特定条件的元素，而不是在数组中查找任何特定元素。通过使用贪心方法，我们希望尽早找到它，但不能保证。

- shubham ranjan

Answer 3

我也正在学习那门课程，而他所定义的峰值是指一个元素，比其相邻的任何元素都要大，例如元素'a'。

在这里，“a”可能是全局峰值[大于矩阵中的所有元素]，无论算法找到什么更快，只要它符合上述条件，就会提供给我们。

关于峰值查找实际上是在查找什么存在一些混淆。它很容易被误认为是数组/矩阵中最大的元素，但实际上取决于所问的问题。如果问题没有指定峰值是什么，通常认为它是遵守上述条件等待算法发现的元素。

看看这个： 贪心上升算法GIF

- Shoaib Wani