1. 외판원 순회 문제(TSP)
외판원 순회 문제는 그래프 탐색 문제입니다. N개의 정점이 있을 때, 이 정점들을 중복하지 않고 모두 방문할 수 있는 최적의 방법을 찾는 것이 문제의 목적입니다. 즉, 가장 효율적인 해밀턴 회로를 찾는 문제라고 설명할 수 있습니다. 이 문제는 쿠팡맨들을 비롯한 택배 기사님들의 숙원이기도 합니다. 정해진 지점들을 중복하지 않고 한 번에 가장 빠르게 돌 수 있는 방법을 알 수 있다면 퇴근을 빨리 할 수 있을 거예요.
2. NP-hard
하지만 택배 기사는 근무 강도가 높은 직종입니다. 그 이유는 바로 외판원 순회 문제가 다항시간 내에 해결할 수 있는 문제가 아니기 때문입니다. 아직까지 이 문제를 다항시간 내에 해결할 수 있는 알고리즘은 확인되지 않았고, 이 문제를 다항시간 내에 해결할 수 없음도 증명되지 않았다고 합니다. 꽤 간단한 문제일 것 같은데 왜 그럴까요? 다음 그래프를 봅시다.
6개의 정점 밖에 없는 그래프입니다. 간선도 11개 뿐입니다. S에서 시작해 S로 돌아오는 가장 빠른 회로를 찾으려면 어떻게 해야 할까요? 그리디한 방법으로 문제를 해결할 경우, 당장 탐색하게 될 간선이 가중치가 작더라도 나중에 가중치가 매우 큰 간선이 강제될 수 있어 결국은 완전 탐색을 해봐야 합니다. 그러면 이 그래프에서 그릴 수 있는 서로 다른 해밀턴 회로는 몇 가지 일까요?
1: [S, 1, 2, 3, 4, 5, S]
2: [S, 1, 2, 3, 5, 4, S]
3: [S, 1, 2, 5, 3, 4, S]
4: [S, 2, 1, 4, 3, 5, S]
5: [S, 2, 3, 5, 4, 1, S]
6: [S, 2, 5, 3, 4, 1, S]
7: [S, 4, 1, 2, 3, 5, S]
8: [S, 4, 3, 5, 2, 1, S]
9: [S, 4, 5, 3, 2, 1, S]
10: [S, 5, 2, 3, 4, 1, S]
11: [S, 5, 3, 2, 1, 4, S]
12: [S, 5, 3, 4, 1, 2, S]
13: [S, 5, 4, 3, 2, 1, S]13가지 입니다. 이 정도면 매우 빠르게 해결 할 수 있을 것 같습니다. 이제 이 그래프를 봅시다. 역시 6개의 정점이 있고, 임의의 정점에서 나머지 모든 정점으로 이어지는 간선이 모두 존재합니다. 이 경우는 몇 가지의 해밀턴 회로를 구성할 수 있을까요?
5! = 120가지 입니다. P1에 5개의 지점 중 1개가 선택될 수 있고 P2에 나머지 4개의 지점 중 1개, 같은 방법으로 Pn을 채우면 (N-1)!가지입니다. 손으로 그려보기는 이제 어려워졌지만 그래도 컴퓨터로 구하기 어렵지 않습니다. 문제는 정점의 수가 늘어났을 때 입니다. N이 11로 늘어나면 출발 지점에서 나머지 10개의 지점을 돌아볼 수 있는 서로 다른 해밀턴 경로는 10! = 36,288,000가지가 됩니다. N = 21이 되면 가지 수는 243경 가지가 넘습니다. 일반적인 방법으로는 도저히 계산할 방법이 없습니다. 이걸 줄일 수 있는 방법이 없을까요? O(N!)에서 O(N)으로 줄일 수 있는 방법은 아직까지 발견되지 않았습니다. 하지만 이미 알려진 몇 가지 트릭으로 불필요한 탐색을 줄여 시간을 아낄 수는 있습니다.
3. DFS + 메모이제이션 = 다이나믹프로그래밍
해밀턴 경로 탐색의 과정을 살펴봅시다.
S-2-4를 탐색한 경우와 S-4-2를 탐색한 경우, 남은 지점은 1, 3, 5로 같습니다. 그러면 1, 3, 5를 통해 S로 돌아가는 방법 중 최적의 방법을 한 번만 구해두면 두 번의 탐색에서 적어도 한 번은 탐색 없이 저장된 값을 사용할 수 있지 않을까요?
남은 지점을 탐색하는 과정이 1-3-5-S 순으로 최적이었다면, S-4-2에 이어서 1 지점으로 탐색을 이어갈 경우, 반드시 1-3-5-S 순으로 탐색하는 것이 최적입니다. 그게 아니라면 이전에 S-2-4-1-3-5-S 라는 최적 탐색 결과가 나올 수 없으니까요. 그렇다면 이와 같은 식으로 이미 탐색한 결과를 기록하며 다음 탐색에 재활용한다면 시간을 많이 아낄 수 있습니다. 대충 짠 코드로 확인해보니 N = 6일 때, 이와 같은 재활용은 85회 발생하고 이로써 아낄 수 있는 탐색 횟수는 280회 정도 되는 것 같습니다. N = 16이면 1,474,575회의 재활용, 16,060,488,047,940회의 탐색 절감이 발생합니다. 효과가 엄청나네요.
4. 비트필드 인덱싱
탐색 여부를 확인할 수 있는 방법으로 저는 1차원 배열을 많이 사용합니다. N개의 정점이 있다면 길이 N의 check 배열을 만들어 0으로 초기화 합니다. 탐색을 한 정점은 1, 아닌 정점은 0으로 표시해서 관리합니다. 이 방법은 간단하고 직관적이지만 문제가 있습니다. 경로 탐색의 특성상 BFS가 되었든 DFS가 되었든 각 탐색 상황에 따라 탐색 상황을 계속 생성해야 합니다. 아까 보니 탐색 횟수도 어마어마하던데 이러다간 메모리가 남아나질 않겠어요.
어떤 지점을 표현하는 방법으로 그 지점의 번호 자체를 인덱스로 사용하는 방법이 있습니다. 이 방법이 먼저 설명했던 일반적이고 쉬운 방법입니다. 또 다른 방법은 인덱스에 전체 지점의 방문 상황을 모두 표현하는 것입니다. 이걸 구현하려면 각 지점을 비트로, 방문 상태를 비트 값으로 표현합니다.
앞서 예로 들었던 그래프의 탐색 상황을 보면 S(편의상 0번으로 표시합니다.), 2, 4번 정점을 방문했고 1, 3, 5번 정점은 방문하지 않았습니다. 그럼 총 6개의 비트가 이런 상태로 표현됩니다.
방문 상태 자체가 하나의 이진수로 표현되어 총 N개의 지점의 가능한 모든 방문 상태를 (1 << N) - 1까지의 숫자로 표현하는 게 가능합니다. TSP 문제는 다항 시간 내에 해결할 수 없다는 특징 때문에 보통 PS에서는 1초 이내에 N = 16 정도의 회로 구성을 요구합니다. N개 지점에서의 방문 상태 2N을 2차원 배열로 표현하면 공간복잡도는 O(N*2N)입니다. 1 << 16 = 65,536으로, N = 16일 때 TSP를 해결하기 위하여 int 값으로 dp 테이블을 구성한다면 대강 5Mb 안쪽으로 구조화가 가능합니다.
5. 점화식
그래서 dp를 구성할 수 있다는 결론인 것 같은데, 그럼 점화식이 있어야 합니다. 우선 상태를 정의하겠습니다.
현재 S(0번 지점)에서 출발하여 1, 6을 거쳐(순서는 무관) 3번 지점까지 왔습니다. 앞으로 남은 탐색 지점은 2, 4, 5, 7, 8, 9입니다. 지금까지의 탐색은 없었던 셈 치고(다르게 표현하자면 S, 1, 3, 6은 앞으로의 경로에 포함시키지 않습니다.), 남은 지점만 두고 탐색을 한다고 생각해봅시다. 다만, 출발 지점만 3입니다. 이렇게 시작된 탐색을 마쳤을 때, 6개의 정점들을 순회하는 최적의 경로를 다음과 같이 정의합니다.
dp[now][visit] = now에서 출발하여 visit에 포함되지 않는 지점만 방문해 얻는 최적 경로
dp[3][0001001011] = dp[3][75]앞의 식은 편의상 비트 상태를 이진수로 표현한 것입니다.
그럼 다시, dp[now][visit]은 어떻게 구할 수 있냐면, now에서 탐색을 이어갈 다음 지점 next를 찾습니다.
N = 전체 정점 개수
inf = 최악의 경로를 구성해도 나올 수 없는 비용
dist[i][j] = 정점 i에서 정점 j로 이동하는 비용
def tsp(now, visit):
# dp[now][visit]은 0으로 초기화 되어있습니다.
# 만약 dp[now][visit] != 0 이라면 이전에 구성된 값이 있으므로
# 그 값을 바로 반환하며 하위 탐색을 시도하지 않습니다.
if dp[now][visit]:
return dp[now][visit]
# dp[now][visit]의 값을 매우 큰 값으로 높입니다.
# 이후 탐색을 거쳐 점점 더 작은 값으로 갱신해 나갑니다.
dp[now][visit] = inf
# 0번 정점은 시작 지점이며 탐색을 출발할 때 이미 거쳤으므로 확인할 필요가 없습니다.
for next in range(1, N):
# dist[now][next] = inf 라면 연결 가능성이 없으므로 탐색하지 않습니다.
# 1 << next 는 현재 탐색을 이어가고자 하는 정점입니다.
# 만약 visit의 비트가 1이어서 & 연산의 결과가 1이라면
# 이전에 탐색한 곳이므로 탐색하지 않습니다.
if dist[now][next] = inf or visit & (1 << next): continue
# dp[now][visit]의 값을 하위 경로에 now에서 next로 이동하는 비용을 더해 갱신합니다.
dp[now][visit] = min(dp[now][visit], tsp(next, visit | (1 << next) + dist[now][next])
# 모든 하위 탐색을 마치고 값을 상위 탐색으로 반환합니다.
return dp[now][visit]아 참고로 이 코드는 제가 그냥 공부하고 짜본 코드라서 최적화는 고려하지 않았습니다. 그냥 이해한 과정을 그대로 구현한 코드입니다.
그런데 한 가지 문제가 있습니다. S에서 출발해 마지막으로 남은 정점을 방문했습니다. 이제 S로 돌아가야 하는데 S로 돌아가는 비트가 이미 출발할 때 채워져있습니다. 돌아가려는 탐색을 시도해도 탐색 조건이 맞지 않습니다. 이 문제를 해결하기 위해 모든 비트가 채워진 값을 출발 지점으로 돌아가는 간선의 가중치로 초기화 해두어야 합니다.
# 출발 지점인 0을 제외한 모든 정점에 대해
for i in range(1, N):
dp[i][(1 << N) - 1] = dist[i][0]
# (1 << N) - 1은 모든 비트가 채워진 상태,
# 모든 정점의 방문을 마친 상태입니다.
# 이 값을 i에서 0으로 돌아가는 간선의 가중치로 설정하면
# 상위 탐색에서 i로 탐색을 시도할 때
# dp[i][visit]의 값이 이미 0이 아닌 값으로 채워졌으므로
# 곧바로 출발 지점으로 돌아가는 가중치를 반환합니다.
여기서 짚고 넘어갈 부분이 있습니다. 외판원 순회 문제는 N개의 정점에서 출발 지점을 어디로 하든 상관이 없습니다. 해밀턴 경로가 아닌 해밀턴 회로를 구성하는 문제이기 때문입니다.
1번 정점에서 출발하든, 5번 정점에서 출발하든 두 회로 모두 같은 최적해를 갖고 경로의 구성 간선도 모두 동일합니다. 따라서 N개의 정점 중 0번 정점을 출발 정점으로 지정해 1회 탐색만 시도하는 것이 저는 좋았습니다. 다만 후술할 몇 가지 바리에이션에 따라 이 부분은 달라질 수 있습니다.
6. variation
가장 기본적인 형태의 TSP 문제입니다. 어느 도시를 출발지점으로 선택해도 상관 없고, 모든 도시를 한 번만 방문해 출발지점으로 돌아오는 최단 경로를 구해야 합니다.
뭐 있어보이는 척 하는 문제이지만 가능한 경우를 따져보면 동일 직선 상에 있는 3점이 존재하지 않는 입력에서는 최단 경로가 구해진다면 반드시 교차 지점이 없을 수 밖에 없습니다.
승패 기록으로 방향 그래프를 구성한 후에 외판원 순회를 시도합니다. 탐색이 끝나고 최적해를 역추적해 경로를 얻어야 합니다. 그리고 방문 가능한 지점만 선택해서 방문하는 문제입니다.
방문 지점의 선후 관계가 있습니다.
다익스트라로 전처리 후(런타임에 해도 상관은 없었습니다.) TSP를 돌립니다. 제한이 작은 편이라 무난하게 풀 수 있었어요.
최대 정점 100,000개, 간선 300,000개에 다익스트라를 돌리고 22개 지점에 대해 TSP를 돌리라고 하는 좀 악랄한 문제입니다.
시간 제한이 7초긴 한데 어디 하나 삐끗하면 바로 TLE 나와버려요.
출발 지점이 진짜로 정해져있습니다. 그리드로 주어진 구조를 탐색해 가중치를 먼저 구해야 합니다. 이후 그래프를 구성하고 TSP로 해결합니다. 그 외에 별 다른 특별한 점은 없습니다.
아, 도시락 배달은 출발 지점으로 돌아가지 않는 해밀턴 회로를 구하는 문제입니다. 이럴 때는 dp 테이블에서 방문 비트가 가득 찬 부분의 초기화를 안하면 됩니다.
순회에서 발생하는 각의 작은 부분의 최소치가 최대가 되도록 해야 합니다. 저도 아직 못풀어서 뭐 어떻게 해야 하는지는 모릅니다.
TSP 문제만 10일째 죽죽 풀어대도록 한 원인입니다. 가중치가 변합니다. 진짜 아직도 뭐가 틀렸는지 감이 안옵니다. 브루트 포스 돌렸다가 터지기도 하고 3차원 dp까지 생각해봤지만 그건 차마 못하겠고요.
끝
