时间戳

首页 > 解决方案 > 2D 峰值算法无法找到峰值

algorithm - 2D 峰值算法无法找到峰值

问题描述

我刚刚开始了关于算法的 MIT 课程，我们学习了 2D 峰值查找算法。我尝试空运行并实施它，但该输入的算法似乎失败了。

{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; 
}

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

标签： algorithm2d

解决方案

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

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

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

推荐阅读