방향성 비순환 그래프의 임계 경로를 계산하는 방법은 무엇입니까?
-
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의 무게입니다.
- 모든 i < k에 대해 S에서 x_i까지의 최대 비용을 계산했다고 가정하면 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를 실행하면 부정된 경로의 가장 작은 경로에 대한 솔루션을 찾고 원래 경로에 대한 가장 긴 경로를 찾을 수 있으므로 충분합니다.