什麼是切割和粘貼證明？

Question

我曾見過參考在某些算法文本中剪切和粘貼證明。這種證明的主要思想是什麼？我如何去用它們來證明一些東西？

Answer 1

術語「剪切和粘貼」顯示，在做動態規劃有時當算法（以及其他的一些東西，但是這是我第一次看到它）。這個想法是，爲了使用動態編程，你試圖解決的問題可能有某種潛在的冗餘。您使用表格或類似的技術來避免一遍又一遍地解決相同的優化問題。當然，在開始嘗試使用動態編程之前，最好能夠證明問題存在這種冗餘，否則使用表格就無法獲得任何收益。這通常被稱爲「最優子問題」屬性（例如，在CLRS中）。

「剪切和粘貼」技術是一種證明問題具有此屬性的方法。特別是，你想表明，當你提出一個問題的最佳解決方案時，你必須使用最優解來解決組成子問題。證明是矛盾的。假設您通過對子問題使用次最佳解決方案來提出問題的最佳解決方案。那麼，如果您要用最佳子問題解決方案（通過「粘貼」）來替代（「削減」）這些次優子問題解決方案，則可以改進您的最優解決方案。但是，由於你的解決方案是假設的最佳選擇，所以你有矛盾。這樣的證明還涉及其他一些步驟，但這是「剪切和粘貼」部分。

Answer 2

剪切和粘貼在打樣圖論概念使用的辦法，思路是這樣的：假設你有解決的問題的，你想說些邊緣/節點，應該是解決方案。你會假設你沒有指定邊緣/節點的解決方案，你試圖通過削減邊緣/節點並粘貼指定的邊緣/節點來重建解決方案，並說新的解決方案的好處至少與以前的解決方案相同。

一個最重要的樣本被證明是MST屬性（證明貪婪的選擇是不夠好）。見presentation on MST from CLRS book。

Answer 3

「剪切和粘貼」可以在證明貪婪算法的兩個正確性（包括最佳結構和貪婪選屬性」和動態編程算法的正確性來使用的技術。

貪婪正確性

本講座從2005年麻省理工學院本科算法類展品剪切和粘貼「技術注意到Correctness of MST證明既最佳結構和貪婪-選擇屬性。

本講座從MIT 6.046J/18.410J彈簧2015使用注意到Correctness of MST「剪切和-paste'技術來證明gr eedy選屬性

動態規劃的正確性

一種「剪切和粘貼」更真實的解釋是在CLRS（3 edtion）章動態規劃的15.3元在頁面推出379

「4 。你表明，在問題的最優解決方案中使用的子問題的解決方案本身必須通過使用「剪切和粘貼」技術來達到最佳效果，假設每個子問題解決方案都不是最優的，然後推導出矛盾。特別是，通過「切斷」非最優子問題解決方案並「粘貼」最優解決方案，表明您可以更好地解決原始問題，從而與您的假設相矛盾，即您已經有了最佳解決方案。如果存在多個子問題，那麼它們通常非常相似，以至於可以毫不費力地爲其他人修改剪切粘貼參數。「

Answer 4

反證法

P被假定是假的，那就是！P爲真。

結果表明，P！意味着兩個相互矛盾的說法，Q和q！。

由於Q和q！不能同時爲真，假設P是假的一定是錯的，而P必須是真實的。