Christofides 알고리즘 (수동)
On 2월 1, 2021 by admin다음 알고리즘 예제를 따르고 있습니다. https://en.wikipedia.org/wiki/Christofides_algorithm#example
The graph:
[! [여기에 이미지 설명 입력] [1]] [1]
Calculate minimum spanning tree T:
[! [여기에 이미지 설명 입력] [2]] [2]
Calculate the set of vertices O with odd degree in T
” 모든 정점의 정도가 홀수이므로 최소 스패닝 트리 T “입니다.
Form the subgraph of G using only the vertices of O
(모두 이상 했으므로 원래 그래프를 제공해야합니다) [! [ 여기에 이미지 설명 입력] [1]] [1]
Construct a minimum-weight perfect matching M in this subgraph
( 제대로 했어요 ) [! [여기에 이미지 설명 입력] [3]] [3]
Unite matching and spanning tree T ∪ M to form an Eulerian multigraph
[! [여기에 이미지 설명 입력] [4]] [4]
이것은 확실히 옳지 않습니다.
무엇이 잘못 되었나요?
댓글
- 참고 : 게시물의 모든 이미지가 사라진 것 같습니다. 작성자가 원본을 가지고 있습니까?
답변
사실 당신은 항상 옳았습니다 . 그러나 아직 Christofides 알고리즘을 완료하지 않았습니다.
다음 단계는 “Calculate Euler tour”입니다.
In 마지막 사진 , 모든 정점이 짝수 인 다중 그래프를 얻었습니다. 그래서 그것은 Eulerian 경로가 있어야합니다. 예를 들어 Eulerian 경로 A-> F-> A-> C-> B-> D-> E-> D-> A를 선택하겠습니다.
마지막 단계는 “반복 된 정점 제거 , 알고리즘의 출력을 제공합니다.
위 경로에서 두 번째 A와 두 번째 D를 제거하면 원하는 출력을 얻습니다. A-> F-> C-> B-> D-> E-> A . 완료.
주어진 그래프에 Christofides 알고리즘을 적용하는 것은 그다지 의미가 없습니다.
“Christofides 알고리즘은
여행하는 세일즈맨 문제 , 거리가 미터법 공간을 형성하는 경우 (대칭이며 삼각형 부등식 “. 주어진 거리는 삼각형 부등식을 따르지 않습니다. d (B, D) + d (D, E) = 1 + 4 < 6 = d (B , E). 또한 A와 B 사이의 (직접) 거리가 주어지지 않아 이것이 여행하는 세일즈맨 문제인지 의심을 불러 일으 킵니다.
다중 그래프 ", 여러 간선, 즉 동일한 간선을 가질 수있는 그래프 끝 노드. D와 E 사이에는 두 개의 모서리가 있습니다. A와 F 사이에는 두 개의 모서리가 있습니다.