[알고리즘] The Traveling Salesperson Problem(외판원 문제)

The Traveling Salesperson Problem

-> 비행기타고 여기저기 출장 다녀오기 (ง˙∇˙)ว 

+ 최소값으로 다녀와야함

Input

- 값이 있는 방향 그래프

- 음수 x

- 행과 열이 1부터 n까지인 2차원 배열 W

- W[i][j] : i번째 정점에서 j번째 정점까지의 간선 위의 가중치

Output

- 최적 투어의 길이를 값으로 하는 변수 minlength, 그를 구성하는 행렬 P

Dynamic Programming for TSP

- Brute force algorithm(전부 찾기)

: (n - 1)!

- The length of the optimal path(최적 경로 방법?)

아무튼 최단 거리를 찾는게 목표

 

일반적으로 i가 1이 아니고 vi가 A가 아니라면

a가 0이 아니면(내가 나한테 갈 수 없자나)

min값 중에서 찾고

∅ 라면 시작지로 돌아감!

 

Practice to solve TSP using Dynamic Programming

전에 했던 그 노가다 방법..https://meongjeong.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Graph-Theory-%EA%B7%B8%EB%9E%98%ED%94%84-%EC%9D%B4%EB%A1%A0

[알고리즘]Graph Theory | 그래프 이론

DP for TSP

void travel(int n, const number W[][], index P[][], number& minlrngth) {
	index i, j, k;
    number D[1..n][subset of V-{v1}]; //배열 선언?
    for(i = 2; i <= n; i++) D[i][emptyset] := W[i][1]; // 공집합이면 원점으로 돌아가는 값 주기
    for(k = 1;k <= n - 2; k++)
    	for all subsets A in(V-{v1}) containing k vertices
        	for(i != 1 and vi is not in A) { //A == n - 1 - k? 시작지에서 출발이 아니고 목적지가 vi(경유지)가 아니라면
            	D[i][A] = minimum_vj∈A (W[i][j] + D[vj][A-{vj}]);
                P[i][A] = value of j that gave the minimum;
            }
            D[1][A] = minimum_2≤j≤n (W[1][j] + D[vj][A-{v1}]); //시작지부터?
            P[1][A] = value of j that gave the minimum;
            minilength = D[1][V - {v1}]; //아무튼 다 구하고 내가 원하는 값 넣어주기?

Theorem 

안쉬워요 뭐라는건지 모르겠어요

Time complexity analysis for TSP in DP

n^2도 있고 2^n도 있고 별로 좋지 않군..

하지만 DP가 brute force algorithm(n-1)!보단 낫다..

Branch and bound in TSP

위에서부터 천천히 타고 내려감..

0 Level

: 자기 자신을 제외한 노드들 중에 출발하는 경우 중 가장 min한 값을 찾아서 더함

bound

= min(14, 4, 10, 20) //1번행에서 출발

+ min(14, 7, 8, 7) //2번 행 출발

+ 3번 행에서 갈 수 있는 도시, + 4번 도시 + 5번 도시

= 4 + 7 + 4 + 2 + 4 = 21 //근데 왜 ml은 무한? << 초기 값은 무한이라?

1 Level

ex. B([1, 2]) //1다음에는 2를 가야함

1 -> 2 : 14(정해져있음)

2 -> : min(7, 8, 7) -> 7 // 1, 2(X) < 출발지와 자기 자신으로 갈 수 없음

3 -> : min(4, 7, 16)-> 4 //2, 3(x) < 2에서 옴(1에서 2로 갔으니 2에서 출발한다고 할 수 있음), 3은 자기 자신, 1은 귀국이라 가능

4 -> : 2, 4(x)

5-> : 2, 5(x)

=> 31

아무튼 bound살펴가며 다 찾아보는듯? leaf node는 length를 담고 있음..

 

그니까..

1. 일단 bound가 가장 작은걸 하나 골라서 length가 나올 때 까지 살펴보기 -> ml

2. backtracking 해서 ml보다 bound가 더 작은 노드랑 비교하기 ex)6번 비교하고 bound = 27짜리 방문

3. 반복하다가 bound랑 length랑 동일하면 선택(더이상 더 작은 length는 없으므로)

라는거지 아무튼 그런거지

Another Bound Functions

1. in the rows //출발 기준

2. in the columns //도착 기준

3. in the rows & columns //평균 기준..?

이런 방법도 생각해 볼 수 있다~