TSP(The Traveling Salesperson Problem) -외판원 문제

TSP (외판원 문제) 란?

 home city에서 출발해 모든 city를 한번씩 거치고 다시 home city로 돌아오는 최단 경로를 구하는 문제이다.

 

즉, 아래와 같이 문제를 생각할 수 있다.

 

어떤 외판원이 n개의 도시를 방문할 계획을 수립하고 있다고 가정하자. 각 도시는 다른 모든 도시와 도로로 연결되어 있다. 출장 비용을 최소로 줄이기 위하여 외판원이 거주하고 있는 도시에서 각 도시를 한 번씩만 방문하고 다시 출발한 도시로 돌아오는 가장 최소 비용의 일주여행 경로를 찾고자 한다.

 

 

그림과 같이 각 도시의 위치가 표시된 미국 지도가 있다. 각 도시를 한 번씩 방문한다고 했을 때, 어떤 순서로 방문해야 가장 짧은 거리가 될까? (n - 1)! 즉 O(n!)이라는 결과가 나온다. 이렇게 비효율적인 방법은 쓸모가 없으므로  우리는 동적계획법을 사용하여  TSP를 풀어보려고 한다.

 

문제풀이

 

용어

• V :  모든 도시(노드)의 집합이고, A는 V의 부분집합
• D[vi][A] :  vi에서 A에 속한 노드만을 이용해 출발 도시(v1)으로 돌아가는 최단 경로의 길이
• A: V의 부분집합
• W: 그래프의 인접행렬
• 최적의 길이 :  minimum(W[1][j] + D[vj][A - {v1, vj}])
  • (이때 j는 2 이상, n 이하)
  • v1에서 vj로 가는 길이 + vj에서 v1, vj가 포함되어 있지 않은 정점들을 이용해 v1으로 가는 최적 경로

 

EX) 

A = {v3}인데, v3 -> v1으로 가는 경로가 없다(무한대)고 가정하면,

D[v2][A] = length[v2, v3, v1]이 되는데, v3 -> v1 경로가 없으므로 길이는 무한대가 된다

 

EX)

A = {v3, v4}이고, v4 -> v1의 길이가 있다고 가정한다면,

D[v2][A] = minimum(length[v2, v3, v4, v1], length[v2, v4, v3, v1])

 -> 앞의 path [v2, v3, v4, v1]이 최적의 경로가 된다

 

 

예시

 

 

 

 

A가 0개,1개,2개,3개인 경우로 나누어서 문제를 해결했다.

이 때, A가 많아질 수록 이전 단계에서 구했던 결과를 활용했는데, 이 과정은 다이나믹 프로그래밍의 Memoization을 활용한 것이다.