Изучение разностного алгоритма Майерса: часть 2 - Средняя змея

Средняя змея

Совпадение

Можно одновременно прогнать прямой и обратный алгоритмы для последовательных значений D. При каком-то значении D две змеи совпадут на какой-то k линии. Статья доказывает, что одна из этих змей является частью решения. Так как она будет находиться где-то посередине, она называется средней змеей.

Средняя змея для примера выделена розовым  на этой диаграмме:

Рисунок 2: Средняя змея

Средняя змея полезна, потому что делит задачу на две части, которые затем можно решить отдельно и рекурсивно.

Средняя змея линейна в пространстве, потому что только последние V векторов должны храниться, давая O (D). Пока этот линейный алгоритм все еще является O ((N+M) D).

Помогает то, что средняя змея должна быть найдена с D, равным половине D из прямого и обратного алгоритмов. Отсюда следует, что по мере того как D возрастает, требуемое время достигает половины времени, требуемого базовым алгоритмам.

Ниже приведен имеющийся пока псевдокод:

for d = 0 to ( N + M + 1 ) / 2
{
  for k = -d to d step 2
  {
    вычислить самый дальний прямой и обратный пути достижения
    если есть совпадение, имеем среднюю змею
  }
}

Нечетная и четная дельты

Каждая разность – горизонтальное удаление или вертикальная вставка – является сдвигом от одной k линии к ее соседней линии. Поскольку дельта является разностью между серединами прямого и обратного алгоритмов, известно, какие значения d надо проверять на среднюю змею.

Для нечетной дельты надо искать совпадение прямых путей с разностями d и обратных путей с разностями d - 1.

Эта диаграмма показывает, что для дельты = 3 совпадение происходит, когда прямая d равна 2 и обратная d равна 1:

Рисунок 3: Нечетная дельта

Аналогично для четной дельты совпадения будут, когда прямой и обратный пути имеют одинаковое число разностей.

Следующая диаграмма показывает, что для дельта = 2 совпадение происходит, когда прямая и обратная разности равны 2:

Рисунок 4: Четная дельта

Алгоритм

Ниже приведен полный псевдокод для отыскания средней змеи:

delta = N - M
for d = 0 to ( N + M + 1 ) / 2
{
  for k = -d to d step 2
  {
    вычислить самый дальний прямой путь достижения на линии k
    если delta нечетна и ( k >= delta - ( d - 1 ) и k <= delta + ( d - 1 ) )
      если совпадение с обратным [ d - 1 ] на линии k
        => найдена средняя змея и SES длины 2D - 1
  }
  
  for k = -d to d step 2
  {
    вычислить самый дальний обратный путь достижения на линии k
    если дельта четна и (k >= -d - delta и k <= d - delta)
      если совпадение с прямым [ d ] на линии k
        => найдена средняя змея и SES длины 2D
  }
}

Замечание: Граничные проверки k служат для исключения невозможных совпадений.