Understand Travelling Salesman Problem

Board Infinity -

Introduction

The Traveling Salesman Problem, or TSP, involves a salesperson visiting various cities. The salesperson must make round-trip trips to all of the cities, starting and finishing in the same place. The difficulty with the situation is that the traveling salesman wants to cut the length of the trip in half. An optimization issue exists. In this, we must streamline our travel path. Traveling Salesperson is a Dynamic Programming problem which requires a masking approach. An NP-hard problem exists here.

Approach

  1. We must first create two primary data holders.
  2. The first of these is a list that can contain the city indices in terms of the input city distance matrix.
  3. And the second is the array, which represents our outcome.
  4. The specified adjacency matrix, tsp[][], should be traversed for each city, and the cost to reach any city from the present city should be updated if it is less than the current cost.
  5. Then, using the previous step, generate the minimum route cycle and report its minimum cost.

Code

The outcomes of the subproblems are being stored in this case utilizing the DP array. To keep track of the cities visited, we employ bit masking methods.

#include<bits/stdc++.h>
using namespace std;
#define MAX 999999


int n=4;
int Adj_matrix[10][10] = {
        {0,10,15,20},
        {10,0,35,25},
        {15,35,0,30},
        {20,25,30,0}
};

int Visited = (1<<n) - 1;
int dp[16][4];

int  TSP_DP(int mask,int pos){
    if(mask==Visited){
 return Adj_matrix[pos][0];
 }

 if(dp[mask][pos]!=-1){
   return dp[mask][pos];
 }
 int ans = MAX;
 for(int city=0;city<n;city++){
 if((mask&(1<<city))==0){
 int newAns = Adj_matrix[pos][city] + TSP_DP( mask|(1<<city), city);
 ans = min(ans, newAns);
 }
 }
 return dp[mask][pos] = ans;
}

int main(){
    for(int i=0;i<(1<<n);i++)
    {
        for(int j=0;j<n;j++)
        {
            dp[i][j] = -1;
        }
    }
 cout<<"Minimum Cost is: "<<TSP_DP(1,0);
 return 0;
}


Output: 

Minimum Cost is: 80

write your code here: Coding Playground

Complexity Analysis

Time Complexity: O (n^22^n)

Here n denotes the number of cities To identify a route to the remaining (n-1) cities, each sub-problem will require O (n) time. Total time complexity is therefore O(n2n) * O (n) = O (n^22^n) (n^22^n)

Space Complexity: O (n^2n) To store all the subproblems in memory.