3

私はこのアルゴリズムを再構築しようとしています:
http://courses.csail.mit.edu/6.006/fall10/lectures/lec02.pdf
(ページ 14 "アルゴリズム II")
(Google でこれを見つけました。残念ながら私は MIT にいません: ）これは宿題ではありません）

それは次のとおりです。

•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!

私が持っているのはこれです：

トリミングされたのは、サイズの頻度 (blockSizeSmall-minBlockSize) を保持するベクトルです。

trimmed.size()したがって、列と (blockSizeSmall-minBlockSize) 行を持つ 2D マトリックスです。

簡単にするために、ピークを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# のアルゴリズムを次に示します。論文の 1 つの例以外はテストされていませんが、動作するはずです。「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 に答える