What is the “cut-and-paste” proof technique?

问题:

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?

回答1:

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.

回答2:

Cut-and-Paste is a way used in proofing graph theory concepts, Idea is this: Assume you have solution for Problem A, you want to say some edge/node, should be available in solution. You will assume you have solution without specified edge/node, you try to reconstruct a solution by cutting an edge/node and pasting specified edge/node and say new solution benefit is at least as same as previous solution.

One of a most important samples is proving MST attributes (proving that greedy choice is good enough). see presentation on MST from CLRS book.

回答3:

Proof by contradiction

P is assumed to be false, that is !P is true.

It is shown that !P implies two mutually contradictory assertions, Q and !Q.

Since Q and !Q cannot both be true, the assumption that P is false must be wrong, and P must be true.

回答4:

'cut-and-paste' technique can be used in proving both correctness of greedy algorithm (both optimal structure and greedy-choice property' and dynamic programming algorithm correctness.

Greedy Correctness

This lecture notes Correctness of MST from MIT 2005 undergrad algorithm class exhibits 'cut-and-paste' technique to prove both optimal structure and greedy-choice property.

This lecture notes Correctness of MST from MIT 6.046J / 18.410J spring 2015 use 'cut-and-paste' technique to prove greedy-choice property

Dynamic Programming Correctness

A more authentic explanation for 'cut-and-paste' was introduced in CLRS (3rd edtion) Chapter 15.3 Element of dynamic programming at page 379

"4. You show that the solutions to the subproblems used within the optimal solution to the problem must themselves be optimal by using a “cut-and-paste” technique, You do so by supposing that each of the subproblem solutions is not optimal and then deriving a contradiction. In particular, by “cutting out” the nonoptimal subproblem solution and “pasting in” the optimal one, you show that you can get a better solution to the original problem, thus contradicting your supposition that you already had an optimal solution. If there is more than one subproblem, they are typically so similar that the cut-and-paste argument for one can be modified for the others with little effort."