Анализ алгоритма

Правильность алгоритма следует непосредственно из (6.16). Время выполнения равно O(mn), так как массив A содержит только O(mn) элементов и в худшем случае на каждый тратится постоянное время.

У алгоритма выравнивания последовательностей существует элегантное визу- альное представление.

Допустим, имеется двумерный решетчатый граф GXY с раз- мерами m X n; строки помечены символами X, столбцы помечены символами Y, а ребра направлены так, как показано на рис. 6.17.

Рис. 6.17. Представление выравнивания последовательностей в форме графа


Строки нумеруются от 0 до m, а столбцы от 0 до n; узел на пересечении i-й стро- ки иj-го столбца обозначается (i, j). Ребрам GXY назначаются стоимости: стоимость каждого горизонтального и вертикального ребра равна δ, а стоимость диагональ- ного ребра из (i - 1J - 1) в (i,j) равна и, t.

Теперь смысл этой схемы становится понятным: рекуррентное отношение для OPT(i, j) из (6.16) в точности соответствует рекуррентному отношению для пути минимальной стоимости от (0, 0) до (i, j) в GXY. Следовательно, мы можем показать

(6.17) Пусть f (i, j) — стоимость минимального пути из (0, 0) в (i, j) в GXY. Тогда для всех i, j выполняется условие f (i, j) = OPT(i, j).

Доказательство. Утверждение легко доказывается индукцией по i + j. Если i + j = 0, значит, i = j = 0, и тогда f (i, j) = OPT(i, j) = 0.

Теперь рассмотрим произвольные значения i и j и предположим, что утвержде- ние истинно для всех пар (i', j') с i' + j' < i + j. Последнее ребро кратчайшего пути к (i, j) проходит либо из (i - 1, j - 1), либо из (i - 1, j), либо из (i, j - 1). Следова- тельно, имеем

f(i,j) = miп[tt, +/(i - l,у - 1), δ +/(i - 1,7), δ +/(i,7 - 1)]

= miп[+ OPT(i - 1,7 - 1), δ + ОРТ(i-l,j), δ + OPT(i,7 - 1)]

= OPT(i,7),

Переход от первой строки ко второй осуществляется по индукционной гипоте- зе, а переход от второй к третьей — по (6.16).

Таким образом, значение оптимального выравнивания равно длине кратчайше- го пути в GXY от (0,0) до (m, n). (Любой путь в GXY из (0,0) в (m, n) будет называться путем из угла в угол.) Более того, диагональные ребра, используемые в кратчайшем пути, точно соответствуют парам выравнивания с минимальной стоимостью. Эти связи в задаче нахождения кратчайшего пути в графе GXY не приводят к прямому улучшению времени выполнения для задачи выравнивания последовательностей; однако они способствуют интуитивному пониманию задачи, а также помогают в поиске алгоритмов для более сложных видов выравнивания последователь- ностей.

Например, на рис. 6.18 приведены значения кратчайшего пути из (0, 0) в каж- дый из узлов (i, j) для задачи выравнивания слов mean и name. В контексте нашего примера предполагается, что δ = 2; стоимость сочетания гласной с другой гласной или согласной с другой согласной равна 1; стоимость сочетания гласной с соглас- ной равна 3. Для каждой ячейки в таблице (представляющей соответствующий узел) стрелкой обозначается последний шаг кратчайшего пути, ведущего к этому узлу, — другими словами, вариант достижения минимума в (6.16). Следовательно, возвращаясь по стрелкам в обратном направлении от узла (4, 4), можно построить выравнивание методом обратного отслеживания.

Рис. 6.18. Значения OPT для задачи выравнивания слов mean и name


6.7.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Анализ алгоритма:

  1. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  2. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  3. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  4. АЛГОРИТМ
  5. АЛГОРИТМ УДАЧИ
  6. Алгоритм исцеления:
  7. Алгоритм избавления от боли
  8. 2. Специфика и алгоритмы работы с источниками.
  9. Алгоритм обработки результатов.
  10. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  11. 2. ИСТОЧНИКИ ИНФОРМАЦИИ. СПЕЦИФИКА И АЛГОРИТМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ. ДОСТУП К ИСТОЧНИКАМ ИНФОРМАЦИИ. ПРАВОВЫЕ И ЭТИЧЕСКИЕ НОРМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ.
  12. Принципы анализа происшествия.
  13. АНАЛИЗ
  14. АНАЛИЗ КОРОТКИЙ