90
правок
Изменения
→Доказательство корректности алгоритма
|proof=
TODO
}}
{{
Теорема|statement=
Построенная перестановка <tex> T </tex> является оптимальной.
|proof=
Рассмотрим случайную перестановку <tex> S </tex>. Пусть перестановки <tex> T </tex> и <tex> S </tex> имеют общий префикс длины <tex> l-1 </tex>. Пусть <tex> i = T_{l} </tex> и <tex> j = S_{l} </tex>. Рассмотрим множество работ <tex>M = \{T_{r} \mid r = l, \dots, n\}</tex>. Заметим, что для любой работы <tex> k \in M </tex> верно, что <tex> \min(p_{k1}, p_{i2}) \geq \min(p_{i1}, p_{k2}) </tex>, так как если было бы верно обратное, то есть <tex> \min(p_{k1}, p_{i2}) < \min(p_{i1}, p_{k2}) </tex>, то по Лемме 1 было бы верно, что <tex> k </tex> идет раньше <tex> i </tex>, что неверно.
Очевидно, что в перестановке <tex> S </tex> работа <tex> i </tex> будет стоять после <tex> j </tex> (иначе общий префикс был бы короче), то заметим, что в этой перестановке для работы <tex> i </tex> и для предыдущей работы <tex> w </tex> верно <tex> \min(p_{w1}, p_{i2}) \geq \min(p_{i1}, p_{w2}) </tex> (так как <tex> w \in M </tex>), то по Лемме 2 можем поменять местами работы <tex> i </tex> и <tex> w </tex> без ухудшения ответа. То такими операциями сможем дойти до пары работ <tex> i </tex> и <tex> j </tex>, которые при смене увеличат общий префикс перестановок <tex> S </tex> и <tex> T </tex>.
Таким образом любая перестановка сводится к нашей без ухудшения ответа такими операциями, что подтверждает оптимальность перестановки <tex> T </tex>
}}
