Интервальное планирование
Рассмотрим очень простую задачу планирования. Имеется некий ресурс — аудито- рия, суперкомпьютер, электронный микроскоп и т. д.; множество людей обращает- ся с заявками на использование ресурса в течение периода времени.
Более формальная постановка: имеется n заявок с номерами 1, …, n; в каждой заявке i указывается начальное время si и конечное время fi. Естественно, si < fi для всех i. Две заявки i и j называются совместимыми, если запрашиваемые интервалы не перекрываются, то есть заявка i приходится либо на более ранний интервал времени, чем у j ( fi ≤ sj), либо на более поздний интервал времени, чем у j ( fj ≤ si).
В более общем смысле подмножество A заявок называется совместимым, если все пары запросов i, j Ѯ A, i ≠ j являются совместимыми. Целью алгоритма является выбор совместимого подмножества заявок максимально возможного размера.
Пример задачи интервального планирования представлен на рис. 1.4. На диа- грамме представлено одно совместимое множество размера 4, и оно является самым большим совместимым множеством.
Вскоре мы увидим, что эта задача может быть решена с применением очень естественного алгоритма, который упорядочивает множество заявок по некоторой эвристике, а затем «жадно» обрабатывает их за один проход, выбирая совместимое подмножество максимально возможного размера. Это типично для категории «жадных» (greedy) алгоритмов, которые мы будем рассматривать для различных задач, — «недальновидных» правил, которые обрабатывают входные данные по одному элементу без сколько-нибудь очевидных опережающих проверок.
Когда «жадный» алгоритм находит оптимальное решение для любых конфигураций зада- чи, это часто выглядит совершенно неожиданно. Впрочем, сам факт оптимальности столь простого решения обычно что-то говорит о структуре нижележащей задачи.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу