【アルゴリズム】第四課学習ノート

一、局部の最大値を求める
1.テーマ
重複要素のない配列A[0...N-1]を与え、その配列の局所最大値を求める.規定:配列境界外の値は無限に小さい.すなわち、A［0］＞A［−1］,A［N−1］＞A［N］である.
明らかに、一度遍歴するとグローバル最大値が見つかり、グローバル最大値は明らかにローカル最大値であり、時間複雑度はO(N)である.
もっと速い方法がありますか?
2.分析
まず「高原配列」の定義を与える(鄒博先生が自作した).
定義:サブ配列Array[from,...,to]が満たされる場合

Array[from]＞Array[from-1]

Array[to]＞Array[to+1]

このサブ配列を「高原配列」と呼ぶ.
例えば配列3,5,1,2,6,7,14については,2<6,14>4のため,6,7,14がその中の1つの高原配列であると考えられる.画像では、
高原配列の長さが1の場合、その高原配列の要素は局所最大値である.
したがって,局所最小値を探すアルゴリズムは長さ1の高原配列を探すことになる.(ここで特に注意!問題ではローカル最大値を1つ見つけるだけでいいです!)
アルゴリズムの説明:インデックスleft、rightを使用して、それぞれ配列の先頭と末尾を指し、定義に基づいて、この配列は高原配列である.

中点mid=(left+right)/

を求める

A[mid]>A[mid+1]、サブ配列A[left...mid]は高原配列

廃棄後半:right=mid

A[mid+1]>A[mid]、サブ配列A[mid...right]高原配列

前半を破棄:left=mid+1

left=right

まで再帰
このアルゴリズムの時間的複雑度はO(logn)であり,最も重要なのは我々にいくつかの思考上の啓発,すなわち特に大きなデータを与え,私は完全に遍歴する必要はなく,このデータの中のいくつかの有効な局所的特徴を知ることができる.
3.コード

/**
 *          
 */
int local_maximum(const int* a, int n){
    int left = 0;
    int right = n - 1;
    int mid;
    while(left < right){
        mid = (right - left) / 2 + left; 
        //    ，   mid = (left + right) / 2 
        cout<a[mid+1])
right = mid;
else
left = mid + 1;
}
return a[left];
}

二、サブセットと数の問題
1.テーマ
配列A[0...N-1]は既知であり、ある数値sumを与え、配列中のいくつかの数(0個またはn個であってもよい)を探し出し、これらの数の和がsumとなるようにする.(配列中の要素が0:A[i]>0より大きいと仮定)
たとえば、
配列1,2,3,4,5に対してsum=10が与えられると、条件を満たすいくつかの数がある.
1, 2, 3, 4
1, 4, 5
2, 3, 5
2.分析とコード
明らかに,この問題はNPの完全な問題である.
この問題に対して、ブールベクトルx[0…N-1](タグ配列)を設定してどの要素を取ったかを表すことができ、x[i]=0はA[i]を取らないことを示し、x[i]=1はA[i]を取ることを示し、0-1リュックサック問題の設定方法と類似している.
(1). DFS再帰遍歴
まず,DFS再帰ループに登場し,関数のパラメータiを用いて現在進行中の位置を表し,hasを用いて加入した要素の現在の和を表し,コードは以下の通りである.

int a[] = {1,2,3,4,5};
int n = sizeof(a) / sizeof(int);
int sum = 10;

/**
 *     
 * x[]    ，i   a[i]    ，has      
 */
void enum_sum_number(bool *x, int i, int has){
    if(i>=n) return;
    if(has + a[i] == sum){
        x[i] = true;
        print(a,x); //         
        x[i] = false;
    }
    x[i] = true;
    enum_sum_number(x, i + 1, has + a[i]);
    x[i] = false;
    enum_sum_number(x, i + 1, has);
}

(2). ぶんきげんかいほう
そしてDFSの最適化を考えると分岐限界法がある.配列A[0…N−1]の要素が0より大きいことを前提として、ブランチをどのように境界するかを考慮する.考察ベクトルx[0…N−1]は、前のi個の値が確定したと仮定し、次にi+1個目の値x[i]が0であるか1であるかを判定する.x[0...i-1]によって決定されたA[0...i-1]の和をhasとする.A[i,i+1,...N−1]の和はresidue(rと略記)である.

has + a[i] ≤ sum、has + r ≥ sum:x[i]は1であってもよい.

has + (r - a[i]) >= sum:x[i]は0であってもよい.

(コードを記述してブランチに入るときは、ブランチに重複しないように注意してください!)
コードは次のとおりです.

/**
 *     
 */
void enum_sum_number2(bool *x, int i, int has, int residue){
    if(i>=n) return;
    if(has + a[i] == sum){
        x[i] = true;
        print(a,x);
        x[i] = false;
    } else if(has + residue >= sum && has + a[i] <= sum){
        //       else if ，       has + a[i] == sum  ，
        //        a[i] ，           a[i] 
        x[i] = true;
        enum_sum_number2(x, i + 1, has + a[i], residue - a[i]);
    }
    if(has + residue - a[i] >= sum){
        x[i] = false;
        enum_sum_number2(x, i + 1, has, residue - a[i]);
    }
}

数理論理の重要な応用:分岐限界の条件
考え:

分岐限界の条件は十分な条件ですか?(いいえ、必要条件です)

新しいテーマの中で、どのように分岐限界の条件を発見します.

(この方法を学ぶことは、この問題自体よりも重要です)
(3). 負数を考慮した場合
配列−3,−5,−2,4,2,1,3,与えられたsum=5,
要件に合致する数は
-3, -2, 4, 2, 1, 3
-3, 4, 1, 3
-5, 4, 2, 1, 3
-2, 4, 2, 1
-2, 4, 3
4, 1
2, 3
DFSは列挙であるため,正確な解が得られるに違いないが,負の数の場合をどのように分岐限界を行うかが鍵となる.
次の方法を示します.
配列A[0...N-1]全体を正負に並べ替えて、負数が前面になり、正数が後になるようにして(負数部分が前面にあることを保証するだけでよく、負数部分の内部も秩序があることを保証する必要はない)、残りの正数の和を分岐限界として制約する:

A[i]が負の場合:すべての正数を計算しても足りない場合は、A[i]を選択できません.

再帰が正数範囲に入った場合、配列が全正数である場合に正常に処理する.

コードは次のとおりです.

/**
 *          ，   negative positive
 */
void positive_negative_sort(int a[], int n, int &negative, int &positive){
    int k = 0;
    negative = positive = 0;
    for(int i=0; i= n) return;
    if(has + a[i] == sum){
        x[i] = true;
        print(a,x);
        x[i] = false;
    } 
    if(a[i] > 0){
        //      
        if(has + positive >= sum && has + a[i] <= sum){
            x[i] = true;
            enum_sum_number3(x, i + 1, has + a[i], negative, positive - a[i]);
            x[i] = false;
        }
        if(has + positive - a[i] >= sum){
            x[i] = false;
            enum_sum_number3(x, i + 1, has, negative, positive - a[i]);
        }
    } else {
        //      
        if(has + x[i] + positive >= sum){
            x[i] = true;
            enum_sum_number3(x, i + 1, has + a[i], negative - a[i], positive);
            x[i] = false;
        }
        if(has + negative <= sum && has + positive >= sum){
            x[i] = false;
            enum_sum_number3(x, i + 1, has, negative - a[i], positive);
        }
    }
}