Press "Enter" to skip to content

Solving the Traveling Salesman Problem in R

Tomaz Kastrun gives us a solution to the Traveling Salesman Problem:

Travelling Salesman Problem is an NP-complete problem and an old mathematical problem. For this useless function, we will look for the nearest city from the previous city (or starting point) and repeat until we visit all cities. The greedy solution is fairly simplified but one disadvantage; it might not give you the best path (optimal solution) and proving that the solution is correct is an additional issue 

As Tomaz notes, this is not guaranteed to be the best solution, just a solution. Considering that TSP is NP-hard, if Tomaz did have a globally optimal solution for us, he certainly wouldn’t be calling it ‘useless-useful’ but instead would be calling it “My prize-winning algorithm.”