algorithm - the - topological sort dfs



목적 함수를 가진 위상 적 정렬 (2)

이를 해결하는 한 가지 방법은 다음과 같습니다.

먼저 All-Pair 최단 경로 알고리즘 Floyd-Warshall을 실행 합니다. 이 알고리즘은 기본적으로 5 줄의 코드 로 코딩 할 수 있으며 O(V^3) 시간에 실행됩니다. 그래프의 각 꼭지점 쌍 사이에 최단 경로를 생성합니다. 즉, 최단 경로의 VXV 행렬을 출력으로 생성합니다.

이 알고리즘을 수정하여 각 O(N^2) 경로에 포함 된 정점의 수를 얻을 수도 있습니다. 이제 N 개의 정점보다 작은 모든 경로를 제거 할 수 있습니다. 나머지 경로의 경우 비용으로 순서를 정한 다음 토폴로지 정렬 속성을 위반하지 않았는지 확인하기 위해 각각을 테스트합니다. 이 속성을 위반하지 않으면 원하는 결과를 얻었습니다.

위의 마지막 단계, 즉 토폴로지 정렬 테스트는 O (V + 2) 경로 각각에 대해 O (V + E)에서 수행 할 수 있습니다. 이렇게하면 최악의 런타임 인 O(V^4) 됩니다. 그러나 Floyd-Warshall은 매우 캐시 친화적으로 만들 수 있기 때문에 실제로는이 작업이 빨라야하며 실제로는 O (N ^ 2) 경로의 일부만 테스트 할 것입니다. 또한 DAG가 고밀도가 아니라면 적절한 데이터 구조로 토폴로지 테스트를 최적화 할 수 있습니다.

https://src-bin.com

나는 N, 즉, 1, 2, ..., N 의 DAG를 가지고 있고, 각 노드는 x_1, x_2, ..., x_N . 토폴로지 정렬을 수행하려고하지만 정렬이 어려울 때 정렬 할 때 목적 함수가 있습니다. 내 목적 함수는 여러 쌍의 노드 사이의 총 시간을 최소화하는 것입니다.

예를 들어 6 개의 노드가있는 DAG가 있고 (1, 3 (1,3) + (2,4) 가 최소화되도록 특정 토폴로지 정렬을 원합니다. 여기서 (A,B) 는 두 노드 A와 B 사이의 시간을 나타냅니다. 예를 들어, 정렬 [1, 6, 3, 2, 5, 4, 7] , (1,3) = x_6(2,4) = x_5 . DAG를 기반으로 (1,3) + (2,4) 를 최소화하는 정렬을 찾고 싶습니다.

나는이 문제를 한동안 생각해왔다. 모든 가능한 토폴로지 정렬 (참조 링크 )을 생성하고 목적 함수를 하나씩 계산하는 것은 항상 가능한 해결책이지만 N이 클 경우 너무 많은 시간이 필요합니다. 모든 가능한 정렬을 생성 할 때 브랜치 바인딩 프 루닝 (branch-bound pruning)을 사용하도록 제안되었습니다 (브랜치 바인딩이 익숙하지는 않지만 복잡성을 크게 줄이지는 못한다고 생각합니다).

이러한 종류의 문제에 대한 (최적 또는 경험적) 알고리즘은 무엇입니까? 알고리즘이 일부 노드의 총 시작 시간을 최소화하는 것과 같은 다른 목적 함수에도 적용될 수 있다면 완벽 할 것입니다. 모든 제안을 부탁드립니다.

추신 : 그렇지 않으면 선형 정수 최적화 문제로이 문제를 공식화하는 것이 가능합니까?


Answer #1

여기에 아이디어가 있습니다.

단순화를 위해 먼저 최적화 할 단일 쌍 (나중에 일반적인 경우에 대해 설명 할 것입니다)을 가정하고 그래프를 위상 배열로 배열로 가정하십시오.

한 쌍의 하위 노드 ( 토폴로지 순서에 따라)에서 시작하여 l 말하고 높은 노드, 예를 들어 h 끝나는 배열 세그먼트를 가져옵니다. lh 사이에서 정렬 된 모든 단일 노드에 대해 아래에서부터 l 그리고 / 또는 위에서부터 h 경계 지어 졌는지 계산합니다. 이전의 특성을 계산할 수 있습니다 노드를 "상향"BFS에 l , 노드를 h 이상 으로 정렬 하여 절단합니다. 비슷하게, 후자는 h 에서 "하향"BFS를 표시하고, l 보다 작은 노드를 절단한다. 어느 패스의 복잡도는 O (B * L) 일 것이며, 여기서 B 는 분기 요인이며, L 은 원래 lh 사이에서 정렬 된 노드의 수입니다.

이제 위에서 h 로부터 경계가 정해져 있지 않은 모든 노드는 h 위에서 움직일 수 있고 l 의해 경계가 정해지지 않은 모든 노드는 l 아래에서 이동할 수 있습니다 (두 세트가 겹칠 수 있습니다). 각 노드 그룹 내에서 원래의 정렬 순서가 위 또는 아래로 재배치 된 경우에 한합니다.

원래의 정렬 순서에서 잘라낸 세그먼트가 겹치지 않는다면 필요한만큼 많은 쌍에 동일한 절차를 적용 할 수 있습니다.

(l1, h1)(l2, h2) 와 같이 두 쌍이 겹치면 원래의 정렬 순서로 l1 <l2 <h1 <h2가되도록 다음 두 가지 경우가 있습니다.

1) h1l2위상 적 순서에서 관련이없는 사소한 경우에, 당신은 서로 독립적으로 두 개의 쌍을 최적화 할 수 있어야합니다. l2 보다 높게 또는 l2 보다 아래로 이동시키기 위해주의를 기울여야합니다. l1 아래의 h1같지 않은 경우 h1 이 가능한 것으로 판명되어야합니다.)

2) 위상차 순서에서 l2 <h1 인 경우, 두 쌍을 단일 쌍 (l1, h2) 으로 처리 할 수 ​​있습니다. 그런 다음 프로 시저를 (l2, h1) 다시 적용 할 수 있습니다.

중요하지 않은 겹치는 경우에 전체 프로세스가 달성 할 수있는 것이 명확하지 않기 때문에 특히 겹치는 패턴이 더 복잡한 경우에는 겹치는 것과 상관없이 모든 쌍을 균일하게 처리하는 것이 더 나을 수 있습니다. 이 경우 순서는 반복적으로 처리 될 수 있지만 각 실행은 이전에 비해 개선됩니다 (프로 시저가 목적 함수의 관점에서 단조롭다면 확실하지 않습니다 - 아마도 그렇지 않습니다).





topological-sort