3

我正在尝试重建这个算法：
http
://courses.csail.mit.edu/6.006/fall10/lectures/lec02.pdf （第14页“算法II”）
（用谷歌找到这个，不幸的是我不在麻省理工学院： ) 这不是家庭作业)

这是：

•Pick middle column (j=m/2)
•Find global maximum a=A[i,m/2]in that column
    (and quit if m=1)
•Compare a to b=A[i,m/2-1]and c=A[i,m/2+1]
•If b>a   then recurse on left columns
•Else, if c>a   then recurse on right columns
•Else a is a 2D peak!

我所拥有的是：

trimmed是一个向量，它保存我的大小频率（blockSizeSmall-minBlockSize）。

所以它是一个具有trimmed.size()列和 (blockSizeSmall-minBlockSize) 行的二维矩阵。

为了简单起见，我将峰值保存在 2 个 int 向量vector<int> peaksrow和peakscolumn中。

那里有什么问题？
我不明白什么

"Find global maximum a=A[i,m/2]in that column (and quit if m=1)"

应该导致。

    public void findPeaks() {
        for (int column = trimmed.size() / 2; column < trimmed.size();) {
            int globalmax = 0;
            for (int row = 0; row < (blockSizeSmall - minBlockSize); row++) {
                if (trimmed.elementAt(column).reducedFreqs[row] > globalmax) {
                    globalmax = row; 
                    //find globalmax in row
                }
            }
            if (globalmax == 0) {
                break; //<- ???
            } else {
                if (column - 1 >= 0 && column + 1 < trimmed.size()) {
                //stay in bounds
                    if (trimmed.elementAt(column - 1).reducedFreqs[globalmax] > globalmax) {
                        column--; 
                        //if element at left side is > globalmax, recurse on column--;

                    } else if (trimmed.elementAt(column + 1).reducedFreqs[globalmax] > globalmax) {
                        column++; 
                        //if element at right side is > globalmax, recurse on column++;

                    } else { 
                        //if globalmax is higher than right or left element i have a peak
                        peaksrown.add(globalmax);
                        peakscolumnn.add(column);
                        Log.e(TAG, "" + peaksrown.size());
                    }
                }else{
                //what to do when out of bounds ?? break ??
                //if i break here, how can i be sure the algorithm 
                //went to both sides(column=0 and column=max) ??
                //just tried with break here, still infinit loop
                }
            }
        }
    }

它只是无限循环。

4

2 回答 2

3

您似乎不了解递归的概念，所以我建议您查一下。这是 C# 中的一种算法供参考，除了本文中的一个示例之外没有经过测试，但它应该可以工作。我忽略了“如果 m=1 则退出”部分，因为我认为这不是必需的。请注意函数 Peak() 如何从自身内部调用自身，但参数已更改。

    static void Peak(int[,] map, int left, int right)
    {
        // calculate middle column
        int column = (right + left) / 2;


        // get max row in column
        int arow = 0;
        for (int row = 0; row < map.GetLength(0); row++)
            if (map[row, column] > map[arow, column])
                arow = row;

        int a = map[arow, column];

        // get left value
        int b = 0;
        if (column - 1 >= left) b = map[arow, column - 1];
        // get right value
        int c = 0;
        if (column + 1 <= right) c = map[arow, column + 1];

        // if left is higher, recurse left
        if (b > a) Peak(map, left, column - 1);
        // else if right is higher, recurse right
        else if (c > a) Peak(map, column + 1, right);
        // else, peak
        else Console.WriteLine("Peak: " + arow + " " + column + " " + a);
    }

    static void Main(string[] args)
    {
        int[,] map = { {12, 8, 5},
                       {11, 3, 6 },
                       {10, 9, 2 },
                       { 8, 4, 1 } };
        Peak(map, 0, 2);
        Console.ReadLine();
    }
于 2012-05-10T11:12:09.197 回答
1

我认为这个算法有一个微妙的错误。右半部的局部最大值不一定是整个阵列中的局部最大值（例如，当右半部的局部最大值位于其左边界时）。因此，虽然右半部分（假设右更高）有一个局部最大值（整个数组的），但递归调用不一定会找到它。

于 2012-10-31T18:59:15.090 回答