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

개요

외판원 순회 문제 (Traveling Salesman Problem)는 조합 최적화 문제의 일종으로, NP-난해 집합에 속하기 때문에 계산 이론에서 해를 구하기 어려운 문제의 대표적인 사례로 많이 다룬다.

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

 

재귀적 관계식

 

예시

 

D[vi][A] Table

 

알고리즘

void travel(int n, const number W[][], index P[][], number& minlength) {
	index i, j, k;
	number D[1..n][subset of V-{v1}];

	for(i=2; i<=n; i++) 
		D[i][∅] = W[i][1];

	for(k=1; k<= n-2; k++)
		for(all subsets A⊆V-{v1} containing k vertices)
			for(i such that i≠1 and vi is not in A){
				D[i][A] = min(j:vj∈A)(W[i][j]+D[j][A-{vj}]);
				P[i][A] = value of j that gave the minimum;
			}

	D[1][V-{v1}] = min(2≤j≤n)(W[1][j]+D[j][A-{v1,vj}]);
	P[1][V-{v1}] = value of j that gave the minimum;
	minlength = D[1][V-{v1}] 
}

 

시간 복잡도

 

비고