Изменения

Перейти к: навигация, поиск

Обсуждение участницы:Анна

822 байта добавлено, 10:47, 5 мая 2016
Нет описания правки
}}
== Описание алгоритма ==
Оптимальное расписание для этой задачи будем задавать множеством работ <tex>S</tex>, которые будут выполнены в начале, как после будет показано, именно за которые эти работы штраф начислен не будет. Работы, которые не войдут в <tex>S</tex>, то есть завершатся с опозданием, могут быть выполнены в конце в любом порядке.<br>
Чтобы построить множество <tex>S</tex>, будем добавлять работы в порядке неуменьшения их времен окончания, и как только некоторая работа <tex>j</tex> опаздывает, удалим из <tex>S</tex> работу с минимальным значением <tex>w_i</tex> и поставим <tex>j</tex> на ее место.<br>
Пусть есть работы <tex>1 \cdots n</tex> с временами окончания <tex>d_1 \leq d_2 \leq \cdots \leq d_n</tex>. Будем называть ''простоем '' временной интервал, в который на машине ничего не обрабатывается. Тогда следующий алгоритм вычислит оптимальное множество <tex>S</tex>.
S = <tex>S \leftarrow \varnothing</tex> '''for''' <tex>j = 1 </tex> '''to''' <tex>n</tex>: '''if''' <tex>j </tex> опаздывает, и все более ранние простои заполнены: найти <tex>i: w[i] = <tex>\min\limits_{k \in S}</tex>(w[k])</tex> '''if''' <tex>w[i] < w[j]</tex>: заменить <tex>i </tex> на <tex>j </tex> в <tex>S</tex>
'''else''':
добавить <tex>i </tex> в <tex>S </tex> и поставить <tex>i </tex> на место самого раннего простоя
Таким образом, работы, не попавшие в <tex>S</tex>, будут иметь минимальное значение <tex>w_i</tex>.
== Доказательство корректности ==
Вышеописанный алгоритм корректен и строит оптимальное множество работ <tex>S</tex>.
|proof=
Пусть <tex>S</tex> {{---}} множество работ, вычисленное с помощью алгоритма. Тогда все работы, находящиеся в этом множестве, будут выполнены в срок, то есть штраф за них налагаться не будет, так как если работа <tex>j</tex> заменила работу <tex>i</tex>, которая успевала выполниться до истечения <tex>d_i</tex>, то <tex>j</tex> так же успеет выполниться в срок, потому что <tex>d_i \leq d_j</tex>.<br>Пусть <tex>S^*</tex> {{---}} множество работ без штрафов в оптимальном расписании.
}}
577
правок

Навигация