Интервальное планирование
Более формальная постановка: имеется n заявок с номерами 1, ..., n; в каждой заявке i указывается начальное время s. и конечное времяf. Естественно, s. < f для всех i . Две заявки i и j называются совместимыми, если запрашиваемые интервалы не перекрываются, то есть заявка i приходится либо на более ранний интервал времени, чем у j (f < s.), либо на более поздний интервал времени, чем у j (f < s). В более общем смысле подмножество A заявок называется совместимым, если все пары запросов i, j A, i Φ j являются совместимыми.
Целью алгоритма является выбор совместимого подмножества заявок максимально возможного размера.Пример задачи интервального планирования представлен на рис. 1.4. На диа- грамме представлено одно совместимое множество размера 4, и оно является самым большим совместимым множеством.
Вскоре мы увидим, что эта задача может быть решена с применением очень естественного алгоритма, который упорядочивает множество заявок по некоторой эвристике, а затем «жадно» обрабатывает их за один проход, выбирая совмести-
мое подмножество максимально возможного размера. Это типично для категории «жадных» (greedy) алгоритмов, которые мы будем рассматривать для различных задач, — «недальновидных» правил, которые обрабатывают входные данные по одному элементу без сколько-нибудь очевидных опережающих проверок. Когда «жадный» алгоритм находит оптимальное решение для любых конфигураций зада- чи, это часто выглядит совершенно неожиданно. Впрочем, сам факт оптимальности столь простого решения обычно что-то говорит о структуре нижележащей задачи.
Рис. 1.4. Пример задачи интервального планирования |
Еще по теме Интервальное планирование:
- 4.2.3. Интервальная шкала
- Интервальная шкала
- Планирование телепередач
- Планирование, а не планы
- 11. КРИМИНАЛИСТИЧЕСКИЕ ВЕРСИИ И ПЛАНИРОВАНИЕ РАССЛЕДОВАНИЯ
- § 2. ПЛАНИРОВАНИЕ И СОДЕРЖАНИЕ НАБЛЮДЕНИЯ
- 10.2. Планирование и организация следственных действий
- 5.4. Планирование упражнений
- Искусство планирования спонтанного
- 5.9. Планирование социальных контактов
- 5.2.9. Планирование сроков достижения уже определённой цели
- Статья 437. Планирование, подготовка, развязывание и ведение агрессивной войны
- 11.3. Понятие и основные принципы планирования расследования в зависимости от исходной информации (следственной ситуации)
- Вопросы для самопроверки
- Программирование телевизионного вещания