Динамическое программирование по интервалам

После принятия этого решения приведенные выше рассуждения ведут прямо к успешной рекурсии. Пусть OPT(i, j) — максимальное количество пар оснований во вторичной структуре bbi+i... b. Запрет на резкие повороты позволяет инициа- лизировать OPT(i, j) = 0 для всех i > j - 4.

(Для удобства записи мы также разрешим ссылки OPT(i,j) даже при i >j; в этом случае значение равно 0).

Теперь в оптимальной вторичной структуре bpi+1... b. существуют те же альтер- нативы, что и прежде:

♦ j не участвует в паре; или

♦ j находится в паре с t для некоторого t < j - 4.

В первом случае имеем OPT(i, j) = OPT(i, j - 1). Во втором случае, изображенном на рис. 6.15, b, порождаются две подзадачи OPT(i, t - 1) и OPT(t + 1, j - 1); как было показано выше, эти две задачи изолируются друг от друга условием отсутствия пересечений.

Следовательно, мы только что обосновали следующее рекуррентное отношение:

(6.13) OPT(i, j) = mах(OPT(i, j - 1), max(1 + OPT(i, t - 1) + OPT(t + 1, j - 1))), где max определяется по t, для которых bt и b. образуют допустимую пару оснований (с учетом условий (i) и (ii) из определения вторичной структуры).

Теперь нужно убедиться в правильном понимании порядка построения реше- ний подзадач. Из (6.13) видно, что решения подзадач всегда вызываются для более коротких интервалов: тех, для которых k = j - i меньше. Следовательно, схема будет работать без каких-либо проблем, если решения строятся в порядке возрастания длин интервалов.

Инициализировать OPT(i,j) = 0 для всех i > j-4

For k = 5, 6............... n - 1

For i = 1,2.............. n - k

Присвоить j = i +k

Вычислить OPT(i,j) с использованием рекуррентного отношения из (6.13)

Конец For Конец For Вернуть OPT(I,n)

Рассмотрим пример выполнения этого алгоритма для входных данных ACCGGUAGU (рис. 6.14). Как и в задаче о рюкзаке, для представления массива M понадобятся два массива: для левой и для правой конечных точек рассматриваемо- го интервала. На рисунке представлены только элементы, соответствующие парам [i, j] с i < j - 4, потому что только они могут быть отличны от нуля.

Рис. 6.16. Итерации алгоритма для конкретного экземпляра задачи предсказания

вторичной структуры РНК


Найти границу для времени выполнения несложно: существуют O(n2) подза- дач, которые необходимо решить, а вычисление рекуррентного отношения в (6.13) занимает время O(n) для каждой задачи. Следовательно, время выполнения будет равно O(n3).

Как обычно, саму вторичную структуру (а не только ее значение) можно вос- становить сохранением информации о достижении минимума в (6.13) и обратного отслеживания по вычислениям.

6.6.

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

Еще по теме Динамическое программирование по интервалам:

  1. СТЕРЕОТИП ДИНАМИЧЕСКИЙ
  2. ПСИХОЛОГИЯ ДИНАМИЧЕСКАЯ
  3. АНАЛИЗ КАУЗАЛЬНО-ДИНАМИЧЕСКИЙ
  4. Динамическая медитация
  5. В динамических методах
  6. Иванова Г.С. Основы программирования, 2002
  7. ПСИХИКА: ПОНИМАНИЕ ДИНАМИЧЕСКОЕ
  8. Динамический смысл аспектов
  9. ПРОЦЕСС ПСИХИЧЕСКИЙ: ХАРАКТЕРИСТИКА ДИНАМИЧЕСКАЯ
  10. Основной курс (Программирование)
  11. Эстетика программирования