3622
правки
Изменения
м
Нет описания правки
Докажем некоторые свойства оптимального расписания, которые мы будем использовать в доказательстве корректности алгоритма.
Введем некоторые обозначения для удобства. За <tex> \mathrm{edges} </tex> обозначим список всех ребёр дерева. Для всех работ <tex>i = 1, ..., n</tex> обозначим за <tex>S(i)</tex> всех потомков <tex>i</tex> в дереве зависимостей, включая саму работу <tex>i</tex>, введём новый параметр работы <tex dpi = 150>q_i = \frac{w_i}{p_i}</tex>.
Для подмножества работ <tex>I \subseteq \{1, ..., n\}</tex> определим:
{{Теорема
|id = theorem1
|statement = Пусть <tex>i, ~j</tex> работы такие, что <tex>i</tex> {{---}} предок <tex>j</tex>, и <tex> q_j = \max \{q_k \mid ~ (i, k) \in \mathrm{edges} \}</tex>. <br>
Тогда существует оптимальное расписание, в котором работа <tex>j</tex> идёт сразу после работы <tex>i</tex>
|proof =
w[root] = <tex> - \infty </tex>
'''for''' i = 1..n: E[i] = {i}, J[i] = {i}, q[i] = w[i] \ p[i]
L = {1, ... , n}
'''while''' L <tex> \ne </tex> {root}: // пока в списке работ не останется только корень
Найти работу j <tex> \in </tex> L с маскимальным значением q[j]
par = P[j]
