Разработка рекурсивного алгоритма

Поскольку исходная задача интервального планирования представляет собой част- ный случай, в котором все веса равны 1, мы уже знаем, что большинство жадных алгоритмов не обеспечивает оптимального решения.
Но даже алгоритм, который работал ранее (многократный выбор интервала, завершающегося раньше всех), в этой ситуации уже не является оптимальным, как показывает простой пример на рис. 6.1.

Действительно, естественный жадный алгоритм для этой задачи неизвестен, что заставляет нас переключиться на динамическое программирование. Как упомина- лось ранее, знакомство с динамическим программированием начнется с рекурсив- ного алгоритма, а затем в следующем разделе мы перейдем на итеративный метод, более близкий по духу к алгоритмам оставшейся части этой главы.

Воспользуемся определениями, приведенными в формулировке задачи интер- вального планирования из раздела 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

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

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