Начало
Учебные материалы
Жадный метод
Задача планирования
У каждого задания есть связанная с ним прибыль `G[i]`, а также предельный срок `D[i]`; если задание не выполнено
к своему предельному сроку, то мы не получаем его прибыль.
Мы хотели бы так запланировать их последовательность выполнения, чтобы получить максимальную прибыль.
Расписание представляет собой массив `S[1...d]`, где `d = max D[i]`, то есть
`d` – это последний предельный срок, после которого задания не могут быть запланированы.
Если `S[t] = i`, то задание `i` запланировано на момент времени `t`, `1 <= t <= d`.
Если `S[t] = 0`, то никакого задания на момент времени `t` не запланировано.
`P(S)` - это прибыль от расписания `S`.
--
Расписание `S` является допустимым, если оно удовлетворяет двум условиям:
1. если `S[t] = i > 0`, то `t <= d_i`, то есть каждое запланированное задание
соответствует своему сроку;
2. если `t_1 != t_2` и `S[t_1] != 0`, тогда `S[t_1] != S[t_2]`, то есть каждое задание планируется не более одного раза.
Жадный алгоритм упорядочивает задания в невозврастающем порядке прибыли и размещает их как можно
позже в пределах их предельного срока. Удивительно, но этот алгоритм работает,
что является научным "обоснованием" для бюрократической волокиты.
--
Алгоритм Planning(`G,D`)
Отсортировать задания в невозрастающем порядке прибылей
`d larr max_i D[i]`
**for** `t in [1...d]` **do**
`quad S[t] larr 0`
**for** `i in [1...n]` **do**
`quad` Найти самое большое `t` такое, что `S[t] = 0` и `t <= D[i]`
`quad` **if** `t` найдено
`quad quad S[t] larr i`
--
Расписание является *перспективным*, если его можно расширить до оптимального расписания.
Условие "`S` является перспективным" является инвариантом для
второго цикла **for** в алгоритме.
Доказательство выполняется по индукции. Базовый случай:
перед циклом `S = (0, 0,..., 0)`, и мы можем расширить его заданиями
`{1, 2,..., n}`, то есть в нашем распоряжении есть все задания; поэтому `S` является
перспективным, так как мы можем взять любое оптимальное расписание, и оно
будет расширением `S`.
--
Индукционный шаг: предположим, что `S` является перспективным, и пусть `S_{"opt"}`
равно некому оптимальному расписанию, которое расширяет `S`. Пусть `S'` равно
результату после `i`-й итерации цикла. Мы должны доказать, что `S'` остается перспективным,
то есть существует оптимальное расписание `S_{"opt"}`, которое расширяет
`S'`.
Случай 1: задание `i` не может быть запланировано. Тогда `S' = S` и доказательство завершено.
--
Случай 2: Задание `i` планируется на момент времени `t_0` и `t_0` является самым последним возможным временем для задания `i`
Мы имеем два подслучая.
Подслучай 2a: задание `i` запланировано в `S_{"opt"}` на момент времени `t_1`:
* если `t_1 = t_0`, то доказательство завершено;
* если `t_1 < t_0`, тогда пусть `S'_{"opt"}` равно `S_{"opt"}`, за исключением того, что мы переставляем
`t_0` и `t_1`, то есть `S'_{"opt"}[t_0] = i` и `S'_{"opt"}[t_1]=S_{"opt"}[t_0]`. Тогда `S'_{"opt"}` является
допустимым, оно расширяет `S'` и `P(S'_{"opt"}) = P(S_{"opt"})`
* Случай `t_1 > t_0` невозможен
--
Подслучай 2b: задание `i` не запланировано в `S_{"opt"}`. Тогда мы просто определяем
`S'_{"opt"}` таким же, как `S_{"opt"}`, за исключением, что `S'_{"opt"}[t_0]=i`.
Поскольку `S_{"opt"}` является допустимым, то и `S'_{"opt"}` тоже является допустимым, и поскольку `S'_{"opt"}` расширяет `S_{"opt"}`, нам
нужно только показать, что `P(S'_{"opt"}) = P(S_{"opt"})`.
Это вытекает из следующего утверждения: Пусть `S'_{"opt"}[t_0]=j`, тогда `G[j] <= G[i]`.
Докажем утверждение от обратного: предположим, что `G[j] > G[i]`. Тогда задание `j` было рассмотрено перед заданием `i`.
Поскольку задание `i` было запланировано на момент времени `t_0`, задание `j`
должно быть запланировано на момент времени `t_2 != t_0`.
Но `S_{"opt"}` расширяет `S`, и `S[t_2] = j != S_{"opt"}[t2]` – противоречие.
