Диффер Майерса: почему V[k - 1] <V[k + 1] гарантированно выбирают дальнейший D-путь?

Как псевдокод в газете

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, а окажется, что наша точка приведет к дальнейшему пути?

И более того, согласно этому:

А именно, возьмите дальнейшее достижение (x ',y' +1) и (x"+1,y") по диагонали k, а затем следуйте по диагональным кромкам, пока это уже не будет возможно сделать, или до границы редактирования график достигнут.

Я думаю, что автор предполагает, что оба (x ',y' +1) и (x"+1,y") (в этом случае v[k-1] и v[k+1]) должны быть рассчитаны.

Так есть идеи, что мне не хватает?

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, поэтому точка с последующим x1 по диагонали к (x1 + 1, x1 + 1 - k)(идите направо), точка с последующим x2 является (x2, x2 - k)(опускаться); у позиция здесь бесполезна. тогда проблема меняется на: if x1 < x2, then x1 + 1 <= x2поскольку x1 < x2 -> x2 - x1 > 0Предположим, что x1 + 1 > x2, затем x2 - x1 < 1, так 0 < x2 - x1 < 1, Но в редактируемом графике основной ход равен 1, 0 < x2 - x1 < 1 никогда не случится, поэтому предположение неверно, поэтому x1 + 1 <= x2,

Я опубликую это и реализацию на https://github.com/psionic12/Myers-Diff-in-c-/blob/master/README.md, вы можете обсудить это.

Другие вопросы по тегам