最も長くなるサブシステムのアプリケーション

Question

他のCSの問題に取り組んでいるときにLIS（Longest Increasing Subsequence）の問題がどれくらい役に立ちますか？忍耐ソート、動的プログラミング、または意思決定ツリーを使用して、いくつかのアルゴリズムがあります。これらは実生活でどのように使用されていますか？おそらくデータストリームなどに使われていますか？

はあなたを思い出させるために、私は、太字で最長の増加シーケンス

{、8、4、12、置く2、10、、14、1、、5 、13,3、,7,}である。

ボーナスとして、a sequence of length mn + 1 will have an increasing subsequence of length m or a decreasing subsequence of length nの結果を使用する方法はありますか？例えば。私たちのリストは長さ16であるので、長さ5のシーケンスが増加するか、長さ5のシーケンスが減少するはずです。0,2,6,9,11,15。

長さ8の増加する配列または長さ3の減少する配列：この場合、12,10,1。

Answer 1

LISの興味深い実際のアプリケーションは、Bazaarバージョン管理システムで使用されているBram Cohen（BitTorrentの作成者）によるPatience Diff、diffingアルゴリズムです。

通常のdiffアルゴリズムでは、2つのドキュメントの間にLCS（Longest Common Subsequence）を計算します。効率的である一方、このアプローチには問題があります。結果はしばしば人にやさしくないことがよくあります。

正規diffが失敗する可能性がどのように簡単な例：

void func1() { 
    x += 1 
+} 
+ 
+void functhreehalves() { 
+ x += 1.5 
} 

void func2() { 
    x += 2 
} 

忍耐差分アルゴリズムの利点は、より密接にどのように人間に対応するようにして、より正確な違いを計算することができることである

実行するだろう。前のケースの忍耐差分で

は違い、より良いスポット：

void func1() { 
    x += 1 
} 

+void functhreehalves() { 
+ x += 1.5 
+} 
+ 
void func2() { 
    x += 2 
} 

を一言で言えば、アルゴリズムは次のとおりです。

1. は、両方の文書に共通するユニークな行を検索します。
2. このような行をすべて最初のドキュメントから取り出し、2番目のドキュメントの外観に従って並べます。
3. 結果シーケンスのLIS（Patience Sortを実行）を計算して、最も長い一致する行のシーケンスを取得します。これは、2つのドキュメントの行間の対応です。
4. すでに一致している行の各行の範囲でアルゴリズムを再帰的に実行します。

the codeをご覧ください。