什么是“剪切粘贴"?证明技术? [英] What is the "cut-and-paste" proof technique?

问题描述

在某些有关算法分析和设计的文章中，我已经看到了对剪切粘贴证明的引用.当为优化问题证明最优子结构时，通常会在动态编程的上下文中提到它(请参见第15.3章CLRS).它还显示在图形操作上.

I've seen references to cut-and-paste proofs in certain texts on algorithms analysis and design. It is often mentioned within the context of Dynamic Programming when proving optimal substructure for an optimization problem (See Chapter 15.3 CLRS). It also shows up on graphs manipulation.

此类证明的主要思想是什么?我该如何使用它们来证明算法的正确性或特定方法的便利性?

What is the main idea of such proofs? How do I go about using them to prove the correctness of an algorithm or the convenience of a particular approach?

推荐答案

在进行动态编程时，剪切和粘贴"一词有时会出现在算法中(还有其他事情，但这是我第一次看到的地方).这个想法是，为了使用动态编程，您尝试解决的问题可能具有某种潜在的冗余.您使用表或类似技术来避免一遍又一遍地解决相同的优化问题.当然，在开始尝试使用动态编程之前，很高兴证明问题具有此冗余，否则，使用表将不会有任何好处.这通常称为最佳子问题"属性(例如，在CLRS中).

The term "cut and paste" shows up in algorithms sometimes when doing dynamic programming (and other things too, but that is where I first saw it). The idea is that in order to use dynamic programming, the problem you are trying to solve probably has some kind of underlying redundancy. You use a table or similar technique to avoid solving the same optimization problems over and over again. Of course, before you start trying to use dynamic programming, it would be nice to prove that the problem has this redundancy in it, otherwise you won't gain anything by using a table. This is often called the "optimal subproblem" property (e.g., in CLRS).

剪切和粘贴"技术是一种证明问题具有此属性的方法.特别是，您想表明，当您提出问题的最佳解决方案时，您必须对组成子问题使用了最佳解决方案.证明是矛盾的.假设您通过对子问题使用次优的解决方案来为问题提供了最佳的解决方案.然后，如果要用最佳子问题解决方案替换(剪切")那些次优子问题解决方案(通过粘贴"它们)，则可以改进您的最佳解决方案.但是，由于您的解决方案在假设条件下是最佳的，因此您有一个矛盾.这种证明还涉及其他一些步骤，但这就是剪切和粘贴"部分.

The "cut and paste" technique is a way to prove that a problem has this property. In particular, you want to show that when you come up with an optimal solution to a problem, you have necessarily used optimal solutions to the constituent subproblems. The proof is by contradiction. Suppose you came up with an optimal solution to a problem by using suboptimal solutions to subproblems. Then, if you were to replace ("cut") those suboptimal subproblem solutions with optimal subproblem solutions (by "pasting" them in), you would improve your optimal solution. But, since your solution was optimal by assumption, you have a contradiction. There are some other steps involved in such a proof, but that is the "cut and paste" part.

这篇关于什么是“剪切粘贴"?证明技术?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！