Разработка алгоритма

Сначала мы покажем, что если интерес представляет только значение оптималь- ного выравнивания, а не само выравнивание, обойтись линейными затратами памяти несложно. Дело в том, что для заполнения элемента массиваA рекуррент- ному отношению из (6.15) необходима только информация из текущего столбца A и предыдущего столбца A.
Это позволяет «свернуть» массив A в массив B с раз- мерами m χ 2: при переборе алгоритмом значений j элементы вида B[i, 0] содержат значение «предыдущего» столбца A[i, j - 1], а элементы вида B[i, 1] — значение «текущего» столбца A[i, j].

Space-Efficient-Alignment(X, Y)

Массив B[0...m, 0...1]

Инициализировать B[i,0] = ίδ для всех i (как в столбце 0 массива A)

For j = 1............. n

B[0,1] = jЪ (соответствует элементу А[0,j])

For i = 1............. т

В[i, 1] = w;;w[Qt^j, + В[i - 1, 0],

δ + ВЦ - 1, 1], δ + ВЦ. 0]]

Конец For

Переместить столбец 1 массива B в столбец 0, чтобы освободить место для следующей итерации:

Обновить B[i,0] = B[i,1] для всех i

Конец For

Как нетрудно убедиться, при завершении этого алгоритма элемент масси- ва B[i, 1] содержит значение OPT(i, n) для i = 0, 1, ..., m. Кроме того, затраты времени этого алгоритма равны O(mn), а затраты памяти — O(m). Но тут возникает про- блема: как получить само выравнивание? Мы не располагаем достаточной инфор- мацией для выполнения такой процедуры, как Find-Alignment. Так как B в конце работы алгоритма содержит только последние два столбца исходного массива A, при попытке обратного отслеживания доступная информация ограничивается этими двумя столбцами. Можно попытаться обойти эту сложность «прогнози- рованием» выравнивания в процессе выполнения процедуры, эффективной по затратам памяти. В частности, при вычислении значений j-го столбца (теперь не- явно заданного) массива A можно предположить, что при очень малом значении некоторого элемента выравнивание, проходящее через этот элемент, является перспективным кандидатом на роль оптимального. Но у этого перспективного выравнивания могут возникнуть большие проблемы в будущем, и оптимальным может оказаться другое выравнивание, которое в данный момент выглядит далеко не так перспективно.

На самом деле у этой задачи имеется решение (само выравнивание можно восстановить с затратами памяти O(m + n)), но оно требует совершенно нового подхода, основанного на применении принципа «разделяй и властвуй», пред- ставленного в книге ранее. Начнем с простого альтернативного пути реализации базового решения, построенного по принципам динамического программирования.

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

Еще по теме Разработка алгоритма:

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