Взвешенное интервальное планирование

В задаче интервального планирования мы стремились максимизировать коли- чество одновременно принимаемых заявок. Теперь рассмотрим более общую постановку задачи: интервалу каждой заявки i присваивается соответствующий коэффициент (вес) v.
> 0; можно рассматривать его как оплату, которую владелец ресурса получит от i-го претендента при удовлетворении его заявки. Наша цель — найти совместимое подмножество интервалов с максимальным общим весом.

Частный случай, при котором v. = 1 для каждого i, представляет собой базовую задачу интервального планирования; однако введение произвольных весов су- щественно влияет на природу задачи максимизации. Например, если значение v1 превышает сумму всех остальных vi, то оптимальное решение должно включать интервал 1 независимо от конфигурации полного набора интервалов. Итак, любой алгоритм для решения этой задачи должен быть крайне чувствителен к значениям весов, но при этом вырождаться в метод решения (невзвешенной) задачи интер- вального планирования, если все значения равны 1.

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

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

Еще по теме Взвешенное интервальное планирование:

  1. 4.2.3. Интервальная шкала
  2. Интервальная шкала
  3. Планирование телепередач
  4. Планирование, а не планы
  5. 11. КРИМИНАЛИСТИЧЕСКИЕ ВЕРСИИ И ПЛАНИРОВАНИЕ РАССЛЕДОВАНИЯ
  6. § 2. ПЛАНИРОВАНИЕ И СОДЕРЖАНИЕ НАБЛЮДЕНИЯ
  7. 10.2. Планирование и организация следственных действий
  8. 5.4. Планирование упражнений
  9. Искусство планирования спонтанного
  10. 5.9. Планирование социальных контактов
  11. 5.2.9. Планирование сроков достижения уже определённой цели
  12. Статья 437. Планирование, подготовка, развязывание и ведение агрессивной войны
  13. 11.3. Понятие и основные принципы планирования расследования в зависимости от исходной информации (следственной ситуации)