1679
правок
Изменения
Новая страница: «== Сведение к другой задаче == При сведении текущей задачи теории расписаний <tex> S </tex> к как...»
== Сведение к другой задаче ==
При сведении текущей задачи теории расписаний <tex> S </tex> к какой-то другой <tex> S' </tex> необходимо доказать два пункта:
# Допустимость расписания, построенного с помощью задачи <tex> P </tex>, или существование способа его трансформации в допустимое.
# Следствие того, что если мы оптимизируем <tex> S' </tex>, мы также оптимизируем ответ для <tex> S </tex> (обратное в общем случае неверно).
Примечание — если требуется полиномиальное время для решения задачи, требуется, чтобы сведение к другой задаче и трансформация расписания в допустимое также происходили за полиномиальное время.
=== Примеры ===
==== 1 | intree | Sum(w_i C_i) ====
Предположим, что мы уже умеем решать задачу <tex> S' = 1 \mid outtree \mid \sum w_i C_i </tex>. Сведем нашу задачу <tex> S </tex> к ней следующим образом:
* Развернем все ребра, теперь если работа <tex> i </tex> зависела от работы <tex> j </tex>, работа <tex> j </tex> будет зависеть от <tex> i </tex>.
* Заменим все стоимости <tex> w_i </tex> на противоположные <tex> w'_i = - w_i</tex>.
Утверждается, что решив соответствующую задачу <tex> S' </tex> и развернув полученное расписание, мы получим ответ для текущей задачи.
# Полученное расписание будет допустимым, так как расписание для <tex> S' </tex> было допустимым, и в нем никакие две работы не пересекались и не прерывались. Развернув, мы не могли нарушить это свойство. Также из-за того, что мы развернули расписание, мы добились того, что все работы выполняются в правильном порядке (в расписании для <tex> S' </tex> из-за того, что расписание было развернуто, порядок был нарушен для всех работ). Таким образом, получили что расписание — допустимое.
# Пусть с помощью задачи <tex> S' </tex> мы получили последовательность работ <tex> 1 \dots n </tex> (не теряя общности, занумеруем их от 1 до n). Распишем по определению значение целевой функции для <tex> S </tex>:
#: <tex>\sum -w_i C_i = \sum \limits_{i=1}^n ( -w_i \sum \limits_{j=1}^i p_j ) = \\
\sum\limits_{i=1}^n ( w_i \sum\limits_{j=i+1}^n p_j ) - \sum\limits_{i=1}^n w_i \sum \limits_{i=1}^n p_i = \\
\sum\limits_{i=1}^n ( w_i \sum\limits_{j=i}^n p_j ) - \sum\limits_{i=1}^n w_i p_i - \sum\limits_{i=1}^n w_i \sum \limits_{i=1}^n p_i </tex>
#: Заметим, что первое слагаемое соответствует целевой функции <tex> \sum w_i C_i </tex> для последовательности <tex> n \dots 1 </tex>, а второе и третье слагаемые — константы, зависящие только от начальных данных и не зависящие от перестановки работ. Таким образом, оптимальное
значение для <tex> S' </tex> также минимизирует <tex> S </tex>, ч.т.д.
==== R || Sum(C_i) ====
==== O | p_ij=1 | Sum(C_i) ====
== Построение расписания по нижней оценке ==
=== Примеры ===
==== P | pmtn | C_max ====
==== O | p_ij=1 | C_max ====
== Бинарный поиск по ответу ==
=== Примеры ===
==== O | p_ij = 1, d_i | - ====
== Жадное построение расписания ==
=== Примеры ===
==== 1 | prec | f_max ====
==== 1 | outtree | Sum(w_i C_i) ====
При сведении текущей задачи теории расписаний <tex> S </tex> к какой-то другой <tex> S' </tex> необходимо доказать два пункта:
# Допустимость расписания, построенного с помощью задачи <tex> P </tex>, или существование способа его трансформации в допустимое.
# Следствие того, что если мы оптимизируем <tex> S' </tex>, мы также оптимизируем ответ для <tex> S </tex> (обратное в общем случае неверно).
Примечание — если требуется полиномиальное время для решения задачи, требуется, чтобы сведение к другой задаче и трансформация расписания в допустимое также происходили за полиномиальное время.
=== Примеры ===
==== 1 | intree | Sum(w_i C_i) ====
Предположим, что мы уже умеем решать задачу <tex> S' = 1 \mid outtree \mid \sum w_i C_i </tex>. Сведем нашу задачу <tex> S </tex> к ней следующим образом:
* Развернем все ребра, теперь если работа <tex> i </tex> зависела от работы <tex> j </tex>, работа <tex> j </tex> будет зависеть от <tex> i </tex>.
* Заменим все стоимости <tex> w_i </tex> на противоположные <tex> w'_i = - w_i</tex>.
Утверждается, что решив соответствующую задачу <tex> S' </tex> и развернув полученное расписание, мы получим ответ для текущей задачи.
# Полученное расписание будет допустимым, так как расписание для <tex> S' </tex> было допустимым, и в нем никакие две работы не пересекались и не прерывались. Развернув, мы не могли нарушить это свойство. Также из-за того, что мы развернули расписание, мы добились того, что все работы выполняются в правильном порядке (в расписании для <tex> S' </tex> из-за того, что расписание было развернуто, порядок был нарушен для всех работ). Таким образом, получили что расписание — допустимое.
# Пусть с помощью задачи <tex> S' </tex> мы получили последовательность работ <tex> 1 \dots n </tex> (не теряя общности, занумеруем их от 1 до n). Распишем по определению значение целевой функции для <tex> S </tex>:
#: <tex>\sum -w_i C_i = \sum \limits_{i=1}^n ( -w_i \sum \limits_{j=1}^i p_j ) = \\
\sum\limits_{i=1}^n ( w_i \sum\limits_{j=i+1}^n p_j ) - \sum\limits_{i=1}^n w_i \sum \limits_{i=1}^n p_i = \\
\sum\limits_{i=1}^n ( w_i \sum\limits_{j=i}^n p_j ) - \sum\limits_{i=1}^n w_i p_i - \sum\limits_{i=1}^n w_i \sum \limits_{i=1}^n p_i </tex>
#: Заметим, что первое слагаемое соответствует целевой функции <tex> \sum w_i C_i </tex> для последовательности <tex> n \dots 1 </tex>, а второе и третье слагаемые — константы, зависящие только от начальных данных и не зависящие от перестановки работ. Таким образом, оптимальное
значение для <tex> S' </tex> также минимизирует <tex> S </tex>, ч.т.д.
==== R || Sum(C_i) ====
==== O | p_ij=1 | Sum(C_i) ====
== Построение расписания по нижней оценке ==
=== Примеры ===
==== P | pmtn | C_max ====
==== O | p_ij=1 | C_max ====
== Бинарный поиск по ответу ==
=== Примеры ===
==== O | p_ij = 1, d_i | - ====
== Жадное построение расписания ==
=== Примеры ===
==== 1 | prec | f_max ====
==== 1 | outtree | Sum(w_i C_i) ====
