Travelling Salesman Problem (TSP)

Travelling Salesman Problem

Problem Statement

Given a set of cities and distance between every pair of cities as an adjacency matrix, the problem is to find the shortest possible route that visits every city exactly once and returns to the starting point.

Travelling Salesman Problem Example 1

Input

Input

Output

Output

TSP Example 2
Input –

TSP Input

Output –
Minimum weight Hamiltonian Cycle
: EACBDE= 32

Simple Approach

  • Consider city 1 as the starting and ending point. Since the route is cyclic, we can consider any point as a starting point.
  • Now, we will generate all possible permutations of cities which are (n-1)!.
  • Find the cost of each permutation and keep track of the minimum cost permutation.
  • Return the permutation with minimum cost.

C++ Implementation

Java Implementation

Python Implementation

Time complexity: O(N!), Where N is the number of cities.
Space complexity: O(1).


Travelling Salesman Problem Using Dynamic Programming

In travelling salesman problem algorithm, we take a subset N of the required cities that need to be visited, the distance among the cities dist, and starting city s as inputs. Each city is identified by a unique city id which we say like 1,2,3,4,5………n

Here we use a dynamic approach to calculate the cost function Cost(). Using recursive calls, we calculate the cost function for each subset of the original problem.

To calculate the cost(i) using Dynamic Programming, we need to have some recursive relation in terms of sub-problems.

We start with all subsets of size 2 and calculate C(S, i) for all subsets where S is the subset, then we calculate C(S, i) for all subsets S of size 3 and so on.

There are at most O(n2^n) subproblems, and each one takes linear time to solve. The total running time is, therefore, O(n^22^n). The time complexity is much less than O(n!) but still exponential. The space required is also exponential.

C Implementation of DP approach

C++ Implementation of DP approach

Python Implementation of DP approach

Java Implementation of DP approach

Time Complexity: O(N^2*2^N).


Greedy Approach

  • First of all, we have to create two primary data holders.
    • First of them is a list that can hold the indices of the cities in terms of the input matrix of distances between cities
    • And the Second one is the array which is our result
  • Perform traversal on the given adjacency matrix tsp[][] for all the city and if the cost of reaching any city from the current city is less than the current cost the update the cost.
  • Generate the minimum path cycle using the above step and return their minimum cost.

C++ Implementation of Greedy Approach

Java Implementation of Greedy Approach

Python Implementation of Greedy Approach

Time complexity: O(N^2*logN), Where N is the number of cities.
Space complexity: O(N).


Practice Questions


Frequently Asked Questions

Q: Which algorithm is used for the Travelling salesman problem?
A: Travelling Salesman Problem uses Dynamic programming with masking algorithm.

Q: What is the complexity of the Travelling salesman problem?
A: The complexity of TSP using Greedy will be O(N^2LogN) and using DP will be O(N^22^N).

Q: How is this problem modeled as a graph problem?

A: The TSP can be modeled as a graph problem by considering a complete graph G = (V, E).A tour is then a circuit in G that meets every node. In this context, tours are sometimes called Hamiltonian circuits.

Q: What is the difficulty level of the Travelling salesman problem?
A: It is an NP-hard problem.

Previous Post
GCD of Two Numbers

GCD of Two Numbers (C, Python, Java) With Examples

Next Post
Difference Between C and Java

​​​​Difference Between C and Java

Total
0
Share