방향성 비순환 그래프의 임계 경로를 계산하는 방법은 무엇입니까?

Question

그래프의 노드에 가중치가 있을 때 방향성 비순환 그래프의 임계 경로를 계산하는 가장 좋은(성능 측면에서) 방법은 무엇입니까?

예를 들어, 다음과 같은 구조가 있다고 가정해 보겠습니다.

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

주요 경로는 A->B->F여야 합니다(총 중량:10)

Answer 1

나는 "중요한 경로"에 대해 전혀 모르지만, 당신이 의미하는 것이라고 가정합니다 이것.

가중치가 있는 비순환 그래프에서 가장 긴 경로를 찾는 것은 전체 트리를 순회한 다음 길이를 비교해야만 가능합니다. 트리의 나머지 부분에 가중치가 어떻게 적용되는지 실제로 알 수 없기 때문입니다.트리 순회에 대한 자세한 내용은 다음에서 확인할 수 있습니다. 위키피디아.구현이 쉽고 간단하므로 선주문 순회를 사용하는 것이 좋습니다.

자주 쿼리하는 경우 삽입 시 하위 트리의 가중치에 대한 정보를 사용하여 노드 사이의 가장자리를 늘릴 수도 있습니다.이는 상대적으로 비용이 적게 드는 반면, 반복 순회에는 비용이 매우 많이 들 수 있습니다.

그러나 그렇게 하지 않으면 전체 순회에서 실제로 벗어날 수 있는 방법이 없습니다.순서는 크게 중요하지 않습니다. 순회 그리고 같은 길을 두 번 가지 마십시오.

Answer 2

동적 프로그래밍으로 이 문제를 해결하겠습니다.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에 대한 가장자리가 있는 모든 노드의 최대 비용을 더한 값입니다.

Answer 3

이에 대한 알고리즘이 있다고 주장하는 논문이 있습니다."시간 제약이 있는 활동 네트워크의 중요 경로".안타깝게도 무료 사본에 대한 링크를 찾을 수 없습니다.그 외에는 수정 아이디어를 고려할 수 없습니다. http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm 또는 http://en.wikipedia.org/wiki/A*

업데이트:형편없는 형식에 대해 사과드립니다. 서버 측 마크다운 엔진이 손상된 것 같습니다.

Answer 4

내 첫 번째 답변이므로 stackoverflow 문화에 따라 비표준적인 사항에 대해 양해해 주시기 바랍니다.

나는 해결책이 간단하다고 생각한다.가중치를 무효화하고 DAG에 대한 일반적인 최단 경로를 실행하세요(물론 정점 가중치에 맞게 수정됨).상당히 빠르게 실행되어야 합니다.(아마도 O(V+E)의 시간 복잡도)

가중치를 무효화하면 가장 큰 것이 가장 작아지고, 두 번째로 큰 것이 두 번째로 작아지는 식으로 작동해야 한다고 생각합니다. a > b 그 다음에 -a < -b.그런 다음 DAG를 실행하면 부정된 경로의 가장 작은 경로에 대한 솔루션을 찾고 원래 경로에 대한 가장 긴 경로를 찾을 수 있으므로 충분합니다.

Answer 5

A* 방법을 사용해 보세요.

A* 검색 알고리즘

마지막에 나뭇잎을 처리하려면 나뭇잎 모두가 최종 지점으로 연결되어 목표로 설정되도록 하면 됩니다.