Разработка рекурсивного алгоритма
Действительно, естественный жадный алгоритм для этой задачи неизвестен, что заставляет нас переключиться на динамическое программирование. Как упомина- лось ранее, знакомство с динамическим программированием начнется с рекурсив- ного алгоритма, а затем в следующем разделе мы перейдем на итеративный метод, более близкий по духу к алгоритмам оставшейся части этой главы.
Воспользуемся определениями, приведенными в формулировке задачи интер- вального планирования из раздела 1.2.
Имеются n заявок с пометками 1, ..., n; длякаждой заявки i указывается начальное время s. и конечное время f.. С каждым интервалом i связывается некоторое значение — вес v. Два интервала называются совместимыми, если они не перекрываются. Целью текущей задачи является на- хождение подмножества S 5Ξ {1,...,;?} взаимно совместимых интервалов, максими- зирующего сумму весов выбранных интервалов ∑.Д’.·
Предположим, заявки отсортированы в порядке неубывания конечного време- ни: f 0 и предположим, что Compute-Opt(i) правильно вычисляет OPT(i) для всех i < j. Из индукционной гипотезы следует, что Compute-Opt( p(j)) = OPT( p(j)) и Compute- Opt(j - 1) = OPT( j - 1); следовательно, из (6.1)
OPT(j) = max(v, + Compute-Opt( p (j)), Compute-Opt( j - 1))
= Compute-Opt(j) ■
К сожалению, если реализовать алгоритм Compute-Opt в этом виде, его выпол- нение в худшем случае займет экспоненциальное время.
Например, на рис. 6.3 изображено дерево вызовов для экземпляра задачи на рис. 6.2: оно очень быстро расширяется из-за рекурсивного ветвления. Или более экстремальный пример: в системе с частым наслоением наподобие изображенной на рис. 6.4, где p( j) = j - 2 для всех j = 2, 3, 4, ..., n, мы видим, что Compute-Opt( j) генерирует раздельные рекур- сивные вызовы для задач с размерами j - 1 и j - 2. Другими словами, общее коли- чество вызовов Compute-Opt в этой задаче будет расти в темпе чисел Фибоначчи, что означает экспоненциальный рост. Таким образом, решение с полиномиальным временем так и остается нереализованным.ОРТ(6)
Рис. 6.3. Дерево подзадач, вызываемых Compute-Opt, для экземпляра задачи на рис. 6.2 |
Рис. 6.4. Экземпляр задачи взвешенного интервального планирования, для которого простая рекурсия Compute-Opt занимает экспоненциальное время. Веса интервалов в этом примере равны 1 |
Еще по теме Разработка рекурсивного алгоритма:
- Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
- Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
- АЛГОРИТМ
- АЛГОРИТМ УДАЧИ
- Алгоритм исцеления:
- Алгоритм избавления от боли
- § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
- Алгоритм обработки результатов.
- 2. Специфика и алгоритмы работы с источниками.
- СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
- Э. ТАНЕНБАУМ, А. ВУДХАЛЛ. ОПЕРАЦИОННЫЕ СИСТЕМЫ Разработка и реализация 3-е издание, 2007
- Разработка Плана
- 2.7. Разработка анкеты
- 6. Разработка перспектив
- Разработка и принятие Основного закона
- Состояние научной разработки проблемы.
- Правило разработки веера версий
- Правило разработки графических схем