ปัญหาการเดินทางของพนักงานขาย

พนักงานขายคนหนึ่งอยู่ในเมืองหนึ่ง เขาต้องไปเยี่ยมชมเมืองอื่นๆ ทั้งหมดที่อยู่ในรายการ รวมทั้งมีค่าใช้จ่ายในการเดินทางจากเมืองหนึ่งไปยังอีกเมืองหนึ่งด้วย ค้นหาเส้นทางที่มีค่าใช้จ่ายต่ำสุดในการเยี่ยมชมเมืองทั้งหมดเพียงครั้งเดียวและกลับไปยังเมืองเริ่มต้น

กราฟจะต้องสมบูรณ์สำหรับกรณีนี้ ดังนั้นพนักงานขายจึงสามารถเดินทางจากเมืองใดก็ได้ไปยังเมืองใดก็ได้โดยตรง

ที่นี่เราต้องหาค่า 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 เพื่อทำเครื่องหมายว่าโหนดทั้งหมดมีการเยี่ยมชม

อินพุต - ค่า mask สำหรับปิดบังบางเมือง ตำแหน่ง

ผลลัพธ์ลบ; ค้นหาเส้นทางที่สั้นที่สุดในการเยี่ยมชมเมืองทั้งหมด

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