1. 왜 v1부터 시작하는가?
cycle 이니까 시작점이 어디든 상관없지만 그냥 v1에서 시작하는걸로 생각하자
2. G = (V,E)
vertex, edge
2.1. W : 인접행렬의 매트릭스
2.2. V : 그래프의 꼭지점 = {v1, v2, v3, v4}
2.3. A : V의 부분집합
2.4. 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로 간다는 소리
3. 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
}
4. 시간 복잡도
'🕶 Algorithm > 알고리즘' 카테고리의 다른 글
Greedy Approach - Prim's Algorithm (0) | 2020.05.18 |
---|---|
Sequence Alignment Algorithm (0) | 2020.05.15 |
Traveling Salesperson Problem (TSP) - 0 (0) | 2020.05.13 |
알고리즘 과제 #3 (0) | 2020.05.12 |
Optimal Binary Search Tree (1) | 2020.04.30 |