algorithm - 最長増加部分列の適用

Question

LIS (最長増加部分列) 問題は、他の CS 問題に取り組む上でどの程度役立ちますか? いくつかのアルゴリズムがあり、忍耐ソート、動的計画法、または決定木を使用しています。これらは実生活でどのように使用されていますか? データストリームなどに使用されているのでしょうか?

思い出していただくために、最長の増加シーケンスを太字で示しました

{ 0、8、4、12、2、10、6、14、1、9、5、13、3、11、7、15 }。_ _ _ _ _ _ _ _ _

おまけとして、長さ mn + 1 のシーケンスが長さ m の増加するサブシーケンスまたは長さ n の減少するサブシーケンスを持つという結果を使用する方法はありますか? たとえば、長さ 16 のリストなので、長さ 5 の増加シーケンスまたは長さ 5 の減少シーケンスが存在するはずです。この場合、0,2,6,9,11,15 .

また、長さ 8 の増加するシーケンスまたは長さ 3 の減少するシーケンス: この場合は12,10,1です。

score 12 · Accepted Answer

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

通常の diff アルゴリズムには、2 つのドキュメント間の LCS ( Longest Common Subsequence ) の計算が含まれます。このアプローチは効率的ですが、問題があります。つまり、結果がたまたま人間に優しくないことがよくあります。

通常の diff が失敗する可能性がある簡単な例:

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

 void func2() {
     x += 2
 }

Patience Diff アルゴリズムの利点は、人間のパフォーマンスにより近い方法で、違いをより正確に計算できることです。

前のケースでは、Patience Diff は違いをよりよく見つけます。

 void func1() {
     x += 1
 }

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

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

コードを見てください。

1 に答える 1