Как вычислить критический путь направленного ациклического графа?
Каков наилучший (с точки зрения производительности) способ вычисления критического пути направленного ациклического графа, когда узлы графа имеют вес?
Например, если у меня следующая структура:
Node A (weight 3)
/ \
Node B (weight 4) Node D (weight 7)
/ \
Node E (weight 2) Node F (weight 3)
Критический путь должен быть A-> B-> F (общий вес: 10)
Ответы 5
Я понятия не имею о «критических путях», но предполагаю, что вы имеете в виду это.
Найти самый длинный путь в ациклическом графе с весами можно только путем обхода всего дерева и последующего сравнения длин, поскольку вы никогда не знаете, как взвешивается остальная часть дерева. Вы можете найти больше об обходе дерева на Википедия. Я предлагаю вам пойти с обходом предварительного заказа, так как это легко и просто реализовать.
Если вы собираетесь часто запрашивать, вы также можете захотеть расширить границы между узлами информацией о весе их поддеревьев при вставке. Это относительно дешево, в то время как повторный обход может быть чрезвычайно дорогостоящим.
Но нет ничего, что могло бы спасти вас от полного обхода, если вы этого не сделаете. Порядок на самом деле не имеет значения, если вы выполняете обход и никогда не идете по одному и тому же пути дважды.
Я бы решил это с помощью динамического программирования. Чтобы найти максимальную стоимость от S до T:
- Топологически отсортируйте узлы графа как S = x_0, x_1, ..., x_n = T. (Игнорируйте любые узлы, которые могут достичь S или быть достигнутыми из T.)
- Максимальная стоимость от S до S - это вес S.
- Предполагая, что вы вычислили максимальную стоимость от S до x_i для всех i <k, максимальная стоимость от S до x_k - это стоимость x_k плюс максимальная стоимость для любого узла с ребром до x_k.
Попробуйте метод A *.
В конце, чтобы разобраться с листьями, просто сделайте так, чтобы все они вели к конечной точке, которую ставили в качестве цели.
Есть статья, в которой якобы есть алгоритм для этого: «Критический путь в сети активности с ограничениями по времени». К сожалению, мне не удалось найти ссылку на бесплатную копию. Если не считать этого, я могу только поддержать идею изменения http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm или http://en.wikipedia.org/wiki/A *
ОБНОВЛЕНИЕ: Прошу прощения за дерьмовое форматирование - серверный механизм уценки явно не работает.
Мой первый ответ, так что, пожалуйста, извините за любые нестандартные вещи, связанные с культурой stackoverflow.
Думаю, решение простое. Просто инвертируйте веса и запустите классический кратчайший путь для DAG (конечно, модифицированный для весов вершин). Он должен работать довольно быстро. (Возможно, временная сложность O (V + E))
Я думаю, это должно сработать, поскольку, когда вы отменяете веса, самый большой станет самым маленьким, второй по величине будет вторым по величине и так далее, как если бы a > b, затем -a < -b. Тогда запуска DAG должно быть достаточно, поскольку он найдет решение для наименьшего пути отрицаемого и, таким образом, найдет самый длинный путь для исходного.