二维峰算法找不到峰

Question

我刚开始学习麻省理工学院的算法课程，我们学习了二维寻峰算法。我试过干燥运行并实施它，但算法似乎对这个输入失败。

{5, 0, 3, 2}
{1, 1, 2, 4}
{1, 2, 4, 4}

这是算法：

• Pick middle column j = m/2
• Find global maximum on column j at (i,j)
• Compare(i,j−1),(i,j),(i,j+1)
• Pick left columns of(i,j−1)>(i,j)
• Similarly for right
• (i,j) is a 2D-peak if neither condition holds ← WHY?
• Solve the new problem with half the number of columns.
• When you have a single column, find global maximum and you‘re done.

更新，这是我试过但似乎不起作用的代码：

#include <bits/stdc++.h> 
using namespace std; 

const int MAX = 100; 

int findMax(int arr[][MAX], int rows, int mid, int& max) 
{ 
    int max_index = 0; 
    for (int i = 0; i < rows; i++) { 
        if (max < arr[i][mid]) { 
            max = arr[i][mid]; 
            max_index = i; 
        } 
    } 
    return max_index; 
} 

int findPeakRec(int arr[][MAX], int rows, int columns, int mid) 
{ 
    int max = 0; 
    int max_index = findMax(arr, rows, mid, max); 
    if (mid == 0 || mid == columns - 1) 
        return max; 
    if (max >= arr[max_index][mid - 1] && max >= arr[max_index][mid + 1]) 
        return max; 
    if (max < arr[max_index][mid - 1]) 
        return findPeakRec(arr, rows, columns, mid - ceil((double)mid / 2)); 
    return findPeakRec(arr, rows, columns, mid + ceil((double)mid / 2)); 
} 

int findPeak(int arr[][MAX], int rows, int columns) 
{ 
    return findPeakRec(arr, rows, columns, columns / 2); 
} 

int main() 
{ 
    int arr[][MAX] = { { 5, 0, 3, 2 }, 
                       { 1, 1, 2, 4 }, 
                       { 1, 2, 4, 4 }, 
                       { 3, 2, 0, 1 } }; 
    int rows = 4, columns = 4; 
    cout << findPeak(arr, rows, columns); 
    return 0; 
}

这就是我实现算法的方式。

Answer 1

算法正确（只是第四个要点的拼写错误：“of”应该读作“if”）。

您错过了“高峰”的正确定义。峰值查找算法旨在找到 local 最大值，不一定是 global 最大值。对于全局最大值，算法很简单，您只需逐行扫描寻找最大值。

但峰值查找效率更高，因为并非所有值都需要检查。

二维峰算法找不到峰

2D Peak Algorithm fails to find the peak

algorithm

2d