외판원 순회 문제(Traveling Salesman Problem, TSP) 소스코드

1. 개요

  외판원 순회 문제 크게 여러 도시들이 있고 한 도시에서 다른 도시로 이동하는 비용이 모두 주어졌을 때, 모든 도시들을 단 한 번씩 방문하는 최소 경로 및 비용을 물어보는 문제이거나 추가로 원래 시작점으로 돌아가는 최소 경로 및 비용을 구하는 문제이다.

2. 모든 경로 출력 소스코드

  아래 소스코드는 모든 도시를 방문하는 경로와 비용을 출력해주는 소스코드이다.

#include <cstdio> #include <algorithm> #include <climits> using namespace std; int N; int W[10][10]; bool visited[10]; int city[10]; void tsp(int node, int costSum, int count) { visited[node] = true; city[count - 1] = node; if (count == N) { for (int i = 0; i < N; i++) { printf("%d ", city[i]); } printf(" : %d\n", costSum); visited[node] = false; city[count - 1] = -1; return; } for(int i=0;i<N;i++){ if(!visited[i] && W[node][i] != 0){ tsp(i, costSum+W[node][i], count+1); } } visited[node] = false; city[count - 1] = -1; } int main(){ scanf("%d", &N); for (int i = 0; i < N; i++) { city[i] = -1; visited[i] = false; for (int j = 0; j < N; j++) scanf("%d", &W[i][j]); } printf("\n"); tsp(0, 0, 1); tsp(1, 0, 1); tsp(2, 0, 1); tsp(3, 0, 1); return 0; }

입력데이터는 다음과 같다.

4 0 20 28 30 25 0 27 28 30 35 0 29 280 29 27 0

결과는 다음과 같다.

0 1 2 3 : 76 0 1 3 2 : 75 0 2 1 3 : 91 0 2 3 1 : 86 0 3 1 2 : 86 0 3 2 1 : 92 1 0 2 3 : 82 1 0 3 2 : 82 1 2 0 3 : 87 1 2 3 0 : 336 1 3 0 2 : 336 1 3 2 0 : 85 2 0 1 3 : 78 2 0 3 1 : 89 2 1 0 3 : 90 2 1 3 0 : 343 2 3 0 1 : 329 2 3 1 0 : 83 3 0 1 2 : 327 3 0 2 1 : 343 3 1 0 2 : 82 3 1 2 0 : 86 3 2 0 1 : 77 3 2 1 0 : 87

3. 최소 비용 경로 출력 소스코드

  아래 소스코드는 위 소스코드를 조금 변경하여 조금이나마 계산 횟수를 줄인 소스코드이다.

#include <cstdio> #include <algorithm> #include <climits> using namespace std; int N; int cost[10][10]; bool visited[10]; int lowCost = INT_MAX; void tsp(int node, int costSum, int count) { visited[node] = true; if (count == N) { lowCost = min(lowCost, costSum); visited[node] = false; return; } for(int i=0;i<N;i++){ if(!visited[i] && cost[node][i] != 0){ if (costSum + cost[node][i] < lowCost) { //여기 코드로 횟수 줄임 tsp(i, costSum + cost[node][i], count + 1); } } } visited[node] = false; } int main(){ scanf("%d", &N); for (int i = 0; i < N; i++) { visited[i] = false; for (int j = 0; j < N; j++) scanf("%d", &cost[i][j]); } printf("\n"); for (int i = 0; i < N; i++) tsp(i, 0, 1); printf("%d\n", lowCost); return 0; }

입력데이터는 위와 똑같으며 결과는 최소값이 나온다.