81
правка
Изменения
м
'''Алгоритм Джонсона''' находит кратчайшие пути <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$-ой работы, была минимальна. ''All Pairs Shortest Path'') во взвешенном ориентированном графе с любыми весами ребер</wikitex>}} Задача <tex> 1 \mid prec, pmtn, r_i \mid f_{max} </tex> является обобщением [[Правило Лаулера|<tex>1 \mid prec \mid f_{max}</tex>]], но не имеющем отрицательных цикловздесь у работ также есть времена появления, раньше которых их делать запрещено, и их можно прерывать.
Алгоритм Джонсона позволяет найти кратчайшие пути между всеми парами вершин в течение времени '''int[]''' modify('''int''' jobs[n]): rm = copy(r) '''for''' u = 1 '''to''' n '''for''' (u, v) <tex> O(V^2\log(V) + VE) in </tex>. Для разреженных графов этот алгоритм ведет себя асимптотически быстрее E rm[v] = max(rm[Алгоритм Флойда|алгоритма Флойдаv], rm[u]. Этот алгоритм либо возвращает матрицу кратчайших расстояний между всеми парами вершин, либо сообщение о том, что в графе существует цикл отрицательной длины.+ p[u]) '''return''' rm
В этом алгоритме используется метод '''изменения веса''' (англ. ''reweighting''). Суть его заключается в том, что После выполнения этого алгоритма для заданного графа любых двух работ <tex> G i, j </tex> строится новая весовая функция , таких, что <tex> \omega_\varphi j </tex>, неотрицательная для всех ребер графа зависит от <tex> G i </tex> и сохраняющая кратчайшие пути. Такая весовая функция строится с помощью так называемой , выполняется <tex> rm[j] > rm[Амортизационный_анализ#.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> — произвольное отображение из множества вершин === Разбиение на блоки ===Здесь и далее считается, что работы отсортированы в вещественные числа. Тогда новой весовой функцией будет порядке неубывания модифицированных <tex> \omega_\varphi(u, v) = \omega(u, v) + \varphi(u) - \varphi(v) rm_i </tex>.
Такая потенциальная функция строится при помощи добавлении фиктивной вершины Станок, выполняющий работы, выполняет работу в <tex> G </tex>, из которой проведены ребра нулевого веса во все остальные вершины некоторые интервалы времени и запуском [[Алгоритм Форда-Беллмана|алгоритма Форда — Беллмана]] из неепростаивает в остальное время. На этом же этапе мы сможем обнаружить наличие отрицательного цикла в графеСледующий алгоритм разбивает множество работ на блоки, внутри которых станок работает без простоя.
Теперь'''Структура блока''' '''struct''' Block '''int''' start <font color = "darkgreen">// Время начала выполнения блока</font> '''int''' time <font color = "darkgreen">// Время, когда мы знаем, что веса всех ребер неотрицательны, и кратчайшие пути сохранятся, можно запустить затрачиваемое на соответствующий блок</font> '''int''' end <font color = "darkgreen"> // Время конца выполнения блока </font> '''int[]''' jobs <font color = "darkgreen">// Номера работ</font> '''void''' add() <font color = "darkgreen">// Добавляет работу в конец jobs[Алгоритм Дейкстры|алгоритм Дейкстры]] из каждой вершины и таким образом найти кратчайшие расстояния между всеми парами вершин.</font>
Пусть <tex>PСуществует оптимальное расписание, такое,\; Q что все во все временные интервалы </tex> {{---}} два пути <tex> a \rightsquigarrow b\[s_j;e_j] </tex> и , соответствующие блокам <tex>\omega(P) < \omega(Q).B_j </tex> Тогда , построенным алгоритмом <tex>\forall \varphi: \; \omega_\varphi(P) < \omega_\varphi(Q)mathrm{Blocks}</tex> , станок работает без простоя.
:Рассмотрим путь Возьмем некоторую работу <tex>P: i </tex>, такую, что она начинается позже, чем в момент времени <tex> s </tex>, не имеет в графе зависимостей предков, завершаемых позже, чем в момент <tex> s </tex> и <tex> rm_i \;u_0 leqslant s </tex>. Такая работа обязательно существует, иначе для множества работ, выполняемых позже, чем в момент <tex> s </tex>, было бы <tex> r = \rightarrow u_1 min\rightarrow u_2 limits_{k \rightarrow \ldots \rightarrow u_k in T} rm_k > s </tex>, и внутри блока <tex> B_j </tex> был бы простой <tex> [s_j; r] </tex>, что невозможно по построению алгоритма Blocks. Очевидно, мы можем начать выполнять ее в момент времени <tex> s </tex> и полностью, либо частично заполнить простой <tex> [s; e] </tex>; так как <tex> f_i </tex>— неубывающая функция, то ответ останется оптимальным. Повторяя этот процесс, мы за конечное число шагов придем к оптимальному расписанию с требуемым свойством.}}
:Вставим определение функции '''<tex> \omega_langle</tex>int, int[]<tex>\varphi rangle</tex>''' decompose('''Block''' b, '''int[]''' schedule): \omega_\varphi '''int''' e = b.end <font color = "darkgreen"> // e — время завершения работ блока B</font> find l: f[l](Pe) = <tex> \min \varphi{f[j](u_0e) + \omegamid j \in B, \overline\exists\ k: jk \in E \} </tex> '''int''' ans = f[l](u_0u_1e) - \varphi b.jobs.remove(u_1l) + \ldots + \varphi '''Block[]''' g = blocks(u_{kb.jobs.p, b.jobs.rm) '''for''' i = 2 '''to''' g.size schedule[g[i-1].end .. g[i].begin -1}) + \omega(u_{k] = l<font color = "darkgreen"> // Вставляем работу в расписание между блоками</font> schedule[b.start .. g[1].start -1}u_k) ] = l <font color = "darkgreen"> // Нужно учесть пропуски перед первым и </font> schedule[g[g.size].end .. b.end - 1] = l <font color = "darkgreen"> // после последнего блоков соответственно</font> '''for''' b <tex>\varphiin</tex> g ans = max(ans, decompose(u_kb, schedule).first) '''return''' <tex>\langle</tex>ans, schedule<tex>\rangle</tex> {{Теорема|statement=Расписание для блока, построенное алгоритмом <tex>\mathrm{Decompose}</tex>, является корректным и оптимальным.|proof=Докажем сначала корректность.
:Убедимся, что порядок выполнения работ, заданный графом зависимостей, не нарушается. Заметим, что потенциалы в разбиении <tex> B \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> rm_l </tex>, будут помещены в пути сократятся. блок <tex> \omega_\varphi(P) = \varphi(u_0) + \omega(P) - \varphi(u_k)B_0 </tex>, следует, что порядок выполнения будет правильным.
:По изначальному предположению: <tex>\omega(P) < \omega(Q)</tex>Также для корректности требуется, чтобы работы выполнялись не раньше, чем они появляются. Так как время выполнения работы определяется в строках 5-9 алгоритма, которые соответствуют этому требованию, то условие выполняется. С новой весовой функцией веса соответствующих путей будут:
:Найдем теперь нижнюю оценку на <tex>\omega_\varphif_{max} </tex>. Пусть <tex> f_{max}(P) = \varphi(a) + \omega(P) - \varphi(bJ)</tex>— ответ для множества работ <tex> J </tex>.
:Очевидно, для любой работы <tex>j \omega_\varphiin J </tex> выполняется <tex> f_{max}(QJ) = \varphigeqslant f_{max}(aJ \setminus j) + \omega</tex>, значит, <tex> f_{max}(QJ) - \varphigeqslant \max\limits_{j \in J} f_{max}(bJ \setminus j)</tex>.
:Также, так как в оптимальном решении какая-то работа без потомков обязательно заканчивается в блоке <tex> B </tex>, то <tex> f_{max}(J) \geqslant f_l(e) </tex>. Отсюда, следует <tex>f_{max}(J) \omega_geqslant \varphimax(Pf_l(e) < , \max\omega_limits_{j \varphiin J} f_{max}(QJ \setminus j))</tex>. По псевдокоду алгоритма видно, что его ответ достигает этой нижней оценки.
В графе Выполним <tex>G\mathrm{Modify}</tex> нет отрицательных циклов , после чего разобъем все множество работ на блоки и для каждого блока запустим <tex>\Leftrightarrowmathrm{Decompose}</tex> существует потенциальная функция <tex> \phi:\; \forall uv \in E\; \omega_\varphi(uv) \geqslant 0 </tex>
|proof <tex>\langle</tex>'''int''', '''int[]'''<tex>\rangle</tex> makeSchedule('''int[]''' jobs): '''int'''[] schedule <font color="darkgreen">// Расписание работ</font> jobs = topSort(jobs) '''int[]''' rm = modify(jobs) ''sort jobs by'' rm ''values'' '''Blocks[]''' b = blocks(jobs.p, rm) '''int''' ans = <tex> -\infty </tex> '''for''' block <tex>\in</tex> b ans = max(ans, decompose(block,schedule).first) '''return''' <tex>\langle</tex>ans, schedule<tex>\rangle</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>\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) geqslant 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 = \omegaBig(uv) </tex> \sum\limits_{i = 1}^{---k}} вес какого-то пути <tex> s n_i\Big)^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>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 \notgeqslant \in V</tex>, а <tex>E' = E sum\cup limits_{\substack{(s,\;v): \omega(si, v) j = 0,1\ v \in V i \ne j}}^{k}</tex> '''function''' Johnson(G): '''int[][]''' '''if''' Bellman_Ford<tex>(G',1 \;\omega,\;s)</tex> cdot n_j == FALSE '''then''' print "Входной граф содержит цикл с отрицательным весом" '''else''' '''for''' <tex>v \in V'</tex> <tex>sum\varphi(v)</tex> limits_{j = <tex>\delta1}^{k} (s,\;vk - 1)</tex> <font color n_j = green>//<tex>\delta(s,\;vk - 1)</tex> вычислено алгоритмом Беллмана — Форда</font> '''for''' <tex>(u,\;v) \in E'</tex> <tex>\omega_\varphi(u,\;v)</tex> = <tex> \omega(u,\;v) + \varphi(u) n - \varphi(v1)</tex> '''for''' <tex>u \in V</tex> Dijkstra<tex>(G,geqslant \;\omega_\varphi,\;u)</tex> '''for''' <tex>v \in V</tex> <tex>d_dfrac{nk}{uv4} \leftarrow \delta_\varphi(u,\;v) + \varphi(v) - \varphi(u)</tex> '''return''' <tex>d</tex>
ИтогоЗначит, в начале алгоритм Форда — Беллмана либо строит потенциальную функцию такую, что после перевзвешивания все веса ребер будут неотрицательны, либо выдает сообщение о том, что в графе присутствует отрицательный циклпри <tex> a \geqslant \dfrac{cn}{2} \cdot \dfrac{4}{nk} = \dfrac{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>.}}
→Декомпозиция
== Алгоритм ==
Работу будем обозначать просто ее номером <tex>(i)</tex>, при этом, номера работ могут меняться в зависимости от того, по какому параметру они отсортированы. Время появления работы — <tex> r[i]</tex>, время, требуемое для ее выполнения — <tex> p[i] </tex>. Множество ребер графа обозначается как <tex> E </tex>.
===Идея алгоритма===
Будем решать задачу рекурсивно. Разобьем множество работ на подмножества (блоки), внутри которых не будет перерыва между выполнением работ. После этого для каждого из блоков найдем работу, которую выгоднее всего выполнить последней, удалим работу из соответствующего блока и повторим разбиение на подблоки для оставшихся работ. Пустые промежутки между подблоками, полученными из данного блока, заполним выбранной работой. Повторим рекурсивно для каждого из полученных подблоков. Как будет показано далее, данный алгоритм строит корректное и оптимальное расписание. Можно заметить, что если на каждом этапе будет получаться всего один блок, алгоритм выродится в [[Правило_Лаулера|алгоритм Лаулера]].
=== Описание Препроцессинг ===Для начала, модифицируем времена появления работ. Если работа <tex> j </tex> зависит от <tex> i </tex>, то, очевидно, она не может быть начата раньше, чем закончится выполнение <tex> i </tex>, поэтому нужно заменить <tex> r_j </tex> на <tex> \max(r_j, r_i + p_i) </tex>. Алгоритм, делающий это, представлен ниже (работы рассматриваются в порядке [[Использование_обхода_в_глубину_для_топологической_сортировки|топологической сортировки]]):
Нетрудно заметить, что переменная <tex>\mathrm{end}</tex> получается из суммы <tex>\mathrm{start}</tex> и <tex>\mathrm{time}</tex>. Используется для читаемости и уменьшения кода <tex>\mathrm{Decompose}</tex>. Можно воспринимать как макроподстановку. '''Алгоритм разбиения''' '''Block[]''' blocks('''int''' p[n], '''int''' rm[n]): '''int''' j = 0 '''int''' t = 0 <font color="darkgreen">// Переменная t указывает на время завершения последней работы </font> '''Block''' b[n] '''for''' i = 1 '''to''' n '''if''' t < rm[i] <font color="darkgreen">// Время появления очередной работы больше, чем время завершения последней </font> t =rm[i] <font color="darkgreen">// работы в блоке, не можем начать её делать. Создаём новый блок </font> j = Сохранение кратчайших путей j + 1 b[j].start =rm[i] b[j].time =0 b[j].add(i) <font color="darkgreen">// Добавляем к последнему блоку рассматриваемую работу, </font>Утверждается b[j].time = b[j].time + p[i] <font color="darkgreen">// увеличиваем суммарное время внутри блока и текущее время</font> t = t + p[i] '''return''' b Если значение <tex>n</tex> равно нулю, то считаем, что если какой-то путь алгоритм <tex>\mathrm{Blocks}</tex> возвращает пустое множество. Определим время начала блока <tex> P B_j </tex> был кратчайшим относительно весовой функции как <tex> s_j = \min\limits_{i \omega in B_j} rm_i </tex>, то он будет кратчайшим и относительно новой весовой функции а время конца — как <tex> e_j = s_j + \sum\omega_limits_{i \varphi in B_j} p_i </tex>.
{{Лемма
|statement=
|proof=
Возьмем произвольное оптимальное расписание <tex> S </tex>, в нем деление на блоки может также быть произвольным. Найдем первый такой временной интервал <tex> [s_j; e_j] </tex>, что в <tex> S </tex> есть период простоя внутри <tex> [s_j; e_j] </tex> (если таких периодов несколько, будем рассматривать первый из них). Обозначим его за <tex> [s; e] </tex>.
=== Декомпозиция ===Допустим, у нас есть блок работ, который можно выполнить без прерываний. Общая идея алгоритма <tex>\mathrm{Decompose}</tex> следующая:Его вес найдем работу <tex> i </tex>, которую выгоднее всего выполнить последней. Разобъем оставшееся множество работ на блоки, решим задачу для этих блоков рекурсивно и вставим <tex> i </tex> в промежутки между ними, до них и после них, начиная с новой весовой функцией равен <tex>\omega_\varphi(P) = \omega_\varphi(u_0u_1) + \omega_\varphi(u_1u_2) + \ldots + \omega_\varphi(u_rm_i </tex>. Псевдокод этого алгоритма представлен ниже. Алгоритм принимает множество блоков и изначально пустое расписание, при каждом вызове заполняет пробелы в расписании очередной работой и обновляет ответ. Возвращает оптимальное расписание и соответствующее значение <tex>f_{k-1max}u_k) </tex>.
}}
=== Теорема о существовании потенциальной функции Общий алгоритм ==={{Теорема|statement=
Из доказанной ранее леммы следует, что <tex>f_{max}(\Leftarrow </tex>: Рассмотрим произвольный <tex>C</tex> — цикл в графе <tex>G{ 1 \ldots n \}) = \max\limits_{j} f_{max}(B_j) </tex>, поэтому расписание для всего множества работ, поделенного на блоки, также будет оптимальным и корректным.
<tex>P(n) \Rightarrow </tex>: Добавим фиктивную вершину <tex>s</tex> в граф, а также ребра <tex> s geqslant сn + \sum\to u </tex> весом <tex> 0 </tex> для всех <tex> u limits_{i = 1}^{k} P(n_i) </tex>.
<tex> 2a \sum\limits_{\substack{i, j = 1\\ i \ne j}}^{k} n_i n_j \geqslant cn </tex>
Чтобы получить максимальную нижнюю оценку на <tex> a </tex>, оценим снизу <tex> \sum\limits_{i, j === Псевдокод ===1}^{k} n_i n_j </tex>:
== См. также ==* [[Алгоритм Дейкстры]]* [[Алгоритм Форда-Беллмана]]* [[Алгоритм ФлойдаПравило_Лаулера|Правило Лаулера]]
== Источники информации ==* ''Кормен ТPeter Brucker.«Scheduling Algorithms» {{---}} «Springer», Лейзерсон Ч2006 г., Ривест Р{{---}} 63-67 стр.'' Алгоритмы: построение и анализ. 2{{---}} ISBN 978-3-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.* [http://rain.ifmo.ru/cat/view.php/vis/graph540-paths/johnson69515-2001 Визуализатор алгоритма]8
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Кратчайшие пути в графах Теория расписаний]]
