Подразделы

Другие разделы

Дата и время

09/04/2025 22:13:37

Авторизация

Зарегистрироваться
Восстановить пароль

Жадный метод

Идея жадного метода Задача планирования

Задача планирования

Мы имеем $n$ заданий, выполнение каждого из которых занимает единицу времени. У каждого задания есть связанная с ним прибыль $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$ является допустимым, если оно удовлетворяет двум условиям:

если $S[t] = i > 0$ , то $t <= d_i$ , то есть каждое запланированное задание соответствует своему сроку;
если $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]$ .