Vấn đề về nhân viên bán hàng đi du lịch

Một nhân viên bán hàng ở một thành phố, anh ta phải đi thăm tất cả các thành phố khác đã được liệt kê, chi phí đi lại từ thành phố này đến thành phố khác cũng được cung cấp. Tìm tuyến đường có chi phí tối thiểu để tham quan tất cả các thành phố một lần và quay trở lại thành phố xuất phát của anh ấy.

Biểu đồ phải hoàn chỉnh cho trường hợp này để nhân viên bán hàng có thể trực tiếp đi từ bất kỳ thành phố nào đến bất kỳ thành phố nào.

Ở đây chúng ta phải tìm Chu trình Hamilton có trọng số tối thiểu.

Đầu vào và Đầu ra

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

Thuật toán

travellingSalesman (mask, pos)

Có một bảng dp và giá trị VISIT_ALL để đánh dấu tất cả các nút đã được truy cập

Đầu vào - giá trị mặt nạ để che một số thành phố, vị trí.

Đầu ra trừ đi; Tìm tuyến đường ngắn nhất để tham quan tất cả các thành phố.

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

Ví dụ

#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
}

Đầu ra

Distance of Travelling Salesman: 80