Traveling Salesperson Problem

왜 v1부터 시작하는가?

cycle 이니까 시작점이 어디든 상관없지만 그냥 v1에서 시작하는걸로 생각하자

---

G = (V,E)

vertex, edge

 

W : 인접행렬의 매트릭스

V : 그래프의 꼭지점 = {v1, v2, v3, v4}

A : V의 부분집합

D[vi][A] : vi 에서 모든 A를 하나씩 방문하면서 v1로 가는 가장 짧은 거리

만약 A가 {v3} 였다면?

D[v2][A] 는 경로가 없으므로 무한대 : 2->3->1

만약 A가 {v3, v4} 였다면?

D[v2][A] 는 2->3->4->1 or 2->4->3->1

---

i = 1 은 아니다. 그리고 vi는 V의 원소가 아니다.

 

D[vi][￠] = W[i][1], if A = 공집합 : vi에서 바로 vi로 간다는 소리

 D[vi][A] = minimum( W[i][j] + D[vj][A-{vj}] ) 

---

A = {v2,v3,v4} : 6가지 나온다. 3가지 잘못나옴

---

int W[MAX][MAX];
int P[MAX][MAX];
int D[MAX][MAX]; // D[vi][A]

void travel(int n){
    int i, j, k, A; 
    for (i = 2; i<=n; i++)
        D[i][0] = W[i][1];
    for (k = 1; k<=n-2; k++)
        for (/* all subsets A (V-{V1}에 포함되는) containing k vertices */)
            for (/* all i 에 대해서 i != 1 and vi is not in A */){
                // Find the minimum from i to j
                D[i][A] = minimum(i, A, &j, n);
                P[i][A] = j; // the value that gave the minimum
            }
    A = V-{vi}
    D[1][A] = minimum(1, A, &j, n);
    P[1][A} = j; // the value that gave the minimum
}

 

---

 

시간 복잡도