Диффер Майерса: почему 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, вы можете обсудить это.