最小编辑距离的动态编程方法的正确性证明

Question

为了计算最小编辑距离（将一个单词转换为另一个单词所需的最小插入，删除和替换量），一种动态编程解决方案基于递归关系，在该关系中将检查两个字符串的最后一个字符。详细信息在https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm中。

关于编辑距离，该算法的描述在Internet上无处不在，但是所有这些都只是断言其正确性而没有证据。通过定义编辑距离，您可以在中间而不是仅在末尾插入，删除或替换字符。那么如何证明这种递归关系确实成立？

Answer 1

使用归纳证明递归算法正确

首先，正如我在评论中所说，您可以将动态编程视为加快递归的一种方式，证明递归算法正确的最简单方法几乎总是通过归纳法：证明在某些小基本情况下它是正确的，然后表明，假设对于大小为n的问题是正确的，那么对于大小为n + 1的问题也是正确的。这样，证明就紧密地反映了递归结构。

此问题的通常递归将问题“找到将字符串A编辑为字符串B的最小开销”分解为（| A | +1）（| B | +1）子问题“查找最小字符以编辑前i个字符”将字符串A转换为字符串B的前j个字符”，对于所有0 <= i <= | A | 和0 <= j <= | B |。

选择基本案例

通常，通过归纳法，我们可以选择少量简单的基本案例（也许只是一个），表明我们可以轻松地为它们计算出正确的答案，很明显，其他所有案例的正确性将如何隐含着基本案例，因为无论我们从哪种案例开始，都将只有一个需要满足的假设“链”，并且该链显然必须以我们的一个基本案例结束。但是，对于这个特定问题，为了表明算法能够最佳地解决（i，j）子问题，我们需要首先假定它解决了（i-1，j），（i，j-1）和（i-1 ，j-1）子问题的最优选择（因为如果这些子问题的答案中的任何一个都不正确，它就很容易为（i，j）子问题计算出完全错误的答案）。这将需要比平常更为复杂的归纳：我们现在有了一个分支的假设“树”，而不是一个需要满足的假设“链”，每个点有（最多）3个子代。我们需要选择基本案例，以便对于任何（i，j），整个假设树最终都会“停止”，即，其中的每条路径最终都会达到满足其假设的基本情况。

概述：为了证明我们对（i，j）最优的解，我们必须假设我们对（i-1，j），（i，j-1）和（i-1，j-1）具有最优解；为了满足（i-1，j）的假设（即证明我们对（i-1，j）的解是最优的），我们需要假设对（i-2，j）有最优解），（i-1，j-1）和（i-2，j-1）等，等等。如何选择可以使用的基本案例？在遍历这棵树时，即从证明我们的解决方案对子问题（i，j）正确到证明我们对任何子问题（i'，j'）正确的解决方案，我们注意到：

1. i'<i或j'<j中的至少一个成立。
2. 我们永远不会“跳过”子问题-也就是说，我们永远不会有ii'> = 2或jj'> = 2。

基本上，如果我们沿这棵树下移一步，则两个“子问题坐标”（i或j）中的至少一个会减少，但不会减少超过1。这意味着，如果我们继续沿树下移，那么无论我们在接下来的过程中选择哪个特定的“子”子问题，我们最终都必须针对（至少）其一个坐标找到0的子问题，即针对（i''，0）的子问题大约0 <= i''<= | A | 或某个（0，j''）子问题对应一些0 <= j''<= | B |。这就意味着，如果我们将这些子问题作为基本案例，我们可以确保归纳树中的每条路径都符合一个基本案例，在该基本案例中其假设得到满足，因此可以停止。

幸运的是，这些基本案例确实很容易计算出最佳答案。考虑一个问题（i，0）：此问题要求将字符串A的第一个i字符更改为字符串B的前0个字符所需的最低成本。显然，最好的（唯一的！）方法是删除所有i的前缀为A，费用为i。同样，问题（0，j）要求将A的前0个字符更改为B的前j个字符所需的最低成本：同样，最好的方法是在该前缀中插入所有j个字符B的成本为j。

归纳步

剩下的只是归纳步骤：假设我们已经计算了（i-1，j），（i，j-1）的答案，表明我们正确计算了（i，j）子问题的答案。和（i-1，j-1）子问题正确。诀窍是要看到，以各种可能的方式将A的前i个字符编辑为B的前j个字符，实际上，我们可以使用这些前缀中的最后一个字符进行3种可能的操作（即， A中的第i个字符和B中的第j个字符）：

• 将A [i]与B [j]配对。它们要么匹配（成本0），要么不匹配（成本1），但是无论哪种方式，该配对的总成本必须是该成本（0或1），再加上编辑A的其余前缀的最小成本（ A [1 .. i-1]）放入B 的其余前缀（B [1 .. j-1]）-根据假设，我们已经正确计算了！
• 删除A [i]。这个成本1，所以这样做的总成本必须是1加上编辑的最小可能成本休息 A的前缀（A [1 ... I-1]）到整个 B的前缀（B [1。 。j]）-根据假设，我们已经正确计算了！
• 插入B [j]。该成本为1，因此执行此操作的总成本必须为1加上将A 的整个前缀（A [1..i]）编辑为B 的其余部分（B [1..j ] 的最小可能成本。 -1]）-根据假设，我们已经正确计算了！

由于这3件事是我们唯一可能做的事情，并且对于这3件事中的每一个，我们都已计算出执行此事情的总体最低成本，因此，总体上最好的事情必须是其中3件事中最好的。这证明对于任何 i和j ，我们都正确地计算了将A的第一个i字符编辑为B的前j个字符所需的最低成本–因此，对于i = | A |尤其如此 j = | B |，即用于将完整字符串A编辑为完整字符串B。