You are using an outdated browser. Please update your browser for a better user experience.

Travelling Salesman Greedy Approach

As you may know, the Traveling Salesman Problem is a classic NP-Hard problem. That means there are no polynomial-time solutions to this problem. Discover such a solution and you'll be the richest person on earth. Well, not really. Jeff Bezos is pretty !%@ing rich.

In any case, the problem is described as follows:

A salesman must travel to some set of different cities and then arrive back home at their starting city. And they want to find the shortest path which satisfies this condition.

This problem is represented by a graph G = {V,E,s}, where the vertices in the V set represent the cities the salesman must travel to and the edges in the E set represent the distance between two cities. The salesman starts at vertex s and must end there as well.

How can you design a polynomial time algorithm which won't necessarily create the SHORTEST path that the salesman can take, but a path which is reasonably close to the optimal solution?

Hint: For solution one, think real simple.

Hint: For a second, more nuanced solution, try to involve a minimum spanning tree.