Algorithem/알고리즘 이론

[TSP] 외판원 순회

jamong5 2023. 6. 15. 10:26

 

문제 정의 - 해밀턴 순환

N개의 연결된 도시가 있고, 도시들을 연결하는 길이 있습니다. 길을 통과하는데는 비용이 듭니다. 길마다 비용은 다를 수 있고, 오는길과 가는길의 비용도 다를 수 있습니다.

모든 도시를 딱 한번씩, 전부 방문하고나서 출발 도시로 되돌아오는 방법 가운데 최소 비용의 길을 알고 싶습니다. (최소 비용 해밀턴 순환)

  • 해밀턴 경로: 모든 점을 딱 한번씩만 지나는 경로
  • 해밀턴 순환: 시작점과 끝점이 같은 해밀턴 경로

 

NP-Hard

Traveling Salesman Problem은 조합 최적화 문제의 일종입니다.

대표적인 NP-Hard 문제로 다항시간에 풀 수 있는 해법이 밝혀지지 않았고 그 가능성도 매우 낮은 문제입니다.

간단해보였지만 생각보다 빡센 문제네요ㄷㄷ

 

시간복잡도 O(N!)

O(N!) 은 15!부터 조단위가 넘어가는 연산입니다.

12! = 약 5억

13! = 약 60억

14! = 약 870억

물론 이건 브루트하게 고려했을 때 입니다.

 

디테일하게 보면 단축시킬 수 있다.

순환을 찾기 때문에 시작점을 어디로 잡든 최소비용은 같습니다. 즉 시작점은 한점만 찾으면 되고, 연결된 길이 없는 노드들도 있을 수 있기 때문에 경우의 수가 줄어들것입니다. 여기에서 DP를 추가하면 중복 연산을 줄일 수 있습니다.

추가로, 방문한 노드들을 표현하는 visit의 경우에 방문 노드 '순열'이 아닌 "조합"에 초점을 두고 2진법화 하여 비트마스킹으로 체크하면 연산 속도를 줄일 수 있습니다.

가장 핵심이 되는 부분은 DP 활용입니다.

 

DP 활용하기

DP 를 어떻게 적용할거냐, dp[현재 위치][지금까지 들른점 집합] = 지금부터 도착지까지 최소 비용 을 저장합니다.

DFS로 그래프 탐색을 진행했고, 재귀를 어떻게 타야하는지 자세한 사항은 제일 밑에서 코드를 통해 설명하겠습니다.

 

시간 복잡도 O($N^2$*$2^N$)

dp 테이블에 채워야하는 칸 개수는

(들를 수 있는 모든 조합) = (원소 N개의 부분집합) = $2^N$

현재 위치 = N

이기 때문에, $2^N$*N 입니다.

각 칸을 채우기 위해서는, 각 칸의 상태에서 (연결된 다음 칸의 DP) + (다음 칸까지 가는데 드는 비용)들 중 최소값을 구해야하기 때문에, N의 연산이 필요합니다.

즉 DP 를 활용하는 경우 시간복잡도가 O($2^N$*N*N) 이 됩니다.

 

코드 및 설명

재귀를 타면서 DP 테이블을 채우는게 목표입니다. 시작 노드의 번호는 0으로 지정했습니다. 예시 설명에서는 노드 4개(N=4)로 가정하겠습니다.

 

위에서 이야기했듯, DP 테이블의 헹과 열은 [현재위치][지금까지 들른 점 집합] 으로 구성되고, "해당 상태에서 0까지 돌아가는데 드는 최소비용" 을 채워넣을 것입니다. [지금까지 들른 점 집합] 은 비트마스킹으로 표현할거고 비트와 노드 대응 위치는 코드 작성 편의성을 위해 "3번 2번 1번 0번" 순서로 했습니다.

예를들어 1,3번을 들렀고, 지금 1번에 위치해있다면 [1][1010(2) = 10] 이 됩니다. 

 

일단 DP 테이블에서 제일 먼저 채울 수 있는 부분은, 모든 노드를 다 돌고 0으로 돌아오기 직전 상태입니다.

마지막 노드 -> 0 의 비용이 DP 테이블에 채워질 값이 되겠고, 모든 노드를 다 돌았기 때문에 1111(2) 이 들른 집합이 되겠습니다.

즉, DP[N][1111(2)] = COST[N][0] 으로 채울 수 있습니다.

 

빈 DP 배열을 만들고 초기값을 채워주었으면 이제 순회를 돌면서 나머지를 채우면 됩니다.

그래프 순회는 dfs로 돌았습니다. input은 현재위치와 들른 집합. 즉 현재상태 이고, return 값은 input상태에서 도착지까지의 최소 비용입니다.

import sys
def solution(input) :
    N = int(input().strip())
    DP = [[0 for _ in range(2**N)] for _ in range(N)] #[현위치][조합],남은 길 최소비용
    # 출발 노드 0, 다 들르고 다시 0으로 돌아가는 케이스의 남은 길 최소비용
    COST = []
    for _ in range(N) :
        COST.append(list(map(int,input().split())))
    for i in range(N) :
        DP[i][-1] = COST[i][0]

    def dfs(now,visit) :
        if DP[now][visit] : # 남은 길 최소비용이 정해진 경우
            return DP[now][visit]
        mc = 999999999999
        for n in range(N) : # 다음 들를 곳은
            if 1<<n & visit : continue # 이미 들렀던 곳이면 패쓰
            dcost = COST[now][n] # 다음 비용
            if dcost == 0 : continue # 0원 길은 없는 길
            mc = min(mc,dfs(n,visit+(1<<n))+dcost)
        DP[now][visit] = mc
        return mc
    
    print(dfs(0,1))


input = sys.stdin.readline
solution(input)