Разработка и анализ алгоритма Динамическое программирование: первая попытка
Проблемы начинаются тогда, когда мы пытаемся записать рекуррентное отноше- ние, выражающее 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
- АНАЛИЗ КАУЗАЛЬНО-ДИНАМИЧЕСКИЙ
- § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
- СОЦИОЛОГИЧЕСКИЙ АНАЛИЗ СЕМЬИ В ЕДИНСТВЕ СТРУКТУРНЫХ И ДИНАМИЧЕСКИХ КООРДИНАТ
- § 2.ФУНКЦИИ МЕТОДОЛОГИИ В РАЗРАБОТКЕ МЕТОДИК АНАЛИЗА СОЦИАЛЬНЫХ ФАКТОВ
- Часть первая Анализ игр
- Часть первая Анализ игр
- Иванова Г.С. Основы программирования, 2002
- Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
- О. Л. Голицына, Т. Л. Партыка, И. И. Попов. ЯЗЫКИ ПРОГРАММИРОВАНИЯ, 2008
- Попытка портрета
- СТЕРЕОТИП ДИНАМИЧЕСКИЙ
- ПСИХОЛОГИЯ ДИНАМИЧЕСКАЯ