Проектирование жадного алгоритма

Задача интервального планирования сделает наше обсуждение жадных алгоритмов более конкретным. Основной идеей жадного алгоритма для интервального планирования является простое правило выбора первой заявки i1.

Возьмем несколько естественных правил и посмотрим, как они работают.

è Самое очевидное правило — всегда выбирать доступную заявку с самым ранним начальным временем, то есть заявку с минимальным значением s(i). При таком выборе ресурс начинает использоваться настолько быстро, насколько это возможно.

Этот метод не обеспечивает оптимального решения. Если самая ранняя заявка i резервирует ресурс на очень долгое время, то принятие заявки i приведет к отклонению множества заявок на более короткие интервалы.

Так как нашей целью является удовлетворение максимально возможного количества заявок, решение получится субоптимальным. В очень плохом случае — скажем, если конечное время f (i) максимально по всем заявкам — принятая заявка i зарезервирует ресурс на все время.

В этом случае жадный алгоритм примет одну заявку, тогда как оптимальное решение могло бы принять много заявок.

Предыдущий результат наводит на мысль о том, чтобы начать с заявки с наименьшим интервалом времени, а именно той, для которой разность f (i) − s(i) оказывается наименьшей из всех возможных.

Как выясняется, это правило чуть лучше предыдущего, но и оно может приводить к субоптимальному расписанию. Например, на рис. 4.1, b выбор короткого интервала в середине помешает принятию двух других заявок, формирующих оптимальное решение.