CLRS の INTRODUCTION TO ALGORITHMS で最も長い一般的なサブ シーケンスの問題を経験していましたが、その背後にある思考プロセスを理解できませんでした。説明された他のほとんどの問題は非常に直感的で、将来同様の問題を解決できると確信していますが、最適な部分構造がどのように決定されるかの背後にあるロジックを理解していないため、LCS 問題を視覚化することはできません。
この本は、最適なサブ構造について次の説明を提供します
**定理 15.1 (LCS の最適部分構造)
X == と Y == をシーケンスとし、Z = を X と Y の任意のxm = ynLCSとする。2. If ,thenは、との LCS であることを意味します。3. If ,thenは、との LCS であることを意味します。証明 (1) の場合、 に追加して長さの共通部分列を得ることができ、との最長共通部分列であるという仮定に反します。したがって、 が必要です。zk = xm = ynZk−1Xm−1Yn−1xm != ynzk = xmZXm−1Yxm != ynzk = ynZXYn−1zk != xmxm = ynZXYk + 1ZXYzk = xm = yn
さて、接頭辞Zk−1は と の共通length-(k − 1)部分列です。それが LCS であることを示したいと思います。矛盾の目的のために、 と の長さが より大きい共通部分列があると仮定します。次に、 に追加すると
、長さが より大きいandの共通部分列が生成されますが、これは矛盾しています。Xm−1Yn−1WXm−1Yn−1k−1xm = ynWXYk
(2) もしzk != xm,thenZが と の共通部分列でXm−1あるY. と
の LCS であるという仮定に反して、長さが より大きいとの共通部分列があった場合W、もと の共通部分列になります。Xm−1YkWXmYZXY
(3) 証明は (2) と対称です。**
証明は明らかですが、彼らがどのようにして最適な部分構造を思いついたのかわかりません。誰か助けてくれませんか？