Изучение разностного алгоритма Майерса: часть 1 - Алгоритм
ОГЛАВЛЕНИЕ
Алгоритм
Алгоритм итеративный. Он вычисляет самые дальние пути достижения на каждой k линии для очередного d. Решение найдено, когда путь достигает правого нижнего угла. Это гарантированно является LCS / SES, так как уже были вычислены варианты с меньшим d. Максимальное значение d наблюдается при отсутствии совпадений, которое является N удалений + M вставок.
for ( int d = 0 ; d <= N + M ; d++ )
Внутри этого цикла мы должны найти самый дальний путь достижения для каждой k линии. Для заданного d единственные k линии, которые могут быть достигнуты, лежат в диапазоне [-d .. +d]. k = -d возможно, когда все сдвиги направлены вниз, и k = +d, когда сдвиги направлены вправо. Важное замечание по реализации заключается в том, что конечные точки для четного d расположены на четных k линиях, и наоборот. Поэтому внутренний цикл такой:
for ( int k = -d ; k <= d ; k += 2 )
Пропущенный кусок – способ отыскания самого дальнего пути достижения на заданной k линии.
Чтобы попасть на линию k, надо сдвинуться вниз от линии k + 1 или вправо от линии k - 1. Если мы сохраним самые дальние пути достижения от предыдущего d, то сможем выбрать сдвиг, который перебросит нас дальше всего вдоль линии k. Два пограничных случая: когда k = -d – в случае чего можно лишь двигаться вниз, и k = +d – когда можно двигаться лишь вправо.
Пример при d = 3
Разберем пример для d = 3, что значит k линии [-3, -1, 1, 3]. Для помощи конечные точки змей переписаны в виды таблицы ниже:
Рисунок 3. Таблица конечных точек
k = -3: Нельзя добраться до линии k = -4 при d = 2, поэтому надо сдвинуться вниз от линии k = -2. Сохраненный результат от предыдущего d = 2 дает начальную точку (2, 4). Сдвиг вниз дает среднюю точку (2, 5), и получаем диагональ, приводящую к (3, 6).
k = -1: Здесь есть два варианта. Можно двигаться вправо от k = -2 или вниз от k = 0. Результаты для предыдущего d = 2 гласят, что предыдущая точка на k = -2 есть (2, 4), а предыдущая точка на k = 0 есть (2, 2). Сдвиг вправо от k = -2 приводит к (3, 4), а сдвиг вниз от k = 0 приводит к (2, 3). Поэтому выбираем k = -2, так как это перебросит нас дальше вдоль линии k = -1. Снова получаем диагональ, поэтому змея является (2, 4) -> (3, 4) -> (4, 5).
k = 1: Снова есть два варианта. Можно двигаться вправо от k = 0 или вниз от k = 2. Предыдущими конечными точками являются (2, 2) и (3, 1), которые обе приводят к (3, 2). Произвольно решаем начать из точки с большим значением x, которая с диагональю дает змею (3, 1) -> (3, 2) -> (5, 4).
k = 3: Это другой пограничный случай. Линия k = 4 невозможна с d = 2, поэтому двигаемся вправо от k = 2. Предыдущий результат для k = 2 есть (3, 1), поэтому сдвиг вправо приводит к (4, 1). Снова получаем диагональ, дающую конечную точку в (5, 2).
Реализация
Как это реализовать? Есть два цикла, нужна структура данных.
Следует отметить, что решения для d(n) зависят только от решений для d(n - 1). Также помните, что для четных значений d мы находим конечные точки на четных k линиях, зависящих только от предыдущих конечных точек, которые все находятся на нечетных k линиях. Аналогично для нечетных значений d.
Поэтому используется массив по имени V с индексом k и координатой x конечной точки в качестве значения. Не надо хранить координату y, так как она вычисляется по заданным x и k: y = x - k. Также для заданного d, k находится в диапазоне [-d … d], являющи(е)хся индексами в V и ограничивающих(е) его размер.
Это хорошо работает, поскольку, когда d – четный, то конечные точки для четных индексов k вычисляются с использованием нечетных значений k, постоянных для этой итерации d. Аналогично для нечетных значений d.
Решение, двигаться вниз или вправо, чтобы дойти до заданной k линии, можно записать в виде булева выражения:
bool down = ( k == -d || ( k != d && V[ k - 1 ] < V[ k + 1 ] ) );
Если k = -d, надо двигаться вниз, а если k = d, надо двигаться вправо. Для нормальных средних случаев начинаем от той из соседних линий, которая имеет большее значение x. Это гарантирует достижение самой дальней точки на k линии.
Также нужна заглушка для d = 0, поэтому задаем V [ 1 ] = 0. Это означает точку на линии k = 1, где x = 0. Следовательно, это точка (0, -1). Мы гарантированно двигаемся вниз от этой точки, дойдя до (0, 0), как требуется.
Основная реализация приведена ниже:
V[ 1 ] = 0;
for ( int d = 0 ; d <= N + M ; d++ )
{
for ( int k = -d ; k <= d ; k += 2 )
{
// вниз или вправо?
bool down = ( k == -d || ( k != d && V[ k - 1 ] < V[ k + 1 ] ) );
int kPrev = down ? k + 1 : k - 1;
// начальная точка
int xStart = V[ kPrev ];
int yStart = xStart - kPrev;
// средняя точка
int xMid = down ? xStart : xStart + 1;
int yMid = xMid - k;
// конечная точка
int xEnd = xMid;
int yEnd = yMid;
// идти по диагонали
int snake = 0;
while ( xEnd < N && yEnd < M && A[ xEnd ] == B[ yEnd ] ) { xEnd++; yEnd++; snake++; }
// сохранить конечную точку
V[ k ] = xEnd;
// проверить на решение
if ( xEnd >= N && yEnd >= M ) /* решение найдено */
}
}
Решение
Код выше находит первую змею, достигающую конца обеих последовательностей. Однако данные в V хранят лишь самую последнюю конечную точку для каждой k линии. Отыскание всех змей, ведущих к решению, требуют фиксации состояния V после каждой итерации d и затем движения обратно от dsolution до 0.
IList<V> Vs; // сохраненный V's проиндексирован на d
IList<Snake> snakes; // список для хранения решения
POINT p = new POINT( N, M ); // начинаем с конца
for ( int d = vs.Count - 1 ; p.X > 0 || p.Y > 0 ; d-- )
{
var V = Vs[ d ];
int k = p.X - p.Y;
// конечная точка находится в V
int xEnd = V[ k ];
int yEnd = x - k;
// вниз или вправо?
bool down = ( k == -d || ( k != d && V[ k - 1 ] < V[ k + 1 ] ) );
int kPrev = down ? k + 1 : k - 1;
// начальная точка
int xStart = V[ kPrev ];
int yStart = xStart - kPrev;
// средняя точка
int xMid = down ? xStart : xStart + 1;
int yMid = xMid - k;
snakes.Insert( 0, new Snake( /* начальная, средняя и конечная точки */ ) );
p.X = xStart;
p.Y = yStart;
}
Следует отметить, что приведенный «жадный» алгоритм имеет сложность O( (N+M) D ) во времени и пространстве.