Расширения

Задача интервального планирования, рассмотренная нами, относится к числу от- носительно простых задач планирования. На практике возникает много дополни- тельных сложностей. Ниже перечислены проблемы, которые в той или иной форме встретятся позднее в книге.

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

♦ Наша постановка задачи стремилась к максимизации удовлетворенных заявок. Однако также можно представить ситуацию, в которой заявки обладают раз- ной ценностью. Например, каждой заявке i может быть присвоен вес vt (доход от удовлетворения заявки i), и целью становится обеспечение максимального дохода: суммы весов всех удовлетворенных заявок. Так мы подходим к задаче взвешенного интервального планирования — второй из типичных задач, упо- минавшихся в главе 1.

У задачи интервального планирования существует много других вариаций и разновидностей. Сейчас мы обсудим одну из таких вариаций, потому что она дает еще один пример ситуации, в которой жадный алгоритм может использоваться для получения оптимального решения.

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

Еще по теме Расширения:

  1. ВАРИКОЗНОЕ РАСШИРЕНИЕ ВЕН
  2. Расширение графического метода
  3. Самовоспитание как "расширение" сознания
  4. 3.1. РАСШИРЕНИЕ НЕЙРОЛОГИЧЕСКОГО КОНТАКТА
  5. 3.12.2. Техника расширенного восприятия
  6. Расширение внутреннего кругозора
  7. 7.2.2. Расширение полноты ответа
  8. 7.2.2. Расширение полноты ответа
  9. Метод расширения сознания
  10. 2. Расширение круга наследников по закону в российском наследственном праве
  11. 2. Расширение сети вольной русской прессы в 1860-е годы
  12. Развивающие вопросы призваны способствовать расширению поля беседы в сторону уточнения деталей, эмоциональных переживаний героя, включая ее в более широкий контекст.