'''Алгоритм Джонсона''' <tex dpi = "200"> 1 \mid prec,pmtn,r_i \mid f_{max}</tex> {{Задача|definition = <wikitex>Дано $n$ работ, которые надо выполнить на одной машине, причем $i$-ая работа выполняется $p_i$ времени. Для каждой работы задана монотонно неубывающая функция $f_i$. Работы можно прерывать, у каждой работы есть время появления $r_{i}$. Также между работами заданы отношения в виде ориентированного графа без циклов: если существует ребро $a \to b$, то работа $a$ должна завершиться до начала выполнения работы $b$. Необходимо построить такое расписание, чтобы величина $f_{max} = \max\limits_{j=1..n}{f_j(англC_j)}$, где $C_j$ {{---}} время окончания выполнения $j$-ой работы, была минимальна. ''Johnson's algorithm'') находит кратчайшие пути между всеми парами вершин во взвешенном ориентированном графе с любыми весами ребер</wikitex>}} Задача <tex> 1 \mid prec, pmtn, r_i \mid f_{max} </tex> является обобщением [[Правило Лаулера|<tex>1 \mid prec \mid f_{max}</tex>]], но не имеющем отрицательных цикловздесь у работ также есть времена появления, раньше которых их делать запрещено, и их можно прерывать.
== Алгоритм ==
Работу будем обозначать просто ее номером (<tex> i </tex>), при этом, номера работ могут меняться в зависимости от того, по какому параметру они отсортированы. Время появления работы — <tex> r[i]</tex>, время, требуемое для ее выполнения — <tex> p[i] </tex>. Множество ребер графа обозначается как <tex> E </tex>.
=== Описание Modify ===Для начала, модифицируем времена появления работ. Если работа <tex> j </tex> зависит от <tex> i </tex>, то, очевидно, она не может быть начата раньше, чем закончится выполнение <tex> i </tex>, поэтому нужно заменить <tex> r_j </tex> на <tex> \max(r_j, r_i + p_i) </tex>. Алгоритм, делающий это, представлен ниже (работы рассматриваются в порядке топологической сортировки):
Алгоритм Джонсона позволяет найти кратчайшие пути между всеми парами вершин в течение времени Modify() '''for''' i = 1 '''to''' n '''for''' j: ij <tex> O(V^2\log(V) + VE) in E </tex>. Для разреженных графов этот алгоритм ведет себя асимптотически быстрее r[j] = max(r[Алгоритм Флойда|алгоритма Флойдаj], r[i] + p[i]. Этот алгоритм либо возвращает матрицу кратчайших расстояний между всеми парами вершин, либо сообщение о том, что в графе существует цикл отрицательной длины.)
В этом алгоритме используется метод '''изменения веса''' (англ. ''reweighting''). Суть его заключается в том, что После выполнения этого алгоритма для заданного графа любых двух работ <tex> G i, j </tex> строится новая весовая функция , таких, что <tex> \omega_\varphi j </tex>, неотрицательная для всех ребер графа зависит от <tex> G i </tex> и сохраняющая кратчайшие пути. Такая весовая функция строится с помощью так называемой , выполняется <tex> r[j] > r[Амортизационный_анализ#.D0.9C.D0.B5.D1.82.D0.BE.D0.B4_.D0.BF.D0.BE.D1.82.D0.B5.D0.BD.D1.86.D0.B8.D0.B0.D0.BB.D0.BE.D0.B2|потенциальнойi]] функции</tex>, поэтому, при рассмотрении работ в порядке неубывания времен их появления, они также будут топологически отсортированы.
Пусть <tex> \varphi : V \rightarrow \mathbb R </tex> — произвольное отображение из множества вершин === Blocks ===Здесь и далее считается, что работы отсортированы в вещественные числа. Тогда новой весовой функцией будет порядке неубывания модифицированных <tex> \omega_\varphi(u, v) = \omega(u, v) + \varphi(u) - \varphi(v) r_i </tex>.
Такая потенциальная функция строится при помощи добавлении фиктивной вершины Станок, выполняющий работы, выполняет работу в <tex> G </tex>, из которой проведены ребра нулевого веса во все остальные вершины некоторые интервалы времени и запуском [[Алгоритм Форда-Беллмана|алгоритма Форда-Беллмана]] из неепростаивает в остальное время. На этом же этапе мы сможем обнаружить наличие отрицательного цикла в графеСледующий алгоритм разбивает множество работ на блоки, внутри которых станок работает без простоя.
Теперь, когда мы знаем, что веса всех ребер неотрицательны, и кратчайшие пути сохранятся, можно запустить Blocks(<tex> \{ 1 \ldots n \} </tex>) j = 0 t = 0 '''for''' i = 1 '''to''' n '''if''' <tex> t < r[i] </tex> t = r[Алгоритм Дейкстры|алгоритм Дейкстрыi] j = j + 1 B[j] из каждой вершины и таким образом найти кратчайшие расстояния между всеми парами вершин.add(i) t = t + p[i] '''return''' B
=== Сохранение кратчайших путей ===УтверждаетсяЕсли алгоритм Blocks вызывается от пустого множества, то считаем, что если какой-то путь он возвращает также пустое множество. Определим время начала блока <tex> P B_j </tex> был кратчайшим относительно весовой функции как <tex> s_j = \min\limits_{i \omega in B_j} r_i </tex>, то он будет кратчайшим и относительно новой весовой функции а время конца — как <tex> e_j = s_j + \sum\omega_limits_{i \varphi in B_j} p_i </tex>.
{{Лемма
|statement=
Пусть Существует оптимальное расписание, такое, что все во все временные интервалы <tex>P,\[s_j; Q e_j] </tex> {{---}} два пути , соответствующие блокам <tex> a \rightsquigarrow b\;B_j </tex> и <tex>\omega(P) < \omega(Q), построенным алгоритмом Blocks, станок работает без простоя.</tex> Тогда <tex>\forall \varphi: \; \omega_\varphi(P) < \omega_\varphi(Q)</tex>
|proof=
Возьмем произвольное оптимальное расписание <tex> S </tex>, в нем деление на блоки может также быть произвольным. Найдем первый такой временной интервал <tex> [s_j; e_j] </tex>, что в <tex> S </tex> есть период простоя внутри <tex> [s_j; e_j] </tex> (если таких периодов несколько, будем рассматривать первый из них). Обозначим его за <tex> [s; e] </tex>.
:Рассмотрим путь Возьмем некоторую работу <tex>P: i </tex>, такую, что она начинается позже, чем в момент времени <tex> s </tex>, не имеет в графе зависимостей предков, завершаемых позже, чем в момент <tex> s </tex> и <tex> r_i \;u_0 le s </tex>. Такая работа обязательно существует, иначе для множества работ, выполняемых позже, чем в момент <tex> s </tex>, было бы <tex> r = \rightarrow u_1 min\rightarrow u_2 limits_{k \rightarrow \ldots \rightarrow u_k in T} r_k > s </tex>, и внутри блока <tex> B_j </tex> был бы простой <tex> [s_j; r] </tex>, что невозможно по построению алгоритма Blocks. Очевидно, мы можем начать выполнять ее в момент времени <tex> s </tex> и полностью, либо частично заполнить простой <tex> [s; e] </tex>; так как <tex> f_i </tex>— неубывающая функция, то ответ останется оптимальным. Повторяя этот процесс, мы за конечное число шагов придем к оптимальному расписанию с требуемым свойством.}}
=== Decompose ===Допустим, у нас есть блок работ, который можно выполнить без прерываний. Общая идея алгоритма Decompose следующая:Его вес найдем работу <tex> i </tex>, которую выгоднее всего выполнить последней. Разобъем оставшееся множество работ на блоки, решим задачу для этих блоков рекурсивно и вставим <tex> i </tex> в промежутки между ними, до них и после них, начиная с новой весовой функцией равен <tex>\omega_\varphir_i </tex>. Псевдокод этого алгоритма представлен ниже. Decompose(B) find <tex> l: f[l](Pe) = \omega_min \varphi{f[j](u_0u_1e) + \omega_mid j \varphi(u_1u_2) + in B, \ldots + overline\omega_exists\varphi(u_{k-1: jk \in E \}u_k</tex> ans = f[l](e) G = Blocks(<tex> B \setminus l </tex>) вставить l в промежутки между блоками G, начиная с <tex> r_l </tex> '''for''' B[j] <tex>\in</tex> G ans = max(ans, Decompose(B[j])) '''return''' ans {{Теорема|statement=Расписание для блока, построенное алгоритмом Decompose, является корректным и оптимальным.|proof=Докажем сначала корректность.
:Вставим определение функции Убедимся, что порядок выполнения работ, заданный графом зависимостей, не нарушается. Заметим, что в разбиении <tex> B \omega_\varphi : \omega_\varphi(P) = \varphi(u_0) + \omega(u_0u_1) - \varphi(u_1) + \ldots + \varphi(u_{k-1}) + \omega(u_{k-1}u_k) - \varphi(u_k) setminus l </tex> на блоки существует не более одного блока <tex> B_0 </tex>, расположенного до момента времени <tex> r_l </tex> — иначе после вставки <tex> l </tex> в промежутки между блоками, <tex> B </tex> выполнялся бы с прерываниями. Далее, заметим, что все интервалы времени, на которые назначается работа из блока <tex> B_j </tex>, находятся внутри интервала <tex> [s_j; e_j] </tex>; это относится и к блоку <tex> B_0 </tex>. Из этих двух наблюдений, а также того, что все работы со временами появления меньше, чем <tex> r_l </tex>, будут помещены в блок <tex> B_0 </tex>, следует, что порядок выполнения будет правильным.
:ЗаметимТакже для корректности требуется, что потенциалы все промежуточных вершин чтобы работы выполнялись не раньше, чем они появляются. Так как время выполнения работы определяется только в пути сократятсястроке 4 алгоритма, которая соответствует этому требованию, то условие выполняется. <tex> \omega_\varphi(P) = \varphi(u_0) + \omega(P) - \varphi(u_k)</tex>
:По изначальному предположению: Найдем теперь нижнюю оценку на <tex>\omegaf_{max} </tex>. Пусть <tex> f_{max}(PJ) < \omega(Q)/tex> — ответ для множества работ <tex> J </tex>. С новой весовой функцией веса соответствующих путей будут:
:Очевидно, для любой работы <tex>j \omega_\varphiin J </tex> выполняется <tex> f_{max}(PJ) = \varphige f_{max}(aJ \setminus j) + \omega</tex>, значит, <tex> f_{max}(PJ) - \varphige \max\limits_{j \in J} f_{max}(bJ \setminus j)</tex>.
:Также, так как в оптимальном решении какая-то работа без потомков обязательно заканчивается в блоке <tex>\omega_\varphi(Q) = \varphi(a) + \omegaB </tex>, то <tex> f_{max}(QJ) - \varphige f_l(be)</tex>.
:Отсюда, следует <tex>f_{max}(J) \omega_ge \varphimax(Pf_l(e) < , \max\omega_limits_{j \varphiin J} f_{max}(QJ \setminus j))</tex>. По псевдокоду алгоритма видно, что его ответ достигает этой нижней оценки.
}}
=== Теорема о существовании потенциальной функции Общий алгоритм ==={{Теорема|statement=
В графе <tex>G</tex> нет отрицательных циклов <tex>\Leftrightarrow</tex> существует потенциальная функция <tex> \phi:\; \forall uv \in E\; \omega_\varphiВыполним Modify, после чего разобъем все множество работ на блоки и для каждого блока запустим Decompose(uv) \geqslant 0 </tex>:
|proof MakeSchedule() Modify() B = Blocks(<tex> \{1 \ldots n \} </tex>) ans = <tex> -\infty </tex> '''for''' B[j] <tex>\in</tex> B ans = max(ans, Decompose(B[j])) '''return''' ans
Из доказанной ранее леммы следует, что <tex>f_{max}(\Leftarrow </tex>: Рассмотрим произвольный <tex>C</tex> — цикл в графе <tex>G{ 1 \ldots n \}) = \max\limits_{j} f_{max}(B_j) </tex>, поэтому расписание для всего множества работ, поделенного на блоки, также будет оптимальным и корректным.
:По лемме, его вес равен == Время работы =={{Теорема|statement=Время работы алгоритма MakeSchedule — <tex> \omegaO(Cn^2) </tex> операций.|proof= \omega_\varphi(C) - \varphi(u_0) - \varphi(u_0) = \omega_\varphiОбозначим за <tex> P(Cn) \geqslant 0</tex>время, необходимое для выполнения алгоритма MakeSchedule на n работах. Очевидно, для корректно определенной функции P в силу структуры алгоритма должно выполняться неравенство:
<tex>P(n) \Rightarrow </tex>: Добавим фиктивную вершину <tex>s</tex> в граф, а также ребра <tex> s ge сn + \sum\to u </tex> весом <tex> 0 </tex> для всех <tex> u limits_{i = 1}^{k} P(n_i) </tex>.
:Обозначим Здесь <tex>\delta(u,v)n_i </tex> как минимальное расстояние между вершинами - размер блока с номером <tex>u,\; vi </tex>, введем потенциальную функцию построенного алгоритмом Blocks(). Заметим, что <tex> \phi sum\limits_{i = 1}^{k} n_i = n - 1</tex>.
: Если <tex>\phiP(un) = \delta(s,u)an^2 </tex>, то имеем:
:Рассмотрим вес произвольного ребра <tex> uv an^2 \in E </tex>: <tex>\omega_\phi(uv) = \phi(u) ge cn + a \omega(uv) - sum\phi(v) limits_{i = \delta(s, u) + \omega(uv) - \delta(s, v)1}^{k} n_i^2 </tex>.
:Поскольку Так как <tex>\deltan^2 > (s, un - 1) + ^2 = (\sum\omega(uv) </tex> limits_{i = 1}^{---k}} вес какого-то пути <tex> s n_i)^2 = \rightsquigarrow v </tex>, а <tex> sum\delta(s, v) </tex> limits_{i = 1}^{---k}} вес кратчайшего пути <tex> s \rightsquigarrow v</tex>, то <tex> \delta(s, u) n_i^2 + 2\omega(uv) sum\geqslant limits_{\delta(ssubstack{i, v) \Rightarrow \delta(s, u) + \omega(uv) - \delta(s, v) j = 1\omega_\varphi(uv) i \geqslant 0 ne j}}^{k} n_i n_j </tex>., то можно переписать неравенство в следующем виде:
<tex> 2a \sum\limits_{\substack{i, j = 1\\ i \ne j}}^{k} n_i n_j \ge cn </tex>
Чтобы получить максимальную нижнюю оценку на <tex> a </tex>, оценим снизу <tex> \sum\limits_{i, j === Псевдокод ===1}^{k} n_i n_j </tex>:
Предварительно построим граф <tex>G' = (V',\;E')</tex>sum\limits_{\substack{i, где <tex>V' j = V 1\\cup i \ne j}}^{s\k}</tex>, <tex>s n_i n_j \notge \in V</tex>, а <tex>E' = E sum\cup limits_{\substack{(si,\;v): \omega(s, v) j = 0,1\ v \in V i \ne j}}^{k}</tex> '''function''' Johnson(G): '''int[][]''' '''if''' BellmanFord<tex>(G',1 \;\omega,\;s)</tex> cdot n_j == ''false'' print "Входной граф содержит цикл с отрицательным весом" '''return''' <tex>\varnothing</tex> '''else''' '''for''' <tex>v sum\in V'</tex> <tex>\varphi(v)</tex> limits_{j = <tex>\delta1}^{k} (s,\;v)</tex> <font color = green>// <tex>\delta(s,\;v)</tex> вычислено алгоритмом Беллмана — Форда</font> '''for''' <tex>(u,\;vk - 1) \in E'</tex> <tex>\omega_\varphi(u,\;v)</tex> n_j = <tex> \omega(u,\;vk - 1) + \varphi(u) n - \varphi(v1)</tex> '''for''' <tex>u \in V</tex> Dijkstra<tex>(G,ge \;\omega_\varphi,\;u)</tex> '''for''' <tex>v \in V</tex> <tex>d_cfrac{nk}{uv4} \leftarrow \delta_\varphi(u,\;v) + \varphi(v) - \varphi(u)</tex> '''return''' <tex>d</tex>
ИтогоЗначит, в начале алгоритм Форда-Беллмана либо строит потенциальную функцию такую, что после перевзвешивания все веса ребер будут неотрицательны, либо выдает сообщение о том, что в графе присутствует отрицательный циклпри <tex> a \ge \cfrac{cn}{2} \cfrac{4}{nk} = \cfrac{2c}{k} </tex> требуемое неравенство будет выполняться.
Затем из каждой вершины запускается алгоритм Дейкстры для составления искомой матрицы. Так как все веса ребер теперь неотрицательны, алгоритм Дейкстры будет работать корректно. А поскольку перевзвешивание таково, что кратчайшие пути относительно обеих весовых функций совпадают, алгоритм Джонсона в итоге корректно найдет все кратчайшие пути между всеми парами вершин. == Сложность ==Алгоритм Джонсона работает за <tex>O(VE + VD)</tex>, где <tex>O(D)</tex> — время работы [[Алгоритм Дейкстры| алгоритма Дейкстры]]. Если в алгоритме Дейкстры неубывающая очередь с приоритетами реализована в виде [[Фибоначчиевы кучи| фибоначчиевой кучи]], то время работы алгоритма Джонсона есть <tex>O(V^2\log V + V E)</tex>. В случае реализации очереди с приоритетами в виде двоичной кучи время работы равно <tex>O(V E \log V)</tex>. == См. также ==* [[Алгоритм Дейкстры]]* [[Алгоритм Форда-Беллмана]]* [[Алгоритм Флойда]]}}
== Источники информации ==* ''Кормен ТPeter Brucker.«Scheduling Algorithms» {{---}} «Springer», Лейзерсон Ч2006 г., Ривест Р{{---}} 379 стр.'' Алгоритмы: построение и анализ. 2{{---}} ISBN 978-3-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.* [http://rain.ifmo.ru/cat/view.php/vis/graph540-paths/johnson69515-2001 Визуализатор алгоритма]8
[[Категория: Алгоритмы Дискретная математика и структуры данныхалгоритмы]][[Категория: Кратчайшие пути в графах Теория расписаний]]
