algorithm
여행 세일즈맨
수색…
비고
여행 세일즈맨 (Traveling Salesman) 문제는 정점 당 N
번 정점을 통과하는 최소 비용을 찾는 문제입니다. 정점 i
에서 정점 j
까지 이동하는 비용 cost[i][j]
입니다.
이 문제를 해결하는 알고리즘에는 두 가지 유형이 있습니다. 정확한 알고리즘 및 근사 알고리즘
정확한 알고리즘
- 무차별 공격 알고리즘
- 동적 프로그래밍 알고리즘
근사 알고리즘
첨가되는
무차별 공격 알고리즘
모든 정점을 통과하는 경로는 정점을 어떤 식 으로든 정렬하는 것과 동일합니다. 따라서 모든 꼭지점을 통과하는 최소 비용을 정확히 한 번 계산하기 위해 N!
1
에서 N
까지의 수의 순열.
가짜 코드
minimum = INF
for all permutations P
current = 0
for i from 0 to N-2
current = current + cost[P[i]][P[i+1]] <- Add the cost of going from 1 vertex to the next
current = current + cost[P[N-1]][P[0]] <- Add the cost of going from last vertex to the first
if current < minimum <- Update minimum if necessary
minimum = current
output minimum
시간 복잡성
N!
이 있습니다 N!
순열이 진행되고 각 경로의 비용이 O(N)
에서 계산되므로이 알고리즘은 정답을 출력하기 위해 O(N * N!)
시간이 필요합니다.
동적 프로그래밍 알고리즘
경로를 (순서대로) 고려하면 다음과 같습니다.
(1,2,3,4,6,0,5,7)
와 경로
(1,2,3,5,0,6,7,4)
정점에서가는 비용 1
정점 2
정점에 3
동일하게 유지, 그래서 왜 다시 계산해야합니까? 이 결과는 나중에 사용하기 위해 저장할 수 있습니다.
dp[bitmask][vertex]
는 비트 bitmask
의 해당 비트가 vertex
에서 끝나는 1
로 설정된 모든 정점을 통과하는 최소 비용을 나타냅니다. 예 :
dp[12][2]
12 = 1 1 0 0
^ ^
vertices: 3 2 1 0
12
는 이진수로 1100
을 나타내므로 dp[12][2]
는 그래프에서 정점 2에서 끝나는 경로를 통해 정점 2
와 3
을 통과하는 것을 나타냅니다.
따라서 우리는 다음과 같은 알고리즘을 가질 수 있습니다 (C ++ 구현).
int cost[N][N]; //Adjust the value of N if needed
int memo[1 << N][N]; //Set everything here to -1
int TSP(int bitmask, int pos){
int cost = INF;
if (bitmask == ((1 << N) - 1)){ //All vertices have been explored
return cost[pos][0]; //Cost to go back
}
if (memo[bitmask][pos] != -1){ //If this has already been computed
return memo[bitmask][pos]; //Just return the value, no need to recompute
}
for (int i = 0; i < N; ++i){ //For every vertex
if ((bitmask & (1 << i)) == 0){ //If the vertex has not been visited
cost = min(cost,TSP(bitmask | (1 << i) , i) + cost[pos][i]); //Visit the vertex
}
}
memo[bitmask][pos] = cost; //Save the result
return cost;
}
//Call TSP(1,0)
이 줄은 조금 혼란 스러울 수 있으므로 천천히 살펴보십시오.
cost = min(cost,TSP(bitmask | (1 << i) , i) + cost[pos][i]);
여기, bitmask | (1 << i)
는 비트 bitmask
의 i 번째 비트를 1로 설정하는데, 이는 i 번째 꼭지점이 방문되었음을 나타냅니다. 쉼표 다음의 i
는 새로운 "마지막"버텍스를 나타내는 함수 호출에서 새로운 pos
를 나타냅니다. cost[pos][i]
는 정점 pos
에서 정점 i
까지의 이동 비용을 더하는 것입니다.
따라서이 라인은 방문한 적이없는 다른 모든 정점으로 이동할 수있는 최소 값으로 cost
값을 업데이트하는 것입니다.
시간 복잡성
함수 TSP(bitmask,pos)
보유 2^N
대한 값은 bitmask
및 N
값 pos
. 각 함수는 O(N)
시간 동안 실행됩니다 ( for
루프). 따라서이 구현은 정답을 출력하기 위해 O(N^2 * 2^N)
시간이 필요합니다.