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

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

0 голосов
/ 09 октября 2018

В качестве псевдокода в статье 

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 Ответ

0 голосов
/ 17 октября 2018

Я думаю, что в статье пропущено доказательство, которое очень просто, но я думаю, что пропущенное приведет к некоторой путанице (для меня), поэтому я привожу это доказательство здесь:

на странице 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]:

lemma4: если v[k - 1] < v[k + 1], то путь, за которым следует v[k + 1] с вертикальным ребром со змеей, будет дальнейшим перестроенным путем по диагонали k.

доказательство: давайте сделаем v[k - 1] до x1 и v[k + 1] до x2.поэтому точка, за которой следует x1 на диагонали k, равна (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.Но в редактируемом графике основной ход равен 1, 0 < x2 - x1 < 1 никогда не произойдет, поэтому предположение неверно, поэтому x1 + 1 <= x2.

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

...