algorithm - 证明动态规划方法对最小编辑距离的正确性

Question

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

关于编辑距离，这个算法的描述在互联网上随处可见，但都只是在没有证明的情况下断言其正确性。根据编辑距离的定义，您可以在中间插入、删除或替换字符，而不仅仅是在末尾。那你怎么证明这个递推关系真的成立呢？

Answer 1

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

首先，正如我在评论中所说，您可以将动态规划视为加速递归的一种方式，证明递归算法正确的最简单方法几乎总是通过 induction : 证明它在一些小的基本情况下是正确的，然后证明，假设它对于大小为 n 的问题是正确的，那么它对于大小为 n+1 的问题也是正确的。通过这种方式，证明紧密地反射(reflect)了递归结构。

此问题的通常递归将问题“找到将字符串 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) and (i-2, j-1), etc., etc. 如何选择有效的基本情况？在遍历这棵树时，即从证明我们对子问题 (i, j) 的解决方案正确到证明我们对其任何一个“子”子问题 (i', j') 的解决方案是正确的，我们注意到:

i' < i 或 j' < j 中的至少一个成立。

我们从不“跳过”子问题——也就是说，我们从来没有 i-i' >= 2 或 j-j' >= 2。

基本上，如果我们沿着这棵树向下走一步，我们的两个“子问题坐标”(i 或 j)中的至少一个会减少，但不会超过 1。这意味着如果我们继续向下遍历这棵树，那么无论我们在下降的过程中选择了哪些特定的“子”子问题，我们最终都必须找到一个子问题，其(至少)一个坐标为 0——即一个 (i'', 0) 子问题一些 0 <= i'' <= |A|或者一个 (0, j'') 子问题对于一些 0 <= j'' <= |B|。这意味着如果我们将这些子问题作为我们的基本情况，我们可以确保归纳树中的每条路径都遇到一个基本情况，在该情况下，其假设得到满足，因此可以停止。

幸运的是，这些基本情况确实很容易计算出最佳答案。考虑一个问题 (i, 0):这个问题要求将字符串 A 的前 i 个字符更改为字符串 B 的前 0 个字符所需的最小成本。显然，最好的(唯一!)方法是删除所有A 的前缀中的 i 个字符，成本为 i。同样，问题 (0, j) 要求将 A 的前 0 个字符更改为 B 的前 j 个字符所需的最小成本:同样清楚，最好的方法是简单地在此前缀中插入所有 j 个字符B，成本为 j。

归纳步骤

剩下的就是归纳步骤:证明我们正确计算了 (i, j) 子问题的答案，假设我们已经计算了 (i-1, j), (i, j-1) 的答案和 (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 .. i-1]) 的最小可能成本。 .j])——假设，我们已经正确计算了!

插入 B[j]。这成本为 1，因此执行此操作的总成本必须是 1 加上将 A 的整个前缀 (A[1 .. i]) 编辑为 B 的其余前缀 (B[1 .. j) 的最小可能成本-1]) -- 根据假设，我们已经正确计算了!

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