외판원 순회 문제
덤프버전 :
분류
1. 개요[편집]
외판원 순회 문제 (Traveling Salesman Problem)는 조합 최적화 문제의 일종으로, NP-난해 집합에 속하기 때문에 계산 이론에서 해를 구하기 어려운 문제의 대표적인 사례로 많이 다룬다.
외판원 문제는 다음과 같이 설명할 수 있다. 어떤 외판원이 n개의 도시를 방문할 계획을 수립하고 있다고 가정하자. 각 도시는 다른 모든 도시와 도로로 연결되어 있다. 출장 비용을 최소로 줄이기 위하여 외판원이 거주하고 있는 도시에서 각 도시를 한 번씩만 방문하고 다시 출발한 도시로 돌아오는 가장 최소 비용의 일주여행 경로를 찾고자 한다.
그림과 같이 각 도시의 위치가 표시된 미국 지도가 있다. 각 도시를 한 번씩 방문한다고 했을 때, 어떤 순서로 방문해야 가장 짧은 거리가 될까?만약 도시가 20개라고 할 때 이 문제의 정답을 찾기 위해 다녀야 하는 총 경로의 수는 [math(20!)]다. 이 값은 얼마나 될까? [math(20!=2,432,902,008,176,640,000)]이다. 그러니까 약 240경 번의 경로를 다녀봐야 가장 짧은 경로를 찾을 수 있다. 문제는 단순하지만 정답은 실로 엄청나다.
2. 문제의 정의[편집]
외판원 순회 문제는 다음과 같이 그래프 이론의 용어로 엄밀하게 정의할 수 있다.
주어진 완전 그래프 G=(V, E)가, 연결되어 있고(connected) 가중치가 있는(weighted) 완전한(complete) 그래프라고 가정하자. 이 그래프에서 출발 정점에서 다른 모든 정점들을 방문하고 원래의 출발 정점으로 되돌아오는 순환 경로들 중에서 가중치의 합이 최소가 되는 순환 경로를 찾아라.
3. 문제의 해결[편집]
외판원 순회 문제는 NP-난해 집합에 속하는 문제라는 것이 증명되었다. 다항 시간에 이 문제를 해결할 수 있는 해결책을 아무도 찾지 못했으며, 다항 시간에 문제를 해결하지 못한다는 것도 아무도 증명하지 못했다.
3.1. 동적 계획법으로 풀기[편집]
외판원 순회 문제의 최적해는 동적 계획법으로 지수 시간에 풀 수 있다. 다음은 동적 계획으로 외판원 순회 문제를 해결하는 파이썬 소스 코드이다.
def travel (W):
n = len(W) - 1
size = 2 ** (n - 1)
D = [[0] * size for _ in range(n + 1)]
P = [[0] * size for _ in range(n + 1)]
for i in range(2, n + 1):
D[i][0] = W[i][1]
for k in range(1, n - 1):
for A in range(1, size):
if (count(A, n) == k):
for i in range(2, n + 1):
if (not isIn(i, A)):
D[i][A], P[i][A] = minimum(W, D, i, A)
A = size - 1
D[1][A], P[1][A] = minimum(W, D, 1, A)
return D, P
def minimum (W, D, i, A):
minValue = INF
minJ = 1
n = len(W) - 1
for j in range(2, n + 1):
if (isIn(j, A)):
m = W[i][j] + D[j][diff(A, j)]
if (minValue > m):
minValue = m
minJ = j
return minValue, minJ
3.2. 분기 한정으로 풀기[편집]
외판원 순회 문제의 최적해는 분기 한정(Branch-and-Bound)으로 지수 시간에 풀 수 있다. 다음은 분기 한정으로 외판원 순회 문제를 해결하는 파이썬 소스 코드이다.
def travel2 (W):
global minlength, opttour
n = len(W) - 1
PQ = PriorityQueue()
v = SSTNode(0)
v.path = [1]
v.bound = bound(v, W)
minlength = INF
PQ.put((v.bound, v))
while (not PQ.empty()):
v = PQ.get()[1]
if (v.bound < minlength):
for i in range(2, n + 1):
if (v.contains(i)):
continue
u = SSTNode(v.level + 1)
u.path = v.path[:]
u.path.append(i)
if (u.level == n - 2):
for k in range(2, n + 1):
if (not u.contains(k)):
u.path.append(k)
u.path.append(1)
if (length(u.path, W) < minlength):
minlength = length(u.path, W)
opttour = u.path[:]
else:
u.bound = bound(u, W)
if (u.bound < minlength):
PQ.put((u.bound, u))
def bound(v, W):
n = len(W) - 1
total = length(v.path, W)
for i in range(1, n + 1):
if (hasOutgoing(i, v.path)):
continue
min = INF
for j in range(1, n + 1):
if (i == j): continue
if (hasIncoming(j, v.path)): continue
if (j == 1 and i == v.path[len(v.path) - 1]): continue
if (min > W[i][j]): min = W[i][j]
total += min
return total
이 문서의 내용 중 전체 또는 일부는 2023-12-10 17:59:22에 나무위키 외판원 순회 문제 문서에서 가져왔습니다.