1outtreesumwc - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:03:43Z

rollbackEdits.php mass rollback

185.243.218.46 в 06:36, 1 сентября 2022

2022-09-01T06:36:42Z

5.142.255.24: Опечатки

2021-12-02T17:19:27Z

Опечатки

Qradimir: 1 | intree | Sum(w*C) - наводим красоту

2016-06-06T23:29:04Z

1 | intree | Sum(w*C) - наводим красоту

188.162.65.20: /* Источники информации */ исправлена первая категория

2016-06-06T14:23:37Z

‎Источники информации: исправлена первая категория

Qradimir: Добавлен раздел про intree расписание

2016-06-06T00:23:14Z

Добавлен раздел про intree расписание

Shersh: /* Доказательство оптимальности алгоритма */

2016-05-01T17:45:37Z

‎Доказательство оптимальности алгоритма

Shersh: /* Алгоритм */

2016-05-01T17:43:07Z

‎Алгоритм

Shersh: /* Свойства оптимального расписания */

2016-05-01T17:42:06Z

‎Свойства оптимального расписания

Shersh в 13:11, 12 февраля 2015

2015-02-12T13:11:07Z

@@ Строка 1: / Строка 1: @@
 <tex dpi = "200" >1 \mid outtree \mid \sum w_i C_i</tex>
@@ Строка 163: / Строка 142: @@
 |statement=Развернутое оптимальное расписание соответствующей задачи <tex> S_{out} </tex> с весами <tex> w'_i </tex> является оптимальным расписанием для задачи  <tex> S_{in} </tex>
 |proof=
-Полученное расписание будет допустимым, так как расписание для <tex> S_{out} </tex> было допустимым, и в нем никакие две работы не пересекались и не прерывались. Развернув ребра, мы не могли нарушить это свойство. Также из-за того, что мы развернули ребра в расписании, мы добились того, что все работы выполняются в правильном порядке (в расписании для <tex> S_{out} </tex> из-за того, что все ребра были развернуты, порядок был нарушен для всех работ). Таким образом получили, что расписание допустимое.
+Полученное расписание будет допустимым, так как расписание для <tex> S_{out} </tex> было допустимым, и в нем никакие две работы не пересекались и не прерывались. Развернув ребра, мы не могли нарушить это свойство. Также из-за того, что мы развернули ребра в расписании, мы добились того, что все работы выполняются в правильном порядке (в расписании для <tex> S_{out} </tex> из-за того, что все ребра были развернуты, порядок был нарушен для всех работ). Таким образом получили, что расписание допустимое.
 Пусть с помощью задачи <tex> S_{out} </tex> мы получили последовательность работ <tex> 1 \dots n </tex>. Распишем по определению значение целевой функции для <tex> S_{out} </tex>:

@@ Строка 1: / Строка 1: @@
 <tex dpi = "200" >1 \mid outtree \mid \sum w_i C_i</tex>
@@ Строка 142: / Строка 163: @@
 |statement=Развернутое оптимальное расписание соответствующей задачи <tex> S_{out} </tex> с весами <tex> w'_i </tex> является оптимальным расписанием для задачи  <tex> S_{in} </tex>
 |proof=
-Полученное расписание будет допустимым, так как расписание для <tex> S_{out} </tex> было допустимым, и в нем никакие две работы не пересекались и не прерывались. Развернув ребра, мы не могли нарушить это свойство. Также из-за того, что мы развернули ребра в расписании, мы добились того, что все работы выполняются в правильном порядке (в расписании для <tex> S_{out} </tex> из-за того, что все ребра были развернуты, порядок был нарушен для всех работ). Таким образом получили, что расписание допустимое.
+Полученное расписание будет допустимым, так как расписание для <tex> S_{out} </tex> было допустимым, и в нем никакие две работы не пересекались и не прерывались. Развернув ребра, мы не могли нарушить это свойство. Также из-за того, что мы развернули ребра в расписании, мы добились того, что все работы выполняются в правильном порядке (в расписании для <tex> S_{out} </tex> из-за того, что все ребра были развернуты, порядок был нарушен для всех работ). Таким образом получили, что расписание допустимое.
 Пусть с помощью задачи <tex> S_{out} </tex> мы получили последовательность работ <tex> 1 \dots n </tex>. Распишем по определению значение целевой функции для <tex> S_{out} </tex>:

@@ Строка 82: / Строка 82: @@
    L = {1, ... , n}
    '''while''' L <tex> \ne </tex> {root} <font color=darkgreen>// пока в списке работ не останется только корень</font>
-     Найти работу j <tex> \in </tex> L с маскимальным значением q[j]
+     Найти работу j <tex> \in </tex> L с максимальным значением q[j]
      par = P[j]
      Найти i, что par <tex> \in </tex> J[i]
@@ Строка 102: / Строка 102: @@
 [[Файл:JobsOuttrees.jpg|650px]]
-Первой выберется работа с номером <tex> 5 </tex>. Она объединиться со своим родителем <tex> 2 </tex> и допишется в конец <tex> \pi_2 </tex>. Потом выберется работа <tex> 4 </tex>, потом <tex> \{2, 5\} </tex> и т. д. Процесс будет продолжаться, пока не останется одна вершина. Ответ {{---}} оптимальная последовательность работ {{---}} содержится в <tex> \pi_1 </tex>, который написан внутри последней вершины.
+Первой выберется работа с номером <tex> 5 </tex>. Она объединится со своим родителем <tex> 2 </tex> и допишется в конец <tex> \pi_2 </tex>. Потом выберется работа <tex> 4 </tex>, потом <tex> \{2, 5\} </tex> и т. д. Процесс будет продолжаться, пока не останется одна вершина. Ответ {{---}} оптимальная последовательность работ {{---}} содержится в <tex> \pi_1 </tex>, который написан внутри последней вершины.
 == Доказательство оптимальности алгоритма ==

@@ Строка 130: / Строка 130: @@
 }}
-== Применение алгоритма в задаче с intree-зависимостью ==
+== 1 | intree | Sum(w*C)==
 Сведем задачу <tex> S_{in} = 1 \mid intree \mid \sum w_i C_i </tex> к решенной задаче <tex>S_{out} = 1 \mid outtree \mid \sum w_i C_i </tex> следующим образом:
-* Развернем все ребра, теперь если работа <tex> i </tex> зависела от работы <tex> j </tex>, работа <tex> j </tex> будет зависеть от <tex> i </tex>.
+# Развернем все ребра: если работа <tex> i </tex> зависела от работы <tex> j </tex>, теперь работа <tex> j </tex> будет зависеть от <tex> i </tex>.
-* Заменим все стоимости <tex> w_i </tex> на противоположные <tex> w'_i = - w_i</tex>.
+# Заменим все стоимости <tex> w_i </tex> на противоположные <tex> w'_i = - w_i</tex>.
-{{Утверждение
+{{Теорема
 |statement=Развернутое оптимальное расписание соответствующей задачи <tex> S_{out} </tex> с весами <tex> w'_i </tex> является оптимальным расписанием для задачи  <tex> S_{in} </tex>
 |proof=
-Полученное расписание будет допустимым, так как расписание для <tex> S_{out} </tex> было допустимым, и в нем никакие две работы не пересекались и не прерывались. Развернув, мы не могли нарушить это свойство. Также из-за того, что мы развернули расписание, мы добились того, что все работы выполняются в правильном порядке (в расписании для <tex> S_{out} </tex> из-за того, что все ребра были развернуты, порядок был нарушен для всех работ). Таким образом, получили что расписание — допустимое.
+Полученное расписание будет допустимым, так как расписание для <tex> S_{out} </tex> было допустимым, и в нем никакие две работы не пересекались и не прерывались. Развернув ребра, мы не могли нарушить это свойство. Также из-за того, что мы развернули ребра в расписании, мы добились того, что все работы выполняются в правильном порядке (в расписании для <tex> S_{out} </tex> из-за того, что все ребра были развернуты, порядок был нарушен для всех работ). Таким образом получили, что расписание допустимое.
 Пусть с помощью задачи <tex> S_{out} </tex> мы получили последовательность работ <tex> 1 \dots n </tex>. Распишем по определению значение целевой функции для <tex> S_{out} </tex>:
-<tex>\sum -w_i C_i = \sum \limits_{i=1}^n ( -w_i \sum \limits_{j=1}^i p_j ) = \\
+<tex>
-\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 \left( -w_i C_i \right)
-\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>
+= \sum \limits_{i=1}^n \left( -w_i \sum \limits_{j=1}^i p_j \right) = \\
 Заметим, что первое слагаемое соответствует целевой функции <tex> \sum w_i C_i </tex> для последовательности <tex> n \dots 1 </tex>, а второе и третье слагаемые — константы, зависящие только от входных данных и не зависящие от перестановки работ. Таким образом, оптимальное значение для <tex> S_{out} </tex> также минимизирует <tex> S_{in} </tex>.
 }}
 == Источники информации ==
 * P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 73 - 78

@@ Строка 148: / Строка 148: @@
 * P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 73 - 78
-[[Категория: Дискретная математика и алгоритмы]]
+[[Категория: Алгоритмы и структуры данных]]
 [[Категория: Теория расписаний]]

@@ Строка 111: / Строка 111: @@
 Доказательство проведём по индукции. Очевидно, что для одной вершины алгоритм построит оптимальное расписание. Пусть теперь он может составить оптимальную последовательность назначенных работ числом меньше <tex> n </tex>. Пусть также работы <tex> i, j </tex> {{---}} работы, которые объединятся на первом шаге алгоритма. Тогда оптимальное расписание <tex> R </tex> можно представить следующим образом:
-<tex> \pi \colon \pi (1), ..., \pi (k), i, j, \pi (k + 3), ..., \pi (n) </tex>
+<tex> \pi \colon \pi (1), \ldots, \pi (k), i, j, \pi (k + 3), \ldots, \pi (n) </tex>
 После объединения работ <tex> i </tex> и <tex> j </tex> в одну расписание <tex> R' </tex> примет такой вид:
-<tex> \pi ' \colon \pi (1), ..., \pi (k), I, \pi (k + 3), ..., \pi (n) </tex>
+<tex> \pi ' \colon \pi (1), \ldots, \pi (k), I, \pi (k + 3), \ldots, \pi (n) </tex>
 где <tex> I = \{i, j\}, ~w(I) = w(i) + w(j), p(I) = p(i) + p(j)</tex>. Обозначим за <tex> f_n(\pi ), ~f_{n-1}(\pi ') </tex> целевые функции для последовательностей <tex> \pi </tex> и <tex> \pi ' </tex> соответственно. Тогда
@@ Строка 125: / Строка 125: @@
 Теперь разделим обе части равенства <tex> (*) </tex> на <tex> w(i)w(j) </tex>. Получим, что расстояние между целевыми функциями равно
-<tex dpi = 150> -\frac{p(j)}{w(j)} = -\frac{1}{q(j)} </tex>
+<tex> -\dfrac{p(j)}{w(j)} = -\dfrac{1}{q(j)} </tex>
 Это расстояние минимально (по модулю), так как мы выбирали работу <tex> j </tex> с максимальным значением <tex> q(j) </tex>. Из этих утверждений и следует оптимальность построенного алгоритмом расписания.

@@ Строка 72: / Строка 72: @@
 Детали описаны в алгоритме ниже, в котором
-* <tex> E(i) </tex> обозначает последнюю работу в последовательности <tex> \pi_i </tex>
+* <tex> E(i) </tex> обозначает последнюю работу в последовательности <tex> \pi_i </tex>,
 * <tex> P(i) </tex> обозначает предка в графе зависимостей, а после слияния с какой-то вершиной <tex> j </tex> {{---}} предыдущую работу в последовательности <tex> \pi_j </tex>.
@@ Строка 96: / Строка 96: @@
 После завершения этой процедуры оптимальное расписание можно восстановить с конца, зная <tex> E(root) </tex> и массив <tex> P </tex>.
-Если для получения работы <tex> j </tex> с минимальным значением <tex> q(j) </tex> использовать очередь с приоритетами, а для поиска родителям вершины использовать систему непересекающихся множеств, то время работы алгоритма будет <tex> O(n\log{n}) </tex>.
+Если для получения работы <tex> j </tex> с минимальным значением <tex> q(j) </tex> использовать очередь с приоритетами, а для поиска родителям вершины использовать систему непересекающихся множеств, то время работы алгоритма будет <tex> \mathcal{O}(n\log{n}) </tex>.
 Проиллюстрируем работу алгоритма на следующем примере.

@@ Строка 11: / Строка 11: @@
 Докажем некоторые свойства оптимального расписания, которые мы будем использовать в доказательстве корректности алгоритма.
-Введем некоторые обозначения для удобства. За <tex> 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>\mathrm{edges} </tex> обозначим список всех ребёр дерева. Для всех работ <tex>i = 1, \ldots, n</tex> обозначим за <tex>S(i)</tex> всех потомков <tex>i</tex> в дереве зависимостей, включая саму работу <tex>i</tex>, введём новый параметр работы <tex>q_i = \dfrac{w_i}{p_i}</tex>.
-Для подмножества работ <tex>I \subseteq \{1, ..., n\}</tex> определим:
+Для подмножества работ <tex>I \subseteq \{1, \ldots, n\}</tex> определим:
-<tex dpi = 150>w(I) = \sum\limits_{i \in I} w_i, p(I) = \sum\limits_{i \in I} p_i, q(I) = \frac{w(I)}{p(I)}</tex>
+<tex>w(I) = \sum\limits_{i \in I} w_i, p(I) = \sum\limits_{i \in I} p_i, q(I) = \dfrac{w(I)}{p(I)}</tex>
-Два непересекающихся множества работ <tex>I, J \subseteq \{1, ..., n\}</tex> будем называть ''параллельными'' <tex>(I \sim J)</tex>, если для всех <tex>i \in I, j \in J</tex> выполняется: <tex>i</tex> не является ни предком, ни потомком <tex>j</tex>. Если множества состоят из одной работы <tex>I = \{i\}, J = \{j\}</tex>, будем писать <tex>i \sim j</tex>. Каждое расписание представлено перестановкой <tex>\pi</tex>.
+Два непересекающихся множества работ <tex>I, J \subseteq \{1, \ldots, n\}</tex> будем называть '''параллельными''' <tex>(I \sim J)</tex>, если для всех <tex>i \in I, j \in J</tex> выполняется: <tex>i</tex> не является ни предком, ни потомком <tex>j</tex>. Если множества состоят из одной работы <tex>I = \{i\},\ J = \{j\}</tex>, будем писать <tex>i \sim j</tex>. Каждое расписание представлено перестановкой <tex>\pi</tex>.
 {{Лемма
 |id=lemma1
 |statement= Пусть <tex>\pi</tex> {{---}} оптимальное расписание, <tex>I</tex> и <tex>J</tex> {{---}} два таких параллельных блока (множества работ, выполняемых последовательно) из <tex>\pi</tex>, что <tex>J</tex> выполняется сразу после <tex>I</tex>. Пусть <tex>\pi'</tex> {{---}} расписание, полученное из <tex>\pi</tex> перестановкой <tex>I</tex> и <tex>J</tex>. Тогда выполяются следующие пункты:
-<tex>(a)~ I \sim J \Rightarrow q(I) \geqslant q(J)</tex>
+:<tex>(a)~ I \sim J \Rightarrow q(I) \geqslant q(J)</tex>
-<tex>(b)</tex> Если <tex>I \sim J</tex> и <tex>q(I) = q(J)</tex>, то <tex>\pi'</tex> {{---}} оптимальное расписание.
+:<tex>(b)</tex> Если <tex>I \sim J</tex> и <tex>q(I) = q(J)</tex>, то <tex>\pi'</tex> {{---}} оптимальное расписание.
 |proof=
-<tex>(a)</tex> Пусть <tex>f = \sum w_i C_i</tex>. Так как <tex>\pi</tex> {{---}} оптимальное расписание, то <tex>f(\pi) \leqslant f(\pi')</tex>. Таким образом:
+<tex>(a)</tex>
-<tex>0 \leqslant f(\pi') - f(\pi) = w(I) p(J) - w(J) p(I)</tex>
+:Пусть <tex>f = \sum w_i C_i</tex>. Так как <tex>\pi</tex> {{---}} оптимальное расписание, то <tex>f(\pi) \leqslant f(\pi')</tex>. Таким образом:
-Поделим на <tex>p(I)p(J)</tex>:
+:<tex>0 \leqslant f(\pi') - f(\pi) = w(I) p(J) - w(J) p(I)</tex>
-<tex dpi = 150>q(I) = \frac{w(I)}{p(I)} \geqslant \frac{w(J)}{p(J)} = q(J) </tex>
+:Поделим на <tex>p(I)p(J)</tex>:
-<tex>(b)</tex> Если <tex>q(I) = q(J) </tex>, то <tex>f(\pi) = f(\pi') </tex>, следовательно расписание <tex>\pi'</tex> оптимально.
+:<tex>q(I) = \dfrac{w(I)}{p(I)} \geqslant \dfrac{w(J)}{p(J)} = q(J) </tex>
 }}
 {{Теорема
 |id = theorem1
-|statement = Пусть <tex>i, ~j</tex> работы такие, что <tex>i</tex> {{---}} предок <tex>j</tex>, и <tex> q_j = \max \{q_k \mid ~ (i, k) \in edges \}</tex>. <br>
+|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 =
@@ Строка 49: / Строка 53: @@
 '''Случай 1''': <tex> k \in S(i) </tex>
-Работа <tex> j </tex> не является потомком работы <tex> k </tex> , иначе у неё было бы <tex>2</tex> предка. Следовательно, <tex> k \sim j </tex>. По [[#lemma1 | лемме]] <tex> q(k) \geqslant q(j) </tex>, а по условию выбора <tex> j </tex> имеем <tex> q(j) \geqslant q(k) </tex>, значит, <tex> q(j) = q(k) </tex>. Опять же из [[#lemma1 | леммы]] следует, что работы <tex> k </tex> и <tex> j </tex> можно поменять местами, не ухудшив расписание. Это противоречит тому, что мы выбрали минимальное <tex> l </tex>.
+:Работа <tex> j </tex> не является потомком работы <tex> k </tex> , иначе у неё было бы <tex>2</tex> предка. Следовательно, <tex> k \sim j </tex>. По [[#lemma1 | лемме]] <tex> q(k) \geqslant q(j) </tex>, а по условию выбора <tex> j </tex> имеем <tex> q(j) \geqslant q(k) </tex>, значит, <tex> q(j) = q(k) </tex>. Опять же из [[#lemma1 | леммы]] следует, что работы <tex> k </tex> и <tex> j </tex> можно поменять местами, не ухудшив расписание. Это противоречит тому, что мы выбрали минимальное <tex> l </tex>.
 '''Случай 2''': <tex> k \not\in S(i) </tex>
-Пусть <tex> h </tex> будет последней работой в расписании между <tex> i </tex> и <tex> j </tex> <tex> ( </tex>включая работу <tex> i) </tex>, которая принадлежит <tex> S(i) </tex>, то есть для всех работ <tex> r </tex> в множестве <tex> K </tex>, назначенных между <tex> h </tex> и <tex> j </tex>, имеем, что <tex> r \not\in S(i) </tex>. Так как наш [[Основные определения теории графов | граф]] зависимостей работ является исходящим деревом и  <tex>(i, j) \in edges </tex>, то любой предок работы <tex> j </tex> также является и предком работы <tex> i </tex>. Поэтому никакая работа из <tex> K </tex> не является предком <tex> j </tex> <tex>(</tex>иначе бы она не смогла стоять после <tex> i) </tex> или потомком, значит, <tex> K \sim j </tex>. Из этого следует, что <tex> q(K) \geqslant q(j) </tex>.
+:Пусть <tex> h </tex> будет последней работой в расписании между <tex> i </tex> и <tex> j\ ( </tex>включая работу <tex> i) </tex>, которая принадлежит <tex> S(i) </tex>, то есть для всех работ <tex> r </tex> в множестве <tex> K </tex>, назначенных между <tex> h </tex> и <tex> j </tex>, имеем, что <tex> r \not\in S(i) </tex>. Так как наш [[Основные определения теории графов | граф]] зависимостей работ является исходящим деревом и  <tex>(i, j) \in \mathrm{edges} </tex>, то любой предок работы <tex> j </tex> также является и предком работы <tex> i </tex>. Поэтому никакая работа из <tex> K </tex> не является предком <tex> j\ (</tex>иначе бы она не смогла стоять после <tex> i) </tex> или потомком, значит, <tex> K \sim j </tex>. Из этого следует, что <tex> q(K) \geqslant q(j) </tex>.
-Работа <tex> h \in S(i) </tex> не является потомком какой-либо работы <tex> r \in K </tex>. В противном же случае получалось, что <tex> r \in S(i) </tex>, значит, <tex> h </tex> является не последней работой из <tex> S(i) </tex> между <tex> i </tex> и <tex> j </tex>. Поэтому <tex> h \sim K </tex>, откуда тут же следует, что <tex> q(h) \geqslant q(K) \geqslant q(j) </tex>. По определению <tex> j </tex> имеем, что <tex> q(j) \geqslant q(h) </tex>, следовательно <tex> q(j) = q(h) = q(K) </tex>. По [[#lemma1 | лемме]] мы можем поменять блоки <tex> K </tex> и <tex> j </tex> не нарушив оптимальности расписания.
+:Работа <tex> h \in S(i) </tex> не является потомком какой-либо работы <tex> r \in K </tex>. В противном же случае получалось, что <tex> r \in S(i) </tex>, значит, <tex> h </tex> является не последней работой из <tex> S(i) </tex> между <tex> i </tex> и <tex> j </tex>. Поэтому <tex> h \sim K </tex>, откуда тут же следует, что <tex> q(h) \geqslant q(K) \geqslant q(j) </tex>. По определению <tex> j </tex> имеем, что <tex> q(j) \geqslant q(h) </tex>, следовательно <tex> q(j) = q(h) = q(K) </tex>. По [[#lemma1 | лемме]] мы можем поменять блоки <tex> K </tex> и <tex> j </tex> не нарушив оптимальности расписания.
 Таким образом мы можем менять соседние работы или блоки работ, пока <tex> j </tex> не окажется сразу за <tex> i </tex>.

@@ Строка 3: / Строка 3: @@
 {{Задача
 |definition=
-Необходимо составить расписание на одном станке работ с произвольными временами выполнения. Минимизировать нужно взвешенную сумму времен завершения работ. Зависимости между работами заданы исходящим [[Дерево, эквивалентные определения | деревом]] {{---}} работа, которая соответствует корню, доступна в начале, все другие работы зависят от одной работы {{---}} отца в дереве. Тривиальным примером подобной задачи является демонтаж сложного механизма.
+Необходимо составить расписание на одном станке работ с произвольными временами выполнения. Минимизировать нужно взвешенную сумму времен завершения работ. Зависимости между работами заданы исходящим [[Дерево, эквивалентные определения | деревом]] {{---}} работа, которая соответствует корню, доступна в начале, все другие работы зависят от одной работы {{---}} отца в дереве.
 }}
 == Свойства оптимального расписания ==