DAG с взвешиванием по узлам и самые длинные пути с обновлениями

Question

Предположим, у вас есть набор заданий, которые можно выполнять параллельно. Каждое задание имеет временное требование (временное требование для i-го задания t_i). Есть также некоторые зависимости, i-й из них говорит, что вы должны сделать работу u_i до работы v_i. Вы должны минимизировать общее требуемое время.

Это легко сделать, преобразовав эти отношения в ориентированный ациклический граф, а затем используя его, чтобы определить, какие из них делать параллельно.

В случае, если мне не ясно, вот пример. Предположим, у вас есть 5 заданий с требованиями времени 2, 9, 3, 12, 5, и вы должны выполнить 3 до 5, 4 до 5, 3 до 1 и 1 до 2. Тогда лучшее, что вы можете сделать, - это 17. Это твой черт

+---> 1 (2) ---> 2(9)
|
3 (3)
|
+----> 5 (5)
       ^
       |
4 (12)-+

Вы можете делать 3 и 4 параллельно, так что вы тратите MAX(3,12)=12 единиц времени, прежде чем делать 5, что занимает 5 единиц времени. Итак, 5 завершено через 17 единиц времени. С другой стороны 2 завершено после 14 единиц. Таким образом, ответ 17.

Вопрос в том, если в каждом запросе обновляется ровно одно требование времени (где каждый раз, когда вы начинаете с исходного графика, а не графика, полученного после предыдущих модификаций), как вы можете эффективно найти новое минимальное требование времени?

Для тех, кто хочет ограничений, количество рабочих мест <= 10^5. количество зависимостей <= 10^6, количество запросов <= 10^6.

Answer 1

Требуемое время - это максимальный вес пути в ациклическом ориентированном графе. Два обхода по линейному времени дают для каждого узла максимальный вес пути, заканчивающегося этим узлом, и максимальный вес пути, начинающегося с этого узла. Теперь мы можем найти максимальную длину пути, включая указанный узел. Если вес узла увеличивается, то мы берем максимум предыдущего максимума и новый максимум, связанный с этим узлом, который мы можем вычислить за постоянное время.

Уменьшение сложнее, поскольку для каждого узла в пути максимального веса нам нужен максимальный вес пути, не включая этот узел. Первый способ (возможно, не самый лучший), который я могу придумать, заключается в следующем. Добавьте к ациклическому ориентированному графу источник и приемник, оба с нулевым весом и соединениями с (источником) или с (приемником) каждого из других узлов. Пронумеруйте узлы в топологическом порядке, где источник равен 0, а приемник равен n + 1, и инициализируйте узлы отображения дерева сегментов в соответствии с весами пути, где начальные значения равны -infinity. Это дерево сегментов имеет следующие логарифмические операции времени.

Weight(i) - returns the value for node i
Update(i, j, w) - updates the value for nodes i..j to
                  the maximum of the current value and w

Для каждой дуги от i в j, вызов Update(i + 1, j - 1, w), где w максимальный вес пути, который включает в себя дугу от i в j, В конце каждый вес в дереве сегментов является максимальным весом пути, исключая соответствующий узел.

(Обратите внимание на время выполнения: обрабатывая узлы без зависимостей отдельно, время выполнения этого подхода можно сделать равным O(m log n + n + q), где n - количество узлов, m - количество зависимостей., и q - количество запросов. Мой тип дерева сегментов вычисляет трехмерные максимумы, проблему, хорошо изученную вычислительными геометрами. С предварительно отсортированным вводом (по крайней мере в двух измерениях) самый быстрый известный алгоритм для n точек - O(n log log n), через деревья Ван Эмде Боаса. Существуют также алгоритмы с временными границами, чувствительными к выходу, которые в некоторых случаях лучше, чем границы наихудшего случая.)