2

我遇到了使用耐心排序来获得最长递增子序列 (LIS) 长度的解决方案。http://www-stat.stanford.edu/~cgates/PERSI/papers/Longest.pdf和这里 - http://en.wikipedia.org/wiki/Patience_sorting。

遵循贪心策略实际上给我们正确的长度的证明有两个部分 -

  1. 证明桩的数量至少等于 LIS 的长度。
  2. 证明使用贪心策略的堆数最多等于LIS。

因此，凭借 1) 和 2)，解决方案正确地给出了 LIS 的长度。

我得到了 1) 的解释，但我无法直观地实现第 2) 部分。有人可以使用不同的例子来说服我这确实是真的。或者，您甚至可以使用不同的证明技术。

4

1 回答 1

3

我刚刚阅读了论文，我同意证明有点，嗯，简洁。（我想说它缺少一些非常重要的步骤！）

直观地说，证明背后的想法是表明，如果您使用贪婪策略并在游戏结束时从一堆编号为 p 的牌中挑选任何一张牌，您可以在原始数组中找到一个长度为 p 的递增子序列。如果你能证明这个事实，那么你可以得出结论，贪心策略产生的最大堆数是最长递增子序列的长度。

为了正式证明这一点，我们将论证以下两个不变量在每一步都成立：

  1. 从左到右阅读时，每堆顶部的卡片按排序顺序排列。

  2. 在任何时间点，每一堆中的每张牌都是递增子序列的一部分，其长度由堆索引给出。

第 (1) 部分很容易从贪心策略中看出 - 每个元素都尽可能放在左侧，而不会违反小卡片必须始终放在大卡片顶部的规则。这意味着如果将一张卡片放入堆 p 中，我们实际上是在采用排序序列并将第 p 个元素的值减少到大于位置 p - 1 中的任何值（如果存在）的值。

要查看第 (2) 部分，我们将进行归纳。第一张放置的卡片被放入堆 1，它也是长度为 1 的递增子序列的一部分（卡片本身）。对于归纳步​​骤，假设在放置 n 张卡片后该属性成立并考虑第 (n+1) 个。假设它最终在堆 p 中。如果 p = 1，那么这个主张仍然成立，因为这张牌本身就形成了一个长度为 1 的递增子序列。否则，p > 1。现在，看看堆顶上的牌 p - 1。我们知道这张牌的价值小于我们刚刚放置的牌的价值，否则我们会将牌放在上面桩。我们还知道，那堆牌顶部的牌在我们刚刚按原始顺序放置的牌之前，因为我们是按顺序打牌的。通过我们现有的不变量，

于 2015-08-27T20:53:22.060 回答