Дан граф G(V, E) и длительность каждой вершины. Необходимо каждой вершине сопоставить непрерывный полуинтервал [l, r) такой, чтобы r - l = W[i], для соседних вершин эти полуинтервалы не пересекаются и максимальное r минимально.
V - множество вершин
Е - множество ребер
W - множество весов вершин
G(V, E) - граф на множестве вершин V с множеством ребер E
F(V, E) - оптимальный ответ для графа G(V, E)
E(A) - ребра из множества E такие, что хотя-бы один их конец лежит в A
E(A, A) - ребра из множества E такие, что оба их конца лежат в A
Тогда можно заметить некоторые факты:
-
F(\empty, \empty) = 0
-
F(V, \empty) = max (v in V) W[v]
-
max ([a, b] in E) W[a] + W[b] <= F(V, E). В случае пустого E, смотрим предыдущий пункт.
-
A - subet of V --> F(V \ A, E \ E(A)) <= F(V, E) <= F(V \ A, E \ E(A)) + F(A, E(A, A))
-
A - independent subset of V --> F(V \ A, E \ E(A)) <= F(V, E) <= F(V \ A, E \ E(A)) + max (v in A) W[v]
-
A[1..k] - independent subset of V, sum A[i] = V -->
max F(A[i], \empty) <= F(V, E) <= sum F(A[i], \empty) <= k * max F(A[i], \empty)
-
H(V, E) - хроматическое число G(V, E) --> F(V, E) <= H(V, E) * max W[i]
-
Несвязный граф, тогда F(V, E) = max (v in V) W[v], запускаем все в момент 0
-
Двудольный граф, тогда F(V, E) = max ([a, b] in E) W[a] + W[b], это нижняя оценка, что следует из теории, а добиться ее можно так:
запускаем все вершины цвета 1 в момент 0
Вершины цвета 2 запускаем в момент F - W[i]
Тогда для пары соседних вершин, одна занимает начало доступного отрезка, а вторая - конец. Значит, они не переекаются.
-
Цикл нечетной длины. Перенумерем вершины в порядке обхода цикла, тогда
F(V, E) = max { max W[i] + W[i+1], min W[i] + W[i+1] + W[i+2]}
Тут пологается циклическая нумерация.
Докажем этот факт
-
если max W[i] + W[i+1] >= min W[i] + W[i+1] + W[i+2]
Очевидно, что ответ не может быть меньше W[i] + W[i+1], значит, осталось его построить.
Давайте рассмотрим такое j, что W[j] + W[j+1] + W[j+2] - минимльно. Покрасим все вершины, кроме j+1 в два цвета.
Вершины цвета 1 запустим в момент 0
Вершины цвета 2 запустим в момент F - W[i]
Как и в двудольном графе, никакая пара вершин тут не будет пересекаться.
Теперь вернемся к вершине j+1. По построению, одна из вершин, пусть j, запущена в 0, а j+2 в F - W[j+2]
Так как известно, что W[j] + W[j+1] + W[j+2] <= F --> если запустить j+1 в момент W[j], то она не пересечется с j+1
Что и требовалось доказать
-
если max W[i] + W[i+1] < min W[i] + W[i+1] + W[i+2]
Давайте докажем, что в этом случае оптимальным ответом будет min W[i] + W[i+1] + W[i+2]. Если это так, то пример строится аналогично предыдущему случаю.
Пусть существует ответ F < min W[i] + W[i+1] + W[i+2], тогда давайте рассмотрим некоторую вершину j.
Ее время работы пересекается с временем работы вершины j+2. Почему? Если это не так, то время работы j, j+1, j+2 попарно не пересекаются,
а значит F >= W[j] + W[j+1] + W[j+2] >= min W[i] + W[i+1] + W[i+2]
Теперь заметим, что есть вершина, начинающая работать в момент 0. Если ее нет, то ответ, очевидно, неоптимален. Пусть это k
Тогда T[k+1] >= W[k] и [0, W[k]) пересекается с [T[k+2], T[k+2] + W[k+2]) значит, T[k+2] + W[k+2] <= T[k+1], иначе не может быть пересечения.
Но верно и то, что [T[k+1], T[k+1] + W[k+1]) пересекается с [T[k+3], T[k+3] + W[k+3]), значит T[k+3] >= T[k+2] + W[k+2], аналогично
Значит верно, что T[k+1] > T[k+2], T[k+3] > T[k+2], значит можно положить T[k+2] = 0, это не ухудшит ответ.
Проведем аналогичные рассуждения с этой вершиной и получим T[k+2c] = 0, но в силу того, что длина графа нечетная - есть 2c = |V|-1
Тогда получается, что T[k] = 0, T[k+2c] = T[k-1] = 0, но тогда время работы этих вершин пересекается - противоречие.
Что и требовалось доказать.
Алгоритм каждый раз жадно набирает независимое множество и запускает все вершины в один момент. Время работы такого множества = максимумальное время работы элементов множества
Решение неточное, работает за O(n * m)
Изначально вершины сортируются по времени работы. Далее запускается greedy-coloring-1
Решение неточное, работает за O(n * m)
В исходный граф добавляется новая вершина с номером 0 и длительностью 0. Из нее проводятся ребра во все вершины. Теперь перебираются все остовные деревья этого графа, подвешиваются за 0 и l[v] = r[pre[v]] - время начала исполнения вершины пологается равным времени окончания исполнения ее предка.
Давайте докажем корректность этого алгоритма:
Для начала заметим, что для любой верины ее время начала либо 0, либо время окончания одного из его соседей. Допустим, это не так. Тогда нет ни одного соседа, что исполняется в момент времени l-1, а значит ничего не мешает нам началь исполнять эту вершину раньше.
Теперь пусть вершина v начинает исполняться за u, тогда оставим ребро u-v. Таким образом, исходный граф разбился на лес. Для того, чтобы это продолжал быть остов и создается новая вершина, не влияющая на общее время исполнения.
Значит теперь оптимальный ответ можно закодировать (возможно не одним) остовным деревом. Значит, перебрав все деревья, мы когда-то посмотрим и на правильный ответ.
Решение работает за O(2^(m + n) * (n + m)), так как перебираются все подмножества ребер
Решение, аналогичное предыдущему, но теперь ведется перебор лишь множеств подмножеств размера n из множества размера (n + m).
Решение работает за O(C_{m+n}^n) (я пока не смог нормльно это вывести)
Заметим, что по аналогии со spanning-tree-1, мы можем кодировать все как перестановку. Для того чтобы раскодировать перестановку, давайте вершине назначать время начала равное максимуму времен окончания вершин соединенных с ней и находящихся в перестановке раньше. Чтобы закодировать в перестановку, просто сортируем вершины по времени начала.
Решение точное, за O(n! * (n + m))
Можно заметить, что если не перебирать перестановку и по ней восстанавливать ответ, а делать это параллельно, то можно сразу отсекать плохие перестановки. Так как кодирование происходит сортировкой по времени начала, то если процессе раскодировки start[perm[i]] > start[perm[i - 1]], то можно сраз прекратить обработку таких перестновок
Решение точное, за O(n! * (n + m))
Будем геренировавать случайную перестановку и пытаться обновить ей ответ, декодируя ее как в permutation-1
Решение неточное, работает за O(cnt * n), где cnt - число перебранных перестановок.
Применим алгоритм отжига к идее перестановок. Будем "ходить" на транспозицию и применим стандартную функцию температуры и вероятности перехода.
Решение неточное, работает за число фаз * время обработки фазы, а именно O(cnt * n)
t -> t/2
(F Old, F New) ->
F Old < F New -> exp(-(F Old - F New) / t)
otherwise -> 1
F(perm) = max time
Немного изменим функцию оптимальности предыдущего способа. Будем использовать
F(perm) = sum time
Немного изменим функцию изменение состояния способа 1. Будем выбирать ребро и переставлять местами две вершины соединенные им.
Немного изменим функцию изменение состояния способа 2. Будем выбирать ребро и переставлять местами две вершины соединенные им.