Myers 的差异：为什么 V[k − 1] < V[k + 1] 保证选择更远的 D 路径？
Myers' diff: Why V[k − 1] < V[k + 1] guarantee to choose the further D-path?
如论文中的伪代码
4. If k = −D or k ≠ D and V[k − 1] < V[k + 1] Then
5. x ← V[k + 1]
6. Else
7. x ← V[k − 1]+1
8. y ← x − k
第 4 行表示如果 k 不是 -D 或 D，则取 x 较大的那个，然后找出蛇。这让我很困惑，难道我不应该同时计算 v[k-1] 和 v[k+1] 并找出哪条路径更远吗？如果我选择 x 较大的那个作为起点，结果我们的点会导致更远的路径怎么办？
此外，据此：
Namely, take the further reaching of (x’,y’+1) and (x"+1,y") in
diagonal k and then follow diagonal edges until it is no longer
possible to do so or until the boundary of the edit graph is reached.
我认为作者建议 (x',y'+1) 和 (x"+1,y")（在这种情况下，v[k-1] 和 v[k+1] ) 应该计算出来。
知道我错过了什么吗？
我认为论文漏掉了一个证明，很简单，但我认为漏掉会导致一些混乱（对我来说），所以我在这里给出这个证明：
第6页第4行代码如下：
f k = −D or k ≠ D and V[k − 1] < V[k + 1] Then
x ← V[k + 1]
Else
x ← V[k − 1]+1
我不认为 lemma2 会导致这个，lemma2 的目的是证明这个问题可以用贪心策略来解决。并且根据 Given the endpoints of the furthest reaching (D − 1)-paths in diagonal k+1 and k−1, say (x’,y’) and (x",y")
respectively, Lemma 2 gives a procedure for computing the endpoint of the furthest reaching D-path in diagonal k.
Namely, take the further reaching of (x’,y’+1) and (x"+1,y") in diagonal k and then follow diagonal edges until it is
no longer possible to do so or until the boundary of the edit graph is reached. 正常的方法是获取从 v[k - 1] 和 v[k + 1] 延伸的两个点，并找出哪个是更远的到达路径。但这会导致双重计算。下面是为什么只检查 V[k − 1] < V[k + 1] 有效的证明：
引理4：
如果 v[k - 1] < v[k + 1]，那么后面跟着 v[k + 1] 且带有一条蛇的垂直边缘的路径将是对角线 k 中进一步研究的路径。
证明：
让我们将 v[k - 1] 变为 x1，将 v[k + 1] 变为 x2。所以对角线k中x1后面的点是(x1 + 1, x1 + 1 - k)（向右走），x2后面的点是(x2, x2 - k)（向下走）； y 位置在这里没用。
然后问题变为：if x1 < x2, then x1 + 1 <= x2
自 x1 < x2 -> x2 - x1 > 0
假设 x1 + 1 > x2，然后 x2 - x1 < 1，所以 0 < x2 - x1 < 1。但是在edit graph中，基本着法是1，0 < x2 - x1 < 1永远不会发生，所以假设是错误的，所以x1 + 1 <= x2。
我已经 post 这个和 https://github.com/psionic12/Myers-Diff-in-c-/blob/master/README.md 上的实现，欢迎您讨论。
如论文中的伪代码
4. If k = −D or k ≠ D and V[k − 1] < V[k + 1] Then
5. x ← V[k + 1]
6. Else
7. x ← V[k − 1]+1
8. y ← x − k
第 4 行表示如果 k 不是 -D 或 D，则取 x 较大的那个，然后找出蛇。这让我很困惑，难道我不应该同时计算 v[k-1] 和 v[k+1] 并找出哪条路径更远吗？如果我选择 x 较大的那个作为起点，结果我们的点会导致更远的路径怎么办？
此外，据此：
Namely, take the further reaching of (x’,y’+1) and (x"+1,y") in diagonal k and then follow diagonal edges until it is no longer possible to do so or until the boundary of the edit graph is reached.
我认为作者建议 (x',y'+1) 和 (x"+1,y")（在这种情况下，v[k-1] 和 v[k+1] ) 应该计算出来。
知道我错过了什么吗？
我认为论文漏掉了一个证明，很简单，但我认为漏掉会导致一些混乱（对我来说），所以我在这里给出这个证明：
第6页第4行代码如下：
f k = −D or k ≠ D and V[k − 1] < V[k + 1] Then
x ← V[k + 1]
Else
x ← V[k − 1]+1
我不认为 lemma2 会导致这个，lemma2 的目的是证明这个问题可以用贪心策略来解决。并且根据 Given the endpoints of the furthest reaching (D − 1)-paths in diagonal k+1 and k−1, say (x’,y’) and (x",y")
respectively, Lemma 2 gives a procedure for computing the endpoint of the furthest reaching D-path in diagonal k.
Namely, take the further reaching of (x’,y’+1) and (x"+1,y") in diagonal k and then follow diagonal edges until it is
no longer possible to do so or until the boundary of the edit graph is reached. 正常的方法是获取从 v[k - 1] 和 v[k + 1] 延伸的两个点，并找出哪个是更远的到达路径。但这会导致双重计算。下面是为什么只检查 V[k − 1] < V[k + 1] 有效的证明：
引理4：
如果 v[k - 1] < v[k + 1]，那么后面跟着 v[k + 1] 且带有一条蛇的垂直边缘的路径将是对角线 k 中进一步研究的路径。
证明：
让我们将 v[k - 1] 变为 x1，将 v[k + 1] 变为 x2。所以对角线k中x1后面的点是(x1 + 1, x1 + 1 - k)（向右走），x2后面的点是(x2, x2 - k)（向下走）； y 位置在这里没用。
然后问题变为：if x1 < x2, then x1 + 1 <= x2
自 x1 < x2 -> x2 - x1 > 0
假设 x1 + 1 > x2，然后 x2 - x1 < 1，所以 0 < x2 - x1 < 1。但是在edit graph中，基本着法是1，0 < x2 - x1 < 1永远不会发生，所以假设是错误的，所以x1 + 1 <= x2。
我已经 post 这个和 https://github.com/psionic12/Myers-Diff-in-c-/blob/master/README.md 上的实现，欢迎您讨论。