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 的一个有趣的实际应用是 Patience Diff，这是Bram Cohen （BitTorrent 的创建者）的一种差异算法，用于Bazaar版本控制系统。

常规差异算法涉及计算两个文档之间的 LCS（最长公共子序列）。虽然效率很高，但这种方法有一个问题，那就是——结果经常碰巧对人类不太友好。

常规差异如何失败的简单示例：

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

 void func2() {
     x += 2
 }

Patience Diff 算法的优势在于它可以更准确地计算差异，以更接近于人类行为方式的方式计算。

在前面的案例中，耐心差异更好地发现了差异：

 void func1() {
     x += 1
 }

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

简而言之，算法是：

看看代码。

1 回答 1