Hamiltonian Cycle

A tour (a Hamiltonian cycle) is a path from a vertex to itself that passes through each other vertex exactly once.

어떤 그래프에서, 어떤 정점 시작해 모든 정점을 딱 한 번씩만 방문하고 그 정점으로 다시 돌아오는 경로. TSP문제는 이 해밀토니안 사이클 중 가장 길이가 짧은 사이클을 찾는 문제이다.

접근법

Let $G = (V,E)$ be a graph with $V = \lbrace{v_1,v_2,...,v_n\rbrace}$.

그래프 G가 있고, 정점 들의 집합 V가 있다.

Brute-force / 완전탐색

시작점을 제외한 정점들로 만들 수 있는 permutation을 모두 구해서, 양끝에 시작점을 더해준 sequence가 tour가 되는지 즉, 그 순서로 연결되어 있는지를 확인한다. 연결되어 있다면 해밀토니안 사이클 하나가 발견된 것이다. 그리고 항상 최소값을 유지하는 C라는 변수의 값과 비교해서 필요하다면 갱신해준다.

𝑇(𝑛)=Θ(𝑛!) 의 시간복잡도를 가진다.

Heuristic Algorithm

Nearest Neighbor(NN). 시작점에서 시작해 연결되있는 정점들 중 가장 거리가 짧은 정점을 tour에 추가하고, 이동한 그 정점에서도 같은 방식으로 진행한다. last는 바로 이전 단계의 정점을 의미.
𝑇(𝑛)=O(𝑛^2)의 시간복잡도를 가지지만, heuristic algorithm이기에 도출된 tour가 가능한 모든 해밀토니안 사이클 중에서 가장 짧은 tour인지 (optimal 한지) 보장할 수 없다. optimal과 근접하긴 하다.

실제로 다음과 같은 반례가 생길 수 있다.

위의 방법을 통해 tour를 구성하면 a - d - e - b - c - f - a 가 나오고 길이는 12이다.
하지만 가장 짧은 tour는 a - b - c - f - e - d - a 이고 길이는 10이다.

Dynamic Programming

The Principle of Optimality

T를 optimal tour라고 가정하고, 그 tour를 V_pi에서 잘라서 V_1까지 도달하는 경로를 P라고 하자. 우리는 전체 최적의 해 T에서 뽑아낸 부분 P 또한 최적인지를 증명하고 싶다.

근데 만약 P와 같이 V_pi에서 시작하지만 V_1까지 도달하는 경로가 다르면서, P 보다 더 짧은 거리로 V_1에 도달할 수 있는 경로를 P'라고 하자. 그렇다면 아까 P를 만들기 위해서 자른 V_pi에서 그 이전의 경로 즉, T-P 와 P'을 더한 T'(T' = T-P + P')은 T보다 더 짧은 tour일 것이다. T-P는 변함이 없지만 P 보다 더 짧은 P'이 더해졌기 때문이다.

하지만 이는 맨 처음에 T를 optimal tour라고 가정했던 것에 모순이다.
그래서 P가 V_pi 부터 시작해 V_1까지 도달하는 경로중 최적의 경로(부분 최적의 해)가 되는 것이고, '최적의 부분도 최적이 된다'는 것이 증명 된 것이다.

그 와중에 P를 다시 전체로 두고 다시 부분으로 나눠서 같은 증명을 할 수 있다. P 경로에서 처음과 끝을 제외한 어느 정점을 골라 다시 부분을 생성하고 같은 증명을 한다. 그러면 그 부분은 또 최적임이 증명된다.

DP

이런 원리를 이용하여, DP를 문제에 적용할 수 있다.
D[V_i][A]가 같는 값의 의미는 V_i로 시작해서 A에 있는 정점들을 한 번 씩만 거쳐 V_1(시작점)으로 갈 수 있는 경로 중 가장 짧은 경로의 길이이다.

점화식의 의미는 아까 principle of optimality에서 설명한 내용을 다시 적용할 수 있다. 부분을 나눌때 (V_i ~ V_1에서) V_j으로 자르면 V_j부터 뒤는 다 최적이고 (여러가지를 확인해서 가장 최적을 고를 예정이고) 그 최적값에 V_i ~ V_j 의 간선을 더해주면 전체 최적이 나올 수 있다. 이 설명을 들으면 top-down 방식처럼 느껴지지만, 재귀로 구현할때 표현만 top-down이 되고 실제로 dp테이블은 bottom-up으로 채워진다.

위의 그림을 보면 DP 방식 또한 완전탐색처럼 트리가 구성되는 것을 알 수 있다.
각 노드는 해당 구성에 대한 최적을 '보장'한다. 예를 들어 B:{C} 는 B에서 시작해 C를 거쳐 시작(A)로 가는 최적의(가장짧은) 값임이 보장된다.

근데 D:{B,C} 또한 같은 방식으로 최적을 보장해야 할 텐데, 트리에서 D:{B,C}에 해당하는 노드가 2개이다. 따라서 둘의 값을 비교해 최적값을 취한다. 최적값이 확인된 경우의 수는 그 값을 DP테이블에 저장한다. 다른 겹치는 노드들도 마찬가지로 최적값을 취하고 저장한다면 아래와 같은 그림이 될 수 있다.

이처럼, 가능한 경로의 경우의수를 따지되, 최적임을 보장하는 부분들을 저장해서 다시 활용하는 DP의 방식이 가능한 것이다.

결국 위와 같이 가장 마지막 A:{B,C,D}에 전체 문제에 대한 최적이 저장된다.

트리를 구성하는 노드의 개수가 시간복잡도와 관련이 있을 것인데, 이는 위의 그림에서 보이듯 시작정점(A)를 제외한 나머지 정점들에 대한 부분집합과 관련있다.

나머지 정점들 B,C,D를 각각의 부분 문제로 다시 생각해보자. 그러면 B의 경우 남은 정점이 C와 D이므로 {C,D}에 대한 부분집합 2^2개가 나온다. 나머지 C, D에 대한 부분문제 또한 마찬가지 이므로 생성 가능한 노드의 개수는 2^2 * 3. 이것을 일반화 해보자면, 맨처음 모든 정점의 개수는 n 이므로 (2^(n-2)) * (n-1)이 된다.
그리고 각 노드에서 최적이 결정되기 전, 그 노드의 각 부분문제를 확인해야한다. 예를 들어 C:{B,D} 노드의 경우 D:{B}, B:{D} 노드를 확인(부분문제가 반환하는 최적들을 비교해 현재 노드의 최적을 결정)해야 한다. 따라서 이는 노드에 따라 다르겠지만 최대 O(n)의 시간이 걸린다고 할 수 있다.

따라서 전체 시간 복잡도는 O(n) x O(n * 2^n) -> O(n^2 * 2^n)이 될수 있는 것이다. brute-force 방법 사용시의 O(n!)보다 많이 개선된 시간임을 알 수 있다.

BitMasking

그렇다면 DP테이블에 해당 노드의 값을 저장해야 하는데, 테이블 구성을 어떻게 할 것인가? 행은 각 정점의 이름, 열은 각 정점들이 경로에 포함되있는지 여부를 담은 정보로 구성해야 한다. 각 정점들이 경로에 포함되어 있는지를 '비트마스킹'을 통해 표현한다.
A, B, C, D 4개의 정점이 있을 때 각 정점이 포함(1), 미포함(0)된 경우를 모두 세면 2^4=16 가지의 경우의 수가 있다. 그래서 이를 0부터 15까지의 십진수를 통해 각각의 경우를 특정할 수 있다.

정점의 개수만큼 이진수자리가 생긴다.
예를 들어 A와 C가 포함된 경우는
DCBA
0101(2) = 5 라는 값으로 표현될 수 있다.

또한 이렇게 표현된 값에서 특정 정점이 포함되어 있는지를 확인할 때도 이진법을 적극 활용한다. 앞서 든 예에서 C가 포함되어있는지 여부를 살펴볼 때 C가 i번째 정점이라고 하면, 5 & (1 << i) 연산을 통해 확인할 수 있다.

• 'a << b' 쉬프트 연산은 a를 이진수로 표현했을 때 각 숫자를 왼쪽으로 b칸 이동한 값을 준다. 4(100) << 2 는 16(10000) 이 된다.
• 'a & b' 연산은 a와 b를 각각 이진수로 표현했을 때 어떤 자리수의 수가 둘다 1이면 그 자리에 1을 반환한다. 예를 들어 10 & 5 는 4가 된다.

1110 = 10
0101 = 5
----
0100 = 4 

위와 같은 연산을 활용하면, C는 2번째(0부터시작) 정점이므로

0101 = 5
0100 = 4 = 1 << 2(번째)
----
0100 = 4 (0이 아님)

이라는 결과가 나온다. 정리해보면 해당 연산을 통해 포함여부를 확인할 때 0(0000)이 나온다면 포함되지 않았다는 뜻이고, 0이 아닌 어떤 값(0100)이 나왔다면 포함되었다는 말이 된다. 이를 구현에서 활용하면 배열을 사용한 포함여부 검사보다 훨씬 시간을 줄일 수 있다. 쉬프트 연산은 빠른 연산에 속하기 때문이다.

구현

백준 2098번 외판원순회 문제를 통해 DP와 BitMasking을 활용한 TSP 구현을 해 볼수 있다.

import sys

n = int(input())
w = [] 
for _ in range(n):
    w.append(list(map(int, sys.stdin.readline().split())))
dp = [[-1] * (1<<(n-1)) for _ in range(n)]  # 어차피 시작 정점의 이진수 자리는 항상 1이기 때문에 한칸 줄여서.
                                            # n-1개의 bit로 만들 수 있는 경우의 수는 1<<(n-1).
                                            # 각각의 경우의 수에대한 십진수 i는  0 <= i <= 1<<(n-1) - 1
                                            # 그래서 함수 호출시 모두 포함하는 경우에 대한 십진수를 1<<(n-1) - 1 로 준다.
def go(i, included):
    if not included and w[i][0]:     # v_i : {}
    								 # 모든 자리수가 0인 상황.
                                     # 즉 아무 정점도 안거치고 v_i에서 시작정점으로 가는 비용 = 해당 간선의 비용이 된다.
        dp[i][included] = w[i][0]
    
    if dp[i][included] < 0:		# 지금 호출된 부분문제에 대한 최적이 구해지지 않았다면 = 해당 DP테이블 공간이 한 번도 건드려지지 않았다면, 다시 하위 부분문제를 생성해 최적을 구한다.
        min_ = 1 << 32
        for j in range(1,n):
            if included & (1<<(j-1)) and w[i][j]:	# 각 부분문제를 생성하는 과정이다.
            										# 중괄호 안에 포함된 정점의 자리수는 1이다.
                length = w[i][j] + go(j, included - (1<<(j-1)))
                if length < min_ : min_ = length
                
        dp[i][included] = min_
    
    return dp[i][included]

go(0, (1<<(n-1))-1)
print(dp[0][(1<<(n-1))-1])

함수가 재귀호출을 통해 top-down방식으로 부분문제로 파고들지만, 결국 DP 테이블은 v_i : {} 인 경우부터, 즉 bottom-up의 방향으로 채워짐을 명심해야 한다.

참고사이트

• https://www.youtube.com/watch?v=_51ot-Ri0ng
• https://www.youtube.com/watch?v=XaXsJJh-Q5Y&t=616s
• 강의자료