알고리즘24-2 traveling salesman problem

세일즈맨이 집에서 출발해서 다른 곳들을 방문하고 자기 집으로 돌아온다.

최소 weight로 모든 곳을 한 번씩만 다 가는 path (출발점인 s만 두번)

 

노드가 n개면 (n-1)!가지 = 노드의 모든 시퀀스

 

한군데를 끝까지 다 가봤다고 치는 작전!

현재까지 cost중 가장 좋은 것 찾기

 

답이 없다는 것이 확실하면 cut off하니까

답을 찾고 있다는 것은 보장할 수 있다.

 

루트에서 쭉 내려오면 cost를 계산할 수 있다.

 

1. current  cost가 current best cost보다 크면 cut off하면 된다.

 

2. (current cost + 남은 엣지의 갯수)를  current best cost와 비교

(edge weight가 최소 1이므로)

 

3. current cost + 남은 엣지의 갯수 * 그래프 전체에서 edge weight가 가장 작은 것

(1이면 두번쨰 방법과 같다.)

 

 

 

 

---

 

 

이 작전을 조금 더 정확하게 해보자

가장 작은 weight가 3이라면 3을 줄 수도 있겠지만

3인 엣지가 딱 하나밖에 없다면 하나는 3을 곱하고 나머지는 4를 곱할 수도

cut off를 더 많이 할 수 있지만 계산 시간이 많이 걸린다.

 

S에서 별까지 왔다.

별과 ?가 직접 연결된 엣지 중 최소 = L이라고 하자.

S과 ?가 연결된 최소 엣지 F

 

(이유: 최소엣지가 이미 S와 V를 연결했다면 계산식에 넣는 의미가 없기 때문에!)

 

별에서 떠날 때 L이상을 써야 하고 S로 돌아올 때는 F이상을 써야 한다.

 

?는 별에서오는데사용될지 / S로가는데사용될지 / ?끼리 연결될지모르기 때문에

각 ?에 대해서 모든 연결된 엣지 중 가장 작은 weight 2개

 

다 더한 값을 X라고 하고

C + X/2 > current best보다 크면 cut off 

 

 

 

물음표가 6개 남았다.

->앞으로 가야할 엣지는 7개

 

1+1+(6*2) = 14개

필요한 엣지는 7개인데 14개를 골랐다.

그래서 X를 반으로 나누는 것이다. => 다행히 보장이 된다.

 

 

어떤 path가 있다고쳐도

별은 L/2

S는 F/2

?은 자신이 선택한 2개의 평균을 받은 것

 

 

 

 

최소 엣지 2개에서 각각 절반 weight를 받는다.

무슨 path 더라도 X/2보다는 크다.