Обратная формулировка динамического программирования

Вспомните, что запись f(i, j) использовалась для обозначения длины кратчай- шего пути из (0, 0) в (i, j) в графе GXY. (Как было показано в исходном варианте алгоритма выравнивания последовательностей, f (i, j) имеет то же значение, что и OPT(i, j)).
Теперь определим g(i, j) как длину кратчайшего пути из (i, j) в (m, n) в GXY. Функция g предоставляет столь же естественный подход к решению задачи выравнивания последовательностей методом динамического программирования, не считая того, что на этот раз решение строится в обратном порядке: мы начинаем с g(m, n) = 0, а искомым ответом является g(0, 0).

По строгой аналогии с (6.16) имеем следующее рекуррентное отношение для g:

(6.18) Для i < m и j < n

g('J) = min[a⅛⅜i +g(i+ 1 ,j+ 1), δ + g(i,j+ 1), δ + g(i +1,;)].

Это же рекуррентное отношение будет получено, если взять граф GXY, «развер- нуть» его так, чтобы узел (m, n) находился в левом нижнем углу, и воспользоваться приведенным выше методом. По этой схеме также можно проработать полный алгоритм динамического программирования для построения значений g в об- ратном направлении, начиная с (m, n). Также существует версия этого обратного алгоритма динамического программирования, эффективная по затратам памяти (аналог описанного выше алгоритма), которая вычисляет значение оптимального выравнивания с затратами памяти, не превышающими O(m + n). Эта обратная версия далее будет обозначаться именем Backward-Space-Efficient-Alignment.

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

Еще по теме Обратная формулировка динамического программирования:

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