我在一些算法分析和设计的文本中看到过关于“剪切粘贴”证明的参考。通常在证明一个优化问题的最优子结构时(见第15.3章CLRS),它会在动态规划的上下文中被提及。它也出现在图形操作中。
这样的证明的主要思想是什么?我该如何运用它们来证明算法的正确性或特定方法的方便性?
我在一些算法分析和设计的文本中看到过关于“剪切粘贴”证明的参考。通常在证明一个优化问题的最优子结构时(见第15.3章CLRS),它会在动态规划的上下文中被提及。它也出现在图形操作中。
这样的证明的主要思想是什么?我该如何运用它们来证明算法的正确性或特定方法的方便性?
MIT 2005年本科算法课程的讲义 MST的正确性展示了“剪切和粘贴”技术,以证明最优结构和贪心选择性质。
MIT 6.046J / 18.410J 2015年春季学期的讲义 MST的正确性使用“剪切和粘贴”技术来证明贪心选择性质。
CLRS(第3版)第15.3章《动态规划元素》第379页介绍了更真实的“剪切和粘贴”解释。
"4. 通过使用“剪切和粘贴”的技术,您表明用于问题的最优解中所使用的子问题的解决方案本身必须是最优的。为此,假设每个子问题的解决方案都不是最优的,然后得出矛盾。特别地,通过“剪切”非最优子问题的解决方案并“粘贴”最优的解决方案,您可以获得更好的原始问题解决方案,从而与您已经具有最优解的假设相矛盾。如果存在多个子问题,则它们通常非常相似,可以轻松修改一个子问题的剪切和粘贴论证以适用于其他子问题。"反证法
假设P是错误的,即!P是正确的。
证明!P意味着两个互相矛盾的断言Q和!Q。
由于Q和!Q不能同时成立,因此假设P是错误的是错误的,P必须是正确的。
这并不是一种全新的证明技巧。它只是一种用反证法来阐述证明的有趣方式。
一个剪切和粘贴的例子:
假设你正在解图中从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。
所以,“剪切”和“粘贴”使得它更加直观和易于解释。