TSP (Traveling Salesperson Problem)

sue991·2021년 3월 23일
0

Algorithm

목록 보기
1/3

외판원 순회 문제

백준을 풀면서 코드는 간단하지만 이해하기 정말 어려웠던 문제이다.

대표적인 NP(Non-deterministic Polynomial time) 문제로, 시간복잡도가 다항시간내에 문제를 해결할 수 있는 문제이다.

ex) 2n , n! , nn 등..

즉, 아무리 알고리즘을 사용하여 시간을 최대한 줄여도 N이 커지면 시간이 기하급수적으로 늘어나는 것이다.

Example

출처 : https://www.acmicpc.net/problem/10971

4
0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0

외판원 순환 문제는 어디서 시작해도 결국 순환하는 길은 똑같기 때문에 시작 지점을 A(첫번째)으로 정해서 시작한다.

시간 복잡도를 줄이기 위해 BitMask를 사용하였다.

ex) A,B,C,D,E 가 있고 A에서 시작 할 때 BitmMask : 00001

TSP함수는 now에서 start로 돌아갈 때 드는 비용을 반환한다.

code

import sys
input = sys.stdin.readline

def TSP(now, visited):
    if dp[now][visited]:
        return dp[now][visited]
    
    if visited == (1<<N) -1:
        return W[now][0] if W[now][0] > 0 else sys.maxsize

    cost = sys.maxsize

    for i in range(1,N):
        if not (visited >> i)%2 and W[now][i]: # 방문한 적이 없고, 길이 있을 때
            tmp = TSP(i, visited|(1<<i))
            cost = min(cost, tmp + W[now][i])

    dp[now][visited] = cost
    return cost    
    
N = int(input())
W = [list(map(int, input().split())) for _ in range(N)]

dp = [[0]*(1<<N) for _ in range(N)]

print(TSP(0,1))
profile
AI Researcher

0개의 댓글