“剪切粘贴”证明技术是什么？

Question

我在一些算法分析和设计的文本中看到过关于“剪切粘贴”证明的参考。通常在证明一个优化问题的最优子结构时（见第15.3章CLRS），它会在动态规划的上下文中被提及。它也出现在图形操作中。

这样的证明的主要思想是什么？我该如何运用它们来证明算法的正确性或特定方法的方便性？

- hari_sree

---

我不明白为什么这不是一个真正的问题。我在算法文本中多次遇到过剪切粘贴证明。为什么这个问题会变成“模糊不清，含糊不清，不完整，过于宽泛或修辞，并且不能被合理地回答”？ @Cameron甚至对动态规划中这种证明的实质给出了很好的解释。 - hari_sree

Answer 1

术语“剪切和粘贴”有时在动态规划（以及其他一些地方）中出现。其想法是，为了使用动态规划，您正在尝试解决的问题可能具有某种基础冗余性。您使用表格或类似技术来避免重复解决相同的优化问题。当然，在开始尝试使用动态规划之前，最好证明该问题具有这种冗余性，否则使用表格不会有任何好处。这通常称为“最优子问题”属性（例如，在CLRS中）。

“剪切和粘贴”技术是证明问题具有此属性的一种方法。特别地，您要展示当您想出一个问题的最优解时，您必须使用最优的子问题解。该证明采用反证法。假设您通过使用子问题的次优解想出了一个问题的最优解。然后，如果您用最优的子问题解（通过“粘贴”它们）替换（“剪切”）那些次优的子问题解，您将改善最优解。但是，由于您的解决方案是根据假设的最优解，因此您将产生矛盾。这样的证明还涉及其他几个步骤，但这就是“剪切和粘贴”的部分。

- Cameron

Answer 2

'剪切和粘贴'技术可用于证明贪心算法（最优结构和贪心选择性质）和动态规划算法的正确性。

贪心算法正确性

MIT 2005年本科算法课程的讲义 MST的正确性展示了“剪切和粘贴”技术，以证明最优结构和贪心选择性质。

MIT 6.046J / 18.410J 2015年春季学期的讲义 MST的正确性使用“剪切和粘贴”技术来证明贪心选择性质。

动态规划正确性

CLRS（第3版）第15.3章《动态规划元素》第379页介绍了更真实的“剪切和粘贴”解释。

"4. 通过使用“剪切和粘贴”的技术，您表明用于问题的最优解中所使用的子问题的解决方案本身必须是最优的。为此，假设每个子问题的解决方案都不是最优的，然后得出矛盾。特别地，通过“剪切”非最优子问题的解决方案并“粘贴”最优的解决方案，您可以获得更好的原始问题解决方案，从而与您已经具有最优解的假设相矛盾。如果存在多个子问题，则它们通常非常相似，可以轻松修改一个子问题的剪切和粘贴论证以适用于其他子问题。"

- Robert.Li

Answer 3

反证法

假设P是错误的，即!P是正确的。

证明!P意味着两个互相矛盾的断言Q和!Q。

由于Q和!Q不能同时成立，因此假设P是错误的是错误的，P必须是正确的。

- Ruling.K

Answer 4

剪切粘贴是证明图论概念的一种方法，其思想是：假设您已经解决了问题A，您想说某个边/节点应该在解决方案中可用。您将假设没有指定的边/节点的解决方案，然后通过剪切边/节点并粘贴指定的边/节点来重构解决方案，并说新解决方案的收益至少与以前的解决方案相同。

其中一个最重要的示例是证明MST属性（证明贪心选择足够好）。请参见 CLRS书中关于MST的演示。

- Saeed Amiri

Answer 5

这并不是一种全新的证明技巧。它只是一种用反证法来阐述证明的有趣方式。

一个剪切和粘贴的例子：

假设你正在解图中从x_1到x_n的最短路径问题。假设你找到了一条从x_1到x_n的最短路径，并且它经过了x_i和x_j（按顺序）。显然，从x_i到x_j的子路径也必须是x_i和x_j之间的最短路径。为什么呢？因为数学就是这样。

使用剪切和粘贴的证明方法： 假设存在一条从x_i到x_j更短的路径。将该路径“剪切”，然后“粘贴”到从x_1到x_n的整体路径中。然后，你将得到另一条从x_1到x_n的路径，它比先前已知路径（严格）更短，并且与该路径的“最短”性质相矛盾。

普通的反证法证明： 假设P：从x_1到x_n的给定路径是最短路径。 Q：从x_i到x_j的子路径是最短路径。 那么，非Q => 非P（根据上面提出的论证）。 因此，P => Q。

所以，“剪切”和“粘贴”使得它更加直观和易于解释。

- Amrinder Arora