Understand Travelling Salesman Problem

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.

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.