Динамическое программирование по интервалам
(Для удобства записи мы также разрешим ссылки 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.
Еще по теме Динамическое программирование по интервалам:
- СТЕРЕОТИП ДИНАМИЧЕСКИЙ
- ПСИХОЛОГИЯ ДИНАМИЧЕСКАЯ
- АНАЛИЗ КАУЗАЛЬНО-ДИНАМИЧЕСКИЙ
- Динамическая медитация
- В динамических методах
- Иванова Г.С. Основы программирования, 2002
- ПСИХИКА: ПОНИМАНИЕ ДИНАМИЧЕСКОЕ
- Динамический смысл аспектов
- ПРОЦЕСС ПСИХИЧЕСКИЙ: ХАРАКТЕРИСТИКА ДИНАМИЧЕСКАЯ
- Основной курс (Программирование)
- Эстетика программирования