Интервальное планирование: жадный алгоритм опережает

Вспомните задачу интервального планирования — первую из пяти типичных задач, рассмотренных в главе 1. Имеется множество заявок {1, 2, ..., n}; i-я заявка соответ- ствует интервалу времени, который начинается в s(i) и завершается в f(i).
(Обра- тите внимание: мы слегка изменили запись по сравнению с разделом 1.2, где вместо s(i) использовалось обозначение s, а вместо f (i) — обозначениеf; такое изменение упростит запись доказательств.) Подмножество заявок называется совместимым, если никакие две заявки не перекрываются по времени; наша цель — получить со- вместимое подмножество как можно большего размера. Совместимые множества максимального размера называются оптимальными.

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

Еще по теме Интервальное планирование: жадный алгоритм опережает:

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