최소 비용으로 강력하게 연결된 Digaph

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

문제

그래프 G의 각 노드 쌍 (i, j)에 대해 강하게 연결된 Digraph가 있습니다 (즉, 각 노드 쌍 (i, j)에 대해 I에서 I 로의 경로가 있습니다). 이 그래프에서 밀접하게 연결된 그래프를 찾고 모든 모서리의 합이 가장 적습니다.

다르게 말하면 가장자리를 제거한 후에는 그래프가 여전히 밀접하게 연결되어 있고 가장자리의 합계에 대한 비용이 가장 적은 방식으로 가장자리를 제거해야합니다.

나는 그것이 NP 어려운 문제라고 생각합니다. 20 개의 노드와 같은 작은 데이터 세트에 대한 근사치가 아닌 최적의 솔루션을 찾고 있습니다.

편집하다

보다 일반적인 설명 : 포도 G (v, e)가 주어지면 그래프 G '(v, e')를 찾으려면 v1에서 v2 로의 경로가 존재하는 경우 G의 V1과 V2 사이의 경로가 존재합니다. '및 e에서 각 ei의 합은 가장 적합하지 않습니다. 따라서 최소 동등한 그래프를 찾는 것과 비슷합니다. 여기서만 가장자리가 아닌 가장자리 가중치의 합을 최소화하려고합니다.

편집하다:

지금까지의 접근 방식 : 여러 번 방문하여 TSP를 사용하여 해결할 생각이지만 정확하지 않습니다. 여기서 나의 목표는 각 도시를 다루는 것이지만 최소 비용 경로를 사용하는 것입니다. 따라서 커버 세트 문제와 비슷하지만 확실하지 않습니다. 나는 총 비용이 최소 인 경로를 사용하여 각 도시를 다루어야하므로 이미 방문한 경로를 여러 번 방문하는 것은 비용에 추가되지 않습니다.

도움이 되었습니까?

해결책

당신의 문제는 다음과 같습니다 최소 스패닝 강한 하위 (DI) 그래프 (MSSS) 또는보다 일반적으로 최소 비용 SUB (DI) 그래프에 걸친 최소 비용 및 IS 실제로 NP-HARD. 다른 책도 참조하십시오. 501 페이지 그리고 480 페이지.

삼각형 불평등을 만족하지 않는 모든 모서리를 제거하는 것으로 시작합니다. A-> B -> C를 사용하는 경우 가장자리 A-> C를 제거 할 수 있습니다. 이것은 나에게 TSP를 생각 나게하지만 그것이 어디서나 이끄는 지 모른다.

나의 이전 대답은 다음을 사용하는 것이 었습니다 Chu-Liu/Edmonds 알고리즘 해결합니다 수목 문제; Kazoom과 Shreevatsar가 지적했듯이 이것은 도움이되지 않습니다.

다른 팁

나는 이것을 역동적 인 프로그래밍 방식으로 시도 할 것입니다.

0- 그래프를 목록에 넣습니다

1- 이전 목록에서 각 그래프의 새 하위 그래프 목록을 작성하십시오. 여기서 각각의 새 하위 그래프에 대해 하나의 다른 에지를 제거합니다.

2- 새 목록에서 복제를 제거합니다

3- 강하게 연결되지 않은 새 목록에서 모든 그래프 제거

4- 새 목록의 최고의 그래프를 현재 최고와 비교하십시오.

5- 새 목록이 비어 있으면 현재 최고는 솔루션입니다. 그렇지 않으면 Reburse/Loop/Goto 1

LISP에서는 다음과 같이 보일 수 있습니다.

(defun best-subgraph (digraphs &optional (current-best (best digraphs)))
  (let* ((new-list (remove-if-not #'strongly-connected
                                  (remove-duplicates (list-subgraphs-1 digraphs)
                                                     :test #'digraph-equal)))
         (this-best (best (cons current-best new-list))))
    (if (null new-list)
        this-best
        (best-subgraph new-list this-best))))

의 정의 strongly-connected, list-subgraphs-1, digraph-equal, best, 그리고 better 독자를위한 운동으로 남겨 둡니다.

이 문제는 여기에 설명 된 문제와 같습니다. http://www.facebook.com/careers/puzzles.php?puzzle_id=1

유명한 Facebull 퍼즐을 해결하는 데 도움이 된 아이디어는 거의 없습니다.

전처리 단계 :

  1. 가지 치기 : 저렴하거나있는 경우 모든 가장자리 AB를 제거합니다. 같은 비용 경로 : 예 : ACB.

  2. 그래프 분해 : 그래프에 관절 지점이있는 경우 하위 문제를 해결할 수 있습니다.

  3. 나가는 가장자리가 하나만 있으면 정점을 하나의 가상 정점으로 병합하십시오.

계산 단계 :

  1. 반복적 인 방문으로 지시 된 TSP를 사용하여 대략적인 솔루션을 얻으십시오. Floyd Warshall을 사용한 다음 헝가리 방법을 사용하여 과제 문제 o (n^3)를 해결하십시오. 한 번 사이클을 얻은 경우 - 지시 된 TSP 솔루션이 아닌 경우 분기와 바운드 TSP를 사용합니다. 그 후 우리는 상한 값 - 최소 비용의주기입니다.

  2. 정확한 솔루션 - 분기 및 바운드 접근. 가장 짧은 사이클에서 정점을 제거하고 상한보다 비용이 적은 비용으로 강력하게 연결된 그래프를 빌드하십시오.

그게 다 사람들입니다. 솔루션을 테스트하려면 여기에서 사용해보십시오. http://codercharts.com/puzzle/caribbean-salesman

사용하고 싶은 것 같습니다 dijkstra 알고리즘

기본적으로 원하는 것은 노드를 두 번 이상 방문 할 수있는 여행사를위한 최적의 솔루션 인 것 같습니다.

편집하다:

흠. 각 노드 I을 본질적으로 반복 한 다음 모든 가장자리가 가리키는 최소 스패닝 트리를 수행 하여이 문제를 해결할 수 있습니까? 에게 그 노드 I은 모든 가장자리가 가리키는 또 다른 최소 스패닝 트리와 결합되었습니다. 떨어져 있는 그 노드에서?

에 대한 2 발사 최소 강하게 연결된 서브 그래프 동일한 (그러나 임의의) vertex에 뿌리를 둔 최소한의 브랜치 및 최소한의 아웃 브랜치의 결합을 취함으로써 얻어진다.

an 아웃 브랜치, 또한 ~으로 알려진 수목, 모든 정점에 걸친 단일 정점에 뿌리를 둔 지시 된 나무입니다. 지배는 역 가장자리와 동일합니다. 이것들은 찾을 수 있습니다 에드몬드 알고리즘 제 시간에 o (VE), 그리고 속도가 빨라집니다 o (e log (v)) (참조 위키 페이지). 심지어도 있습니다 오픈 소스 구현.

2- 발사 결과에 대한 원래 참조는입니다 Jaja와 Frederickson의 종이, 그러나 종이는 자유롭게 접근 할 수 없습니다.

Adrian Vetta의 3/2 근사조차도 있습니다 (PDF), 위의 것보다 더 복잡합니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top