Как вычислить критический путь направленного ациклического графа?

StackOverflow https://stackoverflow.com/questions/107660

  •  01-07-2019
  •  | 
  •  

Вопрос

Каков наилучший (с точки зрения производительности) способ вычисления критического пути направленного ациклического графа, когда узлы графа имеют вес?

Например, если у меня есть следующая структура:

            Node A (weight 3)
               /            \
     Node B (weight 4)      Node D (weight 7)
     /               \
Node E (weight 2)   Node F (weight 3)

Критический путь должен быть A->B->F (общий вес:10)

Это было полезно?

Решение

Я понятия не имею о «критических путях», но я предполагаю, что вы имеете в виду этот.

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

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

Но ничто не спасет вас от полного обхода, если вы этого не сделаете.Порядок не имеет особого значения, пока вы выполняете обход и никогда не идите по одному и тому же пути дважды.

Другие советы

Я бы решил эту проблему с помощью динамического программирования.Чтобы найти максимальную стоимость от 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.

Есть статья, в которой якобы есть алгоритм для этого:«Критический путь в сети деятельности с ограничениями по времени».К сожалению, мне не удалось найти ссылку на бесплатную копию.Если не считать этого, я могу только поддержать идею изменения http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm или http://en.wikipedia.org/wiki/A*

ОБНОВЛЯТЬ:Прошу прощения за дрянное форматирование — механизм уценки на стороне сервера, видимо, сломан.

Мой первый ответ, поэтому, пожалуйста, извините за любые нестандартные вещи, связанные с культурой stackoverflow.

Я думаю, что решение простое.Просто отмените веса и запустите классический кратчайший путь для DAG (разумеется, с учетом весов вершин).Он должен работать довольно быстро.(Возможно, временная сложность O(V+E))

Я думаю, это должно работать так: когда вы отрицаете веса, самый большой становится наименьшим, второй по величине становится вторым по величине и так далее, как если бы a > b затем -a < -b.Тогда запуска DAG должно быть достаточно, поскольку он найдет решение для наименьшего пути из отрицательного и, таким образом, найдет самый длинный путь для исходного.

Попробуйте метод А*.

A* Алгоритм поиска

В конце, чтобы разобраться с листьями, просто заставьте их все вести к конечной точке, поставив ее в качестве цели.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top