외판원 순회 문제 (Traveling Salesman Problem)
외판원 순회 문제는 대표적인 $NP-complete$ 문제로, 다음의 문제 상황을 갖는다.
N개의 정점으로 이루어진 연결 그래프가 있다. 각 간선에는 가중치가 존재한다. 임의의 한 정점을 시작으로 다른 모든 정점을 한 번씩 방문한 뒤 처음 정점으로 돌아오는 최소 비용의 순회를 찾을 수 있는가?
즉, 엄밀히 말하자면 가중치 있는 연결 그래프 속에서 다항 시간 내에 해밀턴 경로를 찾아낼 수 있는가? 가 되겠다.
이 문제를 해결하는 방법에 대해 알아보도록 하자.
단순한 방법
이 문제를 푸는 가장 단순한 방법을 생각해보자. 이는 곧 모든 가능성을 시도해보는 것이다.
정점은 0, 1, 2, ... , n-1의 번호를 갖으며, 그에 따라 각각 0, 1, 2, ... , n-1번 비트로 표현된다. graph[i][j] : i에서 j로 이어진 간선의 가중치 (존재하지 않는다면 0) 최초 호출은 tsp(0, 1)
tsp(now, mask) ← 현재 정점, 방문 상태
{
if mask == (1 << n) - 1 ← n개의 비트가 모두 켜졌다면(= 모든 정점을 방문했다면)
{
if graph[now][0] > 0 ← now에서 시작 정점으로 돌아갈 수 있다면
return graph[now][0]
else
return inf
}
res = inf
for i ← 0 to n-1
{
if graph[now][i] == 0 || (mask & (1 << i)) ← now에서 i로 가는 경로가 없거나 i번 비트가 켜져 있는 경우(i를 이미 방문)
continue
res = min(res, tsp(i, mask | (1 << i)) + graph[now][i])
}
return res
}
위 구현의 경우 $O(n \times n!)$의 시간 복잡도를 갖게 되며, $n$이 굉장히 작지 않은 이상 사용하기에 무리가 있어 보인다.
문제점
위 구현의 시간 복잡도가 파멸적인 이유는 무엇일까? 극단적으로 다음과 같은 그래프 모양을 떠올려볼 수 있을 것이다.
편의 상 구역 $1$을 $\{1, 2, 3, 4, 5\}$, 구역 $2$를 $\{6, 7, 8, 9, 10\}$라 하고, $0$에서 시작하여 구역 $2$를 전부 순회한 뒤 $6$번 정점 위에 서있다고 해보자.
그럼 방문 상태를 나타내는 $mask$는 "$11111000001$"일 것이며 이 방문 상태에 도달할 수 있는 경로는 여러가지일 것이다.
나아가 이 방문 상태에 도달할 때마다 매번 또 구역 $1$을 순회하는 부분 문제를 풀게 되는 불상사가 일어난다.
우리는 이런 부분 구조에서 메모이제이션을 통한 최적화 방법을 알고 있다. 바로 다이나믹 프로그래밍이라고 불리우는 방법이다.
최적화
방문 상태를 비트로 표현함에 따라, 비트의 형태를 저장하는 메모이제이션 방식을 채택하자. $n$개의 비트에 대해 $2^n$개의 상태가 존재한다.
dp[now][mask] : 지금까지 방문한 정점의 비트 표현이 mask이고 now번 정점 위에 서있을 때의 답.
(처음 dp 배열의 크기를 잡을 때 mask의 크기는 1 << n 으로 간단히 표현할 수 있다)
tsp(now, mask) ← 현재 정점, 방문 상태
{
if mask == (1 << n) - 1 ← n개의 비트가 모두 켜졌다면(= 모든 정점을 방문했다면)
{
if graph[now][0] > 0 ← now에서 시작 정점으로 돌아갈 수 있다면
return graph[now][0]
else
return inf
}
if(dp[now][mask] > 0) ← 이미 계산된 상태라면
return dp[now][mask]
dp[now][mask] = inf
for i ← 0 to n-1
{
if graph[now][i] == 0 || (mask & (1 << i)) ← now에서 i로 가는 경로가 없거나 i번 비트가 켜져 있는 경우(i를 이미 방문)
continue
dp[now][mask] = min(dp[now][mask], tsp(i, mask | (1 << i)) + graph[now][i])
}
return dp[now][mask]
}
이렇게 되면 $n \times 2^n$개의 상태가 존재하고 각 상태를 계산하는 데에 $O(n)$의 시간 복잡도를 소요하므로 문제를 총 $O(n^2 \times 2^n)$에 해결할 수 있게 된다.
결론 및 추천 문제
다이나믹 프로그래밍을 이용한 최적화로 팩토리얼 꼴의 시간 복잡도를 지수 꼴의 시간 복잡도로 줄여냈지만, 여전히 터무니 없는 시간 복잡도를 갖는다.현재까지 밝혀진 방법으론 $n$이 충분히 클 경우엔 휴리스틱한 방법으로 근사하는 것이 최선이라고 한다.
아래 추천 문제들을 풀어보며 외판원 순회 문제에 친숙해져 보도록 하자.