Расширения

Существует много разных обобщений задачи планирования. Например, мы пред- положили, что все задания были готовы к запуску, начиная с общего начального времени 5. Естественная, но более сложная версия этой задачи содержит заявки i, которые, в дополнение к предельному времени d.
и запрашиваемому времени t,, также содержат минимально возможное начальное время r. Самое раннее воз- можное начальное время обычно называется временем разблокировки. Задачи с вре- менем разблокировки естественным образом встречаются в ситуациях с заявками вида: «Можно ли зарезервировать аудиторию для проведения двухчасовой лекции в интервале от 13 до 17 часов?» Наше доказательство того, что жадный алгоритм находит оптимальное решение, принципиально зависит от факта доступности всех заявок в общее начальное время 5. (А вы видите, где именно?) К сожалению, как будет показано далее в главе 8, для более общего варианта задачи найти оптималь- ное решение намного сложнее.

4.3.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика 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. Развивающие вопросы призваны способствовать расширению поля беседы в сторону уточнения деталей, эмоциональных переживаний героя, включая ее в более широкий контекст.
  13. VC16 - расположена на уровне 5-го межреберья.
  14. Успех
  15. Линия 5-7 (Юпитер-Сатурн)