Разработка и анализ алгоритма Динамическое программирование: первая попытка

Вероятно, первая естественная попытка применения динамического программи- рования будет основана на следующих подзадачах: мы говорим, что OPT(j) — мак- симальное количество пар оснований во вторичной структуре b1, b2, ..., b.
Согласно приведенному выше запрету на резкие повороты, мы знаем, что OPT( j) = 0 для j < 5; также известно, что OPT(n) — искомое решение.

Проблемы начинаются тогда, когда мы пытаемся записать рекуррентное отноше- ние, выражающее OPT( j) в контексте решений меньших подзадач. Здесь можно прой- ти часть пути: в оптимальной вторичной структуре b1, b2, ..., b. возможно одно из двух:

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

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


В первом случае необходимо обратиться к решению для OPT( j - 1). Второй слу- чай изображен на рис. 6.15, a; из-за запрета на пересечения мы знаем, что не может существовать пары, один конец которой находится между 1 и t - 1, а другой — между t + 1 и j - 1. Таким образом, мы фактически выделили две новые подзадачи: для оснований b1b2 ... bt1 и для оснований b+1... b r Первая решается как OPT(t - 1), а вторая в наш список подзадач не входит, потому что она не начинается с b1.

Это соображение наводит на мысль о том, что в задачу следует добавить пере- менную. Нужно иметь возможность работать с подзадачами, не начинающимися с by, другими словами, необходимо иметь возможность рассматривать подзадачи для b.b.+l... b. при любых i

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

Еще по теме Разработка и анализ алгоритма Динамическое программирование: первая попытка:

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