Travelling Salesperson Problem

[Nishant2209]

I want to add Travelling Salesperson Problem under a new folder Branch and Bound.

The Traveling Salesman Problem (also called the Traveling Salesperson Problem or TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in [theoretical computer science and operations research.

For example, consider the graph shown in the figure on the right side. A TSP tour in the graph is 1-2-4-3-1. The cost of the tour is 10+25+30+15 which is 80. The problem is a famous NP-hard problem. There is no polynomial-time know solution for this problem. The following are different solutions for the traveling salesman problem.

Naive Solution:

1) Consider city 1 as the starting and ending point.

2) Generate all (n-1)! Permutations of cities.

3) Calculate the cost of every permutation and keep track of the minimum cost permutation.

4) Return the permutation with minimum cost.

Time Complexity: Θ(n!)

[Nishant2209]

I want to solve this problem so kindly assign this to me under hacktoberfest.

[shaswata-karan]

I want to solve this problem so kindly assign this to me under hacktoberfest.

[Nishant2209]

@shaswata-karan I have already solved it dude !!!

[chandraPrakash23]

Assign this task to me as I have already solved it.

[github-actions[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

[github-actions[bot]]

Please reopen this issue once you add more information and updates here. If this is not the case and you need some help, feel free to seek help from our Gitter or ping one of the reviewers. Thank you for your contributions!