忍耐ソートを使用して最長増加部分列 (LIS) の長さを取得するソリューションに出くわしました。http://www-stat.stanford.edu/~cgates/PERSI/papers/Longest.pdf、およびここ - http://en.wikipedia.org/wiki/Patience_sorting。
貪欲な戦略に従うと、実際に正しい長さが得られるという証明には、2 つの部分があります。
したがって、1) と 2) の両方のおかげで、解は LIS の長さを正しく与えます。
1)の説明はわかるが、2)は直感的に理解できない。誰かが別の例を使用して、これが実際に真実であることを私に納得させることができますか. または、別の証明手法を使用することもできます。
私はその論文を読み返しましたが、証明が少し、ええと、簡潔であることに同意します。（かなり重要なステップがいくつか欠けていると思います！）
直観的に言えば、この証明の背後にあるアイデアは、貪欲な戦略でプレイし、ゲームの最後に p の番号の山から任意のカードを選ぶと、元の配列で長さが p の増加する部分列を見つけることができることを示すことです。この事実を証明できれば、貪欲な戦略によって生成されるパイルの最大数は、最も長く増加するサブシーケンスの長さであると結論付けることができます。
これを正式に証明するために、次の 2 つの不変条件が各ステップで成り立つことを主張します。
左から右に読んだとき、各山の一番上のカードはソートされた順序になっています。
任意の時点で、すべてのパイルのすべてのカードは、パイル インデックスで指定された長さの増加するサブシーケンスの一部です。
パート (1) は貪欲な戦略から簡単にわかります。小さなカードは常に大きなカードの上に置かなければならないという規則に違反することなく、すべての要素をできるだけ左側に配置します。これは、カードがパイル p に置かれた場合、効果的にソートされたシーケンスを取得し、p 番目の要素の値を位置 p - 1 (存在する場合) よりも大きい値に減らすことを意味します。
パート (2) を見るために、帰納的に行きます。最初に置かれたカードはパイル 1 に置かれ、長さ 1 の増加するサブシーケンスの一部でもあります (カード自体)。誘導ステップでは、n枚のカードを配置した後、このプロパティが保持されていると仮定し、(n + 1)番目を考えます。それがパイル p になったとします。p = 1 の場合、このカードはそれ自体で長さ 1 の増加するサブシーケンスを形成するため、主張は依然として成立します。それ以外の場合、p > 1. 次に、パイル p - 1 の一番上にあるカードを見てください。このカードの値は、配置したばかりのカードの値よりも小さいことがわかっています。パイル。また、カードを順番にプレイしているため、その山の上にあるカードが元の順序で配置したカードよりも前にあることもわかっています。既存の不変式により、