Sanjoy Dasgupta가 저술한 책인 Algorithms과 DongDD님의 블로그를 참고하였다.

1. TSP(Traveling Salesman Problem. 외판원 문제)

여러 도시들이 주어져있고 각 도시들에 가중치가 주어졌을 때, 시작점에서 출발해 모든 도시들을 한번씩 방문하여 다시 돌아오는 데 걸리는 최단 시간을 구하는 문제

만약 TSP를 DP가 아닌, 완전탐색기법으로 구하게된다면 도시의 개수 $n$개 만큼 $O(n!)$ 시간이 소요될 것이다. 이 방법은 $n$이 적을 때는 괜찮지만 $n$이 매우 많다면 비효율적일 것이다. 따라서 왠만하면 그냥 DP를 이용해 구하는게 낫다.

TSP는 도시의 수 $N$이 16개 이하일 때, DP와 비트마스크를 이용해 구한다. 이때 비트마스크는 특정 도시를 방문한 상태를 저장할 때 사용한다.

$C(S, j)$ : 도시의 집합 $S$ 내에서 1부터 $j$까지의 거리 라고 할 때
$C(S, j) = \min C(S-j, i) + d_(ij)$

즉, 1부터 $j$를 제외한 $i$까지의 거리와, $j$를 포함했을 때의 거리 중 최소가 되는 $j$를 선택해나가는 것이다.

부분문제의 수가 $2^nn$개이고, 부분문제를 푸는 데 선형시간이 걸리므로 시간복잡도는 $O(n^2 2^n)$이다.

2. Independent sets in trees(트리들 내의 독립집합)

독립집합 : 하나의 그래프, 트리 내에서 서로 인접하지 않은(이어진 간선이 없는) 정점들의 집합

이때, 가장 큰 독립집합을 찾는 문제이다.

보통 그래프 내에서 가장 큰 독립집합을 찾는 것은 어렵다. 하지만 트리 내에서라면, DP로 선형시간 안에 가장 큰 독립집합을 찾을 수 있다. 부분문제들의 수는 정확히 정점들의 수 이므로 시간복잡도는 $O(n)$이다.

3-1. Floyd-Warshall Algorithm(플로이드-와샬 알고리즘)

최단 경로 알고리즘 중 하나. 정점 $i$부터 $j$까지의 경로에서 새로운 정점 $k$가 중간에 포함될 때 경로가 더 짧아지는지 아닌지를 판단한다.

여기서 경로가 더 적어지는 것이 가능한 이유는 음수 가중치를 허용하기 때문이며, 플로이드-와샬 알고리즘의 핵심은 정점 $k$가 최단경로에 포함되느냐, 아니냐를 판단하는 것이다.

$dist(i, j, k)$ : $i$에서 $j$까지 $k$를 거치는 경로

$dist(i, j, k) = \min(dist(i, k, k-1), dist(k, j, k-1), dist(i, j, k-1))$

예시를 보자. 플로이드-와샬 알고리즘은 현재 경로의 비용을 저장하는 테이블과 중간정점을 저장하는 테이블을 사용한다.

다음과 같은 정점과 간선이 있다고 하자. 정점에서 다른 정점으로 바로 이동가능한 경우 그 비용을 표에 채우고, 그렇지 않은 경우 무한대(INF)로 설정한다. 그 다음, 차례대로 정점을 경유할 때의 가중치를 업데이트 해준다. 먼저 1번 정점을 경유해보자.

그렇게 되면 4번 정점에서 2번정점으로 나갈 수 있게 되므로 4 $\rightarrow$ 1 $\rightarrow$ 2　:　5 + 4 = 9이다.
이제 2번 정점을 경유해보자.

1번 정점 : 2번을 거쳐 4번으로 갈 수 있게 됨. 1 $\rightarrow$ 2 $\rightarrow$ 4　:　4 + 1 = 5

3번 정점 : 2번을 거쳐 자기 자신 3번으로 올 수 있게 됨. 3 $\rightarrow$ 2 $\rightarrow$ 3　:　1 + 2 = 3

3번 정점 : 2번을 거쳐 4번으로 갈 수 있게 됨 : 3 $\rightarrow$ 2 $\rightarrow$ 4　:　1 + 1 = 2

4번 정점 : 1번과 2번을 거쳐 자기 자신 4번으로 올 수 있게 됨. 4 $\rightarrow$ 1 $\rightarrow$ 2 $\rightarrow$ 4　:　5 + 4 + 1 = 10

다음으로 3번 정점을 경유하고, 또 4번 정점을 경유해서 각각 최소 비용으로 그 거리를 업데이트 한다면 최종 결과는 다음과 같다.

3-2. Floyd-Warshall Algorithm 시간복잡도

노드의 개수가 $V$개 일 때, 매번 모든 노드들의 조합에 대해 현재까지의 최단경로를 구해야하므로 $O(V^2)$ 시간이 소요되고, 이를 총 $V - 1$번 반복해야 하므로 최종 시간복잡도는 $O(V^3)$이다. 즉 다시 말해, 정점 $i, j, k$가 모두 1부터 $V$까지 반복되므로 $O(V^3)$이다.