한 영업 사원이 도시에 있고, 그는 나열된 다른 모든 도시를 방문해야 하며, 한 도시에서 다른 도시로 이동하는 비용도 제공됩니다. 모든 도시를 한 번 방문하는 비용이 최소인 경로를 찾아 출발 도시로 돌아갑니다.
이 경우 그래프는 완전해야 영업 사원이 어느 도시에서나 직접 도시로 이동할 수 있습니다.
여기서 우리는 최소 가중치 Hamiltonian Cycle을 찾아야 합니다.
입력 및 출력
Input: Cost matrix of the matrix. 0 20 42 25 30 20 0 30 34 15 42 30 0 10 10 25 34 10 0 25 30 15 10 25 0 Output: Distance of Travelling Salesman: 80
알고리즘
travellingSalesman (mask, pos)
테이블 dp가 있고 VISIT_ALL 값이 방문하여 모든 노드를 표시합니다.
입력 - 일부 도시, 위치를 마스킹하기 위한 마스크 값입니다.
출력 마이너스; 모든 도시를 방문할 수 있는 최단 경로를 찾으세요.
Begin if mask = VISIT_ALL, then //when all cities are visited return cost[pos, 0] if dp[mask, pos] ≠ -1, then return dp[mask, pos] finalCost := ∞ for all cities i, do tempMask := (shift 1 left side i times) if mask AND tempMask = 0, then tempCpst := cost[pos, i] + travellingSalesman(mask OR tempMask, i) finalCost := minimum of finalCost and tempCost done dp[mask, pos] = finalCost return finalCost End
예
#include<iostream> #define CITY 5 #define INF 9999 using namespace std; int cost[CITY][CITY] = { {0, 20, 42, 25, 30}, {20, 0, 30, 34, 15}, {42, 30, 0, 10, 10}, {25, 34, 10, 0, 25}, {30, 15, 10, 25, 0} }; int VISIT_ALL = (1 << CITY) - 1; int dp[16][4]; //make array of size (2^n, n) int travellingSalesman(int mask, int pos) { if(mask == VISIT_ALL) //when all cities are marked as visited return cost[pos][0]; //from current city to origin if(dp[mask][pos] != -1) //when it is considered return dp[mask][pos]; int finalCost = INF; for(int i = 0; i<CITY; i++) { if((mask & (1 << i)) == 0) { //if the ith bit of the result is 0, then it is unvisited int tempCost = cost[pos][i] + travellingSalesman(mask | (1 << i), i); //as ith city is visited finalCost = min(finalCost, tempCost); } } return dp[mask][pos] = finalCost; } int main() { int row = (1 << CITY), col = CITY; for(int i = 0; i<row; i++) for(int j = 0; j<col; j++) dp[i][j] = -1; //initialize dp array to -1 cout << "Distance of Travelling Salesman: "; cout <<travellingSalesman(1, 0); //initially mask is 0001, as 0th city already visited }
출력
Distance of Travelling Salesman: 80