외판원 문제 (Traveling Salesman Problem, TSP)

외판원 문제 (Traveling Salesman Problem, TSP)

TSP문제는 해밀토니안 사이클을 이용해 다음과 같이 정의된다.

가중치 그래프 G = (V, E)가 주어졌다. G에서 모든 가능한 해밀토니안 사이클 중에서 경로의 합이 최소인 사이크르이 경로의 합을 구하라.

 

완전 탐색을 이용하면 항상 확실한 해를 구할 수 있다. 임의의 한 점을 출발점으로 잡고 아직 가보지 않은 모든 이웃 정점으로 계속 이동하면서 검사하면 된다. 그래프가 N개의 정점을 갖는 완전그래프라면 모든 해밀토니안 사이클은 (N-1)! 개가 된다. 

 

1. 임의의 도시를 출발점으로 잡는다.
2. 이 도시를 시작으로 하여 (N-1)!가지의 순열 객체를 생성한다.
3. 모든 순열 객체에서 경로의 합을 구하고, 경로의 합이 최소인 순열 객체와 경로 합을 찾는다.
4. 최소 경로의 합을 반환한다.

도시의 수가 n이라면 이 알고리즘의 복잡도는 O(n!)이고, n이 조금만 커지더라고 계산량이 비현실적으로 늘어난다.

따라서 계산량을 줄이거나 보다 현실적인 알고리즘이 필요하다.

 

백트래킹과 분기한정 기법을 사용하면 가지치기를 통해 상태공간트리를 보다 효율적으로 탐색할 수 있다. 

 

 

 

관련 알고리즘 문제

from itertools import permutations
import sys
input = sys.stdin.readline

n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
arr = [i for i in range(n)]

ans = 1e9
for p in permutations(arr, n):
    val = 0
    for i in range(n):
        if graph[p[i]][p[(i+1)%n]] == 0:
            val += 1e9
        else:
            val += graph[p[i]][p[(i+1)%n]]

    ans = min(ans, val)

print(ans)