Travelling Salesperson Problem using Dynamic Approach in C++

In this tutorial, we will learn about the TSP(Travelling Salesperson problem) problem in C++. In this tutorial, we will learn about what is TSP. Next, what are the ways there to solve it and at last we will solve with the C++, using Dynamic Approach. This is also known as Travelling Salesman Problem in C++.

Let’s take a scenario. Suppose you want to travel by car from your home to 4 places and at the end of it you want to return back to your home. Taking the problem as a worst case, let’s think all the 4 places are connected with each other [we are taking the worst case because we don’t know in details about the places ].

TSP USING DYNAMIC APPROACH in C++

To solve the problem we have some exact conditions :

  1.      You can only visit each place only once. Once visited you can’t visit the place.
  2.       Most importantly you have to find the shortest path. [This condition will differentiate the problem with Hamiltonian Problem.

 

We know what are the conditions we have to follow. Now we are going to see what are the process we can use in this problem.




Approaches to solve TSP :

  1.      Dynamic Approach
  2.      Brute Force Approach
  3.      Backtracking Approach
  4.      Branch and Bound
  5.      Genetic Algorithm
  6.      Simulated Annealing

– We are not going to use every approach to solve the problem. We are going to pick up the Dynamic Approach to solve the problem.

Now the question is why Dynamic approach?

Brute Force (or we can tell Backtracking Approach ) solves the problem, checking all the possible solutions to solve it. That will take O(n^n) time to solve it. But in the Dynamic Approach, we can divide the problem into subproblems.

Let’s check the coding of TSP using Dynamic Approach.

Travelling Salesperson Problem in C++

#include<iostream>
using namespace std;

#define MAX 9999

int n=4; // Number of the places want to visit

 //Next distan array will give Minimum distance through all the position
int distan[10][10] = {                
                    {0, 10, 15, 20},
                    {10, 0, 35, 25},
                    {15, 35, 0, 30},
                    {20, 25, 30, 0}
};
int completed_visit = (1<<n) -1;

int DP[16][4];


int  TSP(int mark,int position){

  if(mark==completed_visit){      // Initially checking whether all
                                  // the places are visited or not
    return distan[position][0];
  }
  if(DP[mark][position]!=-1){
     return DP[mark][position];
  }

  //Here we will try to go to every other places to take the minimum
  // answer
  int answer = MAX;

  //Visit rest of the unvisited cities and mark the . Later find the 
  //minimum shortest path
  for(int city=0;city<n;city++){

    if((mark&(1<<city))==0){

      int newAnswer = distan[position][city] + TSP( mark|(1<<city),city);
      answer = min(answer, newAnswer);
    }

  }

  return DP[mark][position] = answer;
}

int main(){
    /* initialize the DP array */
    for(int i=0;i<(1<<n);i++){
        for(int j=0;j<n;j++){
            DP[i][j] = -1;
        }
    }
  cout<<"Minimum Distance Travelled by you is "<<TSP(1,0);

return 0;
}

Output :

  Minimum Distance Travelled by you is 80


Time Complexity :

         O(n^2 * 2^n)

Thus we have learned How to solve Travelling Salesperson Problem in C++.

Put your doubts and questions in the below comment section.

You may also learn:


Leave a Reply

Your email address will not be published. Required fields are marked *