algorithm => 最長増加サブシーケンス

最長増加サブシーケンス基本情報

最長増加サブシーケンス問題は、サブシーケンスの要素が最下位から最上位にソートされている入力シーケンスからサブシーケンスを見つけることです。すべてのサブシーケンスは、連続していなくても一意ではありません。

最長増加サブシーケンスの適用：

Longest Increasing Subsequence、Longest Common Subsequenceなどのアルゴリズムは、Gitなどのバージョン管理システムで使用されます。

シンプルなアルゴリズム：

両方の文書に共通する一意の行を見つけます。
最初の書類からそのような行をすべて取り出し、2番目の書類に出てくるように指示します。
得られたシーケンスのLISを（忍耐ソートを行うことによって）計算し、最も長いマッチする系列のシーケンスを得る。これは2つの文書のライン間の対応である。
すでに一致している行の各行の範囲でアルゴリズムを再帰します。

次に、LCS問題のより簡単な例を考えてみましょう。ここで、入力は、異なる整数a1,a2,...,an. 1つのシーケンスのみa1,a2,...,an.私たちはその中で最も長い部分配列を見つけたいと思っています。たとえば、入力が7,3,8,4,2,6の場合、最も長くなるサブシーケンスは3,4,6です。

最も簡単なアプローチは、入力要素を昇順でソートし、元の列とソートされた列にLCSアルゴリズムを適用することです。しかし、結果の配列を見ると、多くの値が同じであり、配列は非常に繰り返し見えます。これは、LIS（最長増加サブシーケンス）問題は、1次元アレイのみを使用する動的プログラミングアルゴリズムで行うことができることを示唆している。

擬似コード：

計算したい値の配列を記述する。
1 <= i <= n 、入力の最長増加シーケンスの長さをA（i）とする。最終的に私たちが興味を持っている長さはmax{A(i)|1 ≤ i ≤ n}です。
再発する。
1 <= i <= n 、 A(i) = 1 + max{A(j)|1 ≤ j < iかつinput(j) < input(i)}.
A.の値を計算する
最適な解を見つけてください。

次のプログラムはAを使用して最適解を計算します。第1の部分は、 A（m）が入力の最適な増加するサブシーケンスの長さであるような値mを計算する。 2番目の部分は、最適な増加部分列を計算しますが、便宜上、逆順に出力します。このプログラムは時間O（n）で実行されるので、アルゴリズム全体が時刻O（n ^ 2）で実行されます。

パート1：

m ← 1 
for i : 2..n 
    if A(i) > A(m) then 
        m ← i 
    end if 
end for

パート2：

put a
while A(m) > 1 do 
    i ← m−1 
    while not(ai < am and A(i) = A(m)−1) do 
        i ← i−1 
    end while 
    m ← i 
    put a
 end while

再帰的解決策：

アプローチ1：

LIS(A[1..n]):
    if (n = 0) then return 0
    m = LIS(A[1..(n − 1)])
    B is subsequence of A[1..(n − 1)] with only elements less than a[n]
    (* let h be size of B, h ≤ n-1 *)
    m = max(m, 1 + LIS(B[1..h]))
    Output m

アプローチ1の時間複雑さ： O(n*2^n)

アプローチ2：

LIS(A[1..n], x):
    if (n = 0) then return 0
    m = LIS(A[1..(n − 1)], x)
    if (A[n] < x) then
        m = max(m, 1 + LIS(A[1..(n − 1)], A[n]))
    Output m

MAIN(A[1..n]):
    return LIS(A[1..n], ∞)

アプローチ2の時間複雑度： O(n^2)

アプローチ3：

LIS(A[1..n]):
    if (n = 0) return 0
    m = 1
    for i = 1 to n − 1 do
        if (A[i] < A[n]) then
            m = max(m, 1 + LIS(A[1..i]))
    return m

MAIN(A[1..n]):
    return LIS(A[1..i])

アプローチ3の時間複雑度： O(n^2)

反復アルゴリズム：

値をボトムアップで繰り返し計算します。

LIS(A[1..n]):
    Array L[1..n]
    (* L[i] = value of LIS ending(A[1..i]) *)
    for i = 1 to n do
        L[i] = 1
        for j = 1 to i − 1 do
            if (A[j] < A[i]) do
                L[i] = max(L[i], 1 + L[j])
    return L

MAIN(A[1..n]):
    L = LIS(A[1..n])
        return the maximum value in L

繰り返しアプローチにおける時間の複雑さ： O(n^2)

補助空間： O(n)

入力として{ 0、8、4、12、2、10、6、14,1,9,5,13,3,11,7,15 }を取ります。したがって、与えられた入力の最長増加サブシーケンスは{0,2,6,9,5,15}です。

C＃の実装

public class LongestIncreasingSubsequence
{
    private static int Lis(int[] input, int n)
    {
        int[] lis = new int[n];
        int max = 0;
        for(int i = 0; i < n; i++)
        {
            lis[i] = 1;
        }
        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (input[i] > input[j] && lis[i] < lis[j] + 1)
                    lis[i] = lis[j] + 1;
            }
        }
        for (int i = 0; i < n; i++)
        {
            if (max < lis[i])
                max = lis[i];
        }
        return max;
    }

    public static int Main(int[] input)
    {
        int n = input.Length;
        return Lis(input, n);
    }
}

Modified text is an extract of the original Stack Overflow Documentation

ライセンスを受けた CC BY-SA 3.0

所属していない Stack Overflow

algorithm
最長増加サブシーケンス

サーチ…

最長増加サブシーケンス基本情報

C＃の実装