동적 그래프 프로그래밍

Error

동적 프로그래밍을 사용하는 솔루션에서는 역학이 계산되는 순서가 중요합니다(현재 값이 의존하는 값을 먼저 계산해야 함).
따라서 방향성 비순환 그래프에 대해 동적 프로그래밍을 사용해야 하는 경우 초기에 그래프의 위상 정렬을 구성해야 합니다. 그런 다음 구성된 토폴로지 정렬 순서로 꼭지점을 정렬하여 역학을 계산합니다(문제에 따라 순회 순서는 소스에서 싱크로 또는 그 반대로 될 수 있음).
 
 

그래프에 주기가 포함되어 있으면(토폴로지 정렬이 없음) 두 가지 트릭이 도움이 될 수 있습니다.

1) 동역학을 n번 계산합니다. 여기서 n은 그래프의 정점 수입니다(Ford-Bellman 알고리즘과 유사). 그러나 이것은 점근선을 증가시키고 일반적으로 거의 효율적이지 않습니다.

2) 그래프 응축을 구성합니다. 원래 그래프의 강하게 연결된 각 구성 요소에 대해 문제를 개별적으로 풉니다. 응축된 그래프는 비순환적이며 이를 위해 토폴로지 정렬과 함께 표준 접근 방식을 사용할 수 있으며 정점 값으로 강하게 연결된 구성 요소에 대해 계산된 값을 사용할 수 있습니다. 이 방법이 주로 사용됩니다.