面白いアルゴリズムの問題の巧みな考え

面白いアルゴリズム
アルゴリズムが面白いのは、彼が繁を簡略化することができ、彼は世の中の万物を概括し、複雑な問題を非常に簡単な問題にまとめることができるからだ.実はすべての高次のアルゴリズムは、2つの大きな方法で解決することができ、何度も試しても気分が悪い.それぞれ動的計画と貪欲なアルゴリズムである.まずダイナミックな計画の問題から話しましょう.
どうてきけいかくもんだい
最長共通サブシーケンス問題(LCS)は,2つのシーケンスXとYを与え,それらの間で最も長い共通サブシーケンスを求める.
わあ、この問題はちょっと難しいですね.最長共通サブシーケンス問題は実際には最も最も簡単な繰返し式にまとめることができ,まずシーケンスX要素の個数をi,Yをj,C[i,j]と仮定して最長共通サブシーケンスの長さを表す.では問題は,この最長共通サブシーケンスの長さをどのように求めるかという問題になる.数式もとても簡単==easy=:smile:
$$C[i, j] =\left{\begin{array}{lr} 0,\quad if\x=0 , or\y=0\C[i-1, j-1] + 1,\quad if ; i,j>0 ; , x_i=y_i\max{C[i, j-1], C[i-1, j]} ,\quad if\i,j>0,\x_ieq x_j\end{array}\right. $$
この公式はやはり難しいですね.たぶんそういう意味でしょう.どうやってこの表現を見るとすごいですか.勝手に2つのシーケンスをください.私は彼を通じて長男のシーケンスの長さを求めることができますか.余計なことは言わないで、コードに直接行って、いったいこんなに牛がいるかどうか見てみましょう.
もし私たちが2つのシーケンスを持っているならば、私たちは文字列で表しましょうX=cnblogs、Y=belong、肉眼で最も長男のシーケンスがblogであることを見ることができます.では、長さは4です.いったいこんな牛がいるのか見てみましょう.
その前に、私は考えを整理しなければなりません.まず、私たちが求めているこのC[i,j]は、実際には2次元のマトリクスです.iは0からiに、jは0からjに、それはi行j列のマトリクスではないでしょうか.ターゲット値は右下のこの要素です.こうなった以上はやりやすい.

// this code calculate the max length of common sub-sequence of 2 strings
int lcs_length(string a, string b) {
    // given 2 string, return the LCS length
    // define a 2 dim array
    int matrix[a.size()+1][b.size()+1];
    for (int i = 0; i <= a.size(); ++i) {
        matrix[i][0] = 0;
    }
    for (int j = 0; j <= b.size(); ++j) {
        matrix[0][j] = 0;
    }

    for(int i = 1; i <= a.size(); i++) {
        for(int j = 1; j <= b.size(); j++) {
            if (a[i-1] == b[j-1]) {
                matrix[i][j] = matrix[i-1][j-1] + 1;
            } else {
                matrix[i][j] = matrix[i][j-1] > matrix[i-1][j] ? matrix[i][j-1] : matrix[i-1][j];
            }
        }
    }
    return matrix[a.size()][b.size()];
}

この関数は最長の共通サブ列の長さを正確に得ることができることは明らかである.相変わらずすごいように見えますが、実は理屈も簡単で、上の3つの公式にほかならない.では、上の3つの公式はどうやって来たのでしょうか.共通サブストリングZの最後の要素がXの最後の要素だとすれば、Yの最後の要素に違いない.Xを最後の要素を削除すれば、Yが最後の要素を削除し、最長の共通サブストリングが削除された+1で、追加されたものになるだろう.では、最後の要素がXではなく、Yの最後の要素だとすれば、もっといいです.このとき、共通のサブストリングはXとYの中間のあるサブストリングですね.このとき、Xは最後のサブストリングを削除して、共通のサブストリングを求めます.やはり同じですね.Yは1つ削除しても、同じですね.直接XかYは1つ削除した共通のサブストリングの最大値になります.(なぜXに等しくないのかと聞かれると、Yは1つの最大値を削除しますか?つまり$$max{C[i-1,j-1],C[i-1,j-1]}$$,これはだめです.理由は簡単です.Xを1つ削除すると、最長男串にYの最後の値が含まれる可能性があります.あなたはすべて削除すると多くの状況が減少し、望ましくありません).
この問題は歴史的な一歩を踏み出した:2つのシーケンスの最長男シーケンスの長さを求めることができる.では、次のステップは、この長男シーケンスをどうやって見つけるかです.このステップの考え方は次のとおりです.
(想像できないかもしれませんが、私は最大の共通のサブシーケンスを求めてC++コードを上げて午坑を踏んで、私の曹、本当に天坑です).まず考えを話しましょう.とても複雑です.まず、上の関数の中でpFlagの2次元配列を伝えます.これはポインタです.後で彼を再帰する必要があるからです.この2次元配列に格納されているサイズはmatrixと同じですが、この中に格納されているのは文字列です.理解しやすいように「left」,「up」,「left_up」と格納します.「ああ、三つの文字列ですが、実は自分でmatrixという表を描いたら、実はこのような矢印でこの長男のシーケンスが何なのかを遡ることができ、矢印が指す経路であることがわかります.それから、関数を再帰して、矢印に基づいて対応するサブシーケンスを見つけます.すべてのコードは以下の通りです.

#include 
#include 
using namespace std;
void sub_sequence(int i, int j, string **pFlag, string a) {
    if (i == 0 || j == 0) {
        return;
    }
    if (pFlag[i][j] == "left_up") {
        sub_sequence(i - 1, j - 1, pFlag, a);
        cout << a[i-1] << " ";
    } else {
        if (pFlag[i][j] == "left") {
            sub_sequence(i, j-1, pFlag, a);
        } else {
            sub_sequence(i-1, j, pFlag, a);
        }
    }
}

int lcs_length(string a, string b, string **pFlag) {
    // given 2 string, return the LCS length
    // define a 2 dim array
    int matrix[a.size()+1][b.size()+1];
    for (int i = 0; i <= a.size(); ++i) {
        matrix[i][0] = 0;
    }
    for (int j = 0; j <= b.size(); ++j) {
        matrix[0][j] = 0;
    }
    for(int i = 1; i <= a.size(); i++) {
        for(int j = 1; j <= b.size(); j++) {
            if (a[i-1] == b[j-1]) {
                matrix[i][j] = matrix[i-1][j-1] + 1;
                // using string to indicate location
                pFlag[i][j] = "left_up";
            } else {
                if (matrix[i][j-1] > matrix[i-1][j]) {
                    matrix[i][j] = matrix[i][j-1];
                    pFlag[i][j] = "left";
                } else {
                    matrix[i][j] = matrix[i-1][j];
                    pFlag[i][j] = "up";
                }
            }
        }
    }
    return matrix[a.size()][b.size()];
}

int main()
{
    string b = "gheteuponthiop";
    string a = "giothuphyo";
    //      **pFlag, markdown     ，    
    auto ** pFlag = new string* [a.size() + 1];
    for (int k = 0; k <= a.size(); ++k) {
        pFlag[k] = new string[b.size() + 1];
    }
    int l = lcs_length(a, b, pFlag);
    sub_sequence((int) a.size(), (int) b.size(), pFlag, a);
    cout << endl;
    cout << l << endl;
    return 0;
}

仕事が終わる!后で最大の公共のサブシーケンスの问题を求めて私のブログに来ます!!!
ここまで書いてみるとそんなに面白くない.複雑ですね...しかし、その言葉を信じて、万変はその宗から離れない.