Adobe Interview Question
Data ScientistsCountry: United States
The Travelling Salesman Problem belongs to the NP-Hard problems set and the decision version of the problem belongs to the NP-Complete problems set.
One probable approach I can think of is Branch and Bound, which can perform O(N^2) at the worst case.
I have read about a Stanford-McGill team which figured out the most optimal Solution for the TSM problem in 2013. But have not seen the paper.
If anyone knows of a better approach, please post it here.
The Travelling Salesman Problem belongs to the NP-Hard problems set and the decision version of the problem belongs to the NP-Complete problems set.
One probable approach I can think of is Branch and Bound, which can perform O(N^2) at the worst case.
I have read about a Stanford-McGill team which figured out the most optimal Solution for the TSM problem in 2013. But have not seen the paper.
If anyone knows of a better approach, please post it here.
The travelling salesman problem belong to the NP-Hard problems set and the decision version of the problem belongs to the NP-Complete problems set.
- Vasanth November 08, 2015The best algorithm I can think of to solve the problem can be Branch and Bound, which can be O(N^2) at the worst case.
If there is a better approach please do post here.
I remember reading about a Stanford-McGill team achieving a better approach in 2013.
But havent seen the actual paper.