The Traveling Salesman and The Shortest Tree

The shortest tree is not actually that short.  “Computer scientist Richard Karp, of the University of California at Berkeley, showed that the traveling salesman problem is “NP-hard,” which means that it has no efficient algorithm.” After his article was published a number of computer scientists decided to create an algorithm to get as close to solving the Traveling Salesman Problem as they could. “A string of improved approximation algorithms have since emerged, after computer scientists began looking at the problem with fresh eyes. Although these approximations apply only to certain types of traveling salesman problems, the approach they embody holds great promise.”

The Shortest Tree is the outcome of one of these algorithms. It starts by connecting the shortest highway between two cities and that connection forms a branch. You add branches by finding more short highways to connect more cities. For example: city A and city B are connected by highway 1, then you connect city C to city B by highway 2 and so on and so forth. Until all the cities have been reached. “The resulting tree is not a possible solution to the traveling salesman problem because it does not create a round-trip route. But it can be converted into a round-trip by visualizing the branches as walls and then imagining walking along the tree, with your finger touching the wall, until you get back to where you started.”

It is kind of a cool way to look at the traveling salesman problem in a new way. “The resulting trip visits every city and returns to the starting point, but it is usually far from the shortest way to do so because it typically involves retracing steps many times — every wall in the tree is traversed twice, once on each side.” Though it may not be the fastest way to travel, it does give a person a new way of doing it. Also the idea of making the graph into a tree like figure is very interesting. The graphs we used in class with our dots and lines weren’t trees, but some of them did turn out into pretty interesting shapes.

Leave a Reply