The traveling salesman, Steiner trees, and bubbles

Be forewarned: Of course no solution here, but rather a train of thought I want to jot down…if not for your consideration, then for me to pick up later. Also, this post mentions soap film, not bubbles. But who doesn’t like bubbles? Same generally can’t be said for soap film.

The Traveling Salesmen Problem is a hard problem. In fact, it’s NP-hard. Here’s a description (thanks, Wikipedia!):

The Traveling Salesman Problem describes a salesman who must travel between N cities. The order in which he does so is something he does not care about, as long as he visits each one during his trip, and finishes where he was at first. Each city is connected to other close by cities, or nodes, by airplanes, or by road or railway. Each of those links between the cities has one or more weights (or the cost) attached. The cost describes how “difficult” it is to traverse this edge on the graph, and may be given, for example, by the cost of an airplane ticket or train ticket, or perhaps by the length of the edge, or time required to complete the traversal. The salesman wants to keep both the travel costs, as well as the distance he travels as low as possible.

The salesmen needs to find a single loop to hit every city, and our objective is to find the least cost to make that loop. Let’s assume that cost is the distance: the salesman wants to get home as fast as possible.

OK, put that on ice for a moment and switch gears.

Another problem that also involves graphs is the Steiner Tree Problem, which is a little different. While you can still consider many cities as with the above problem, in this case we’re talking about road planning. How do you connect all the cities with the minimum distance of road pavement? In more general terms, what is the minimum length of edges that include all fixed points in the graph?

I was first introduced to Steiner Trees via this wonderful video by the good folks at Numberphile:

What astounded me is that we can “use nature” by exploiting an inherent property: get to the lowest energy state possible. Whether its water rolling down a hill to find bottom, or lightening finding the optimum path to reach ground, nature generally looks for the easiest path to get to the lowest possible energy state. In this particular scenario, the soap film expends as little energy as possible to maintain itself. The area of the film for a segment varies with the total length between the pegs. Nature wants to minimize its film area, so in doing so it also finds the minimum length solution for us. (The end of the video showed a local minimum, which by adding some energy, yielded the global minimum. Clever!)

The ultimate supercomputer

No calculations, no algorithms, no processing. Intrinsically, nature behaves like an infinitely-scaled parallel processor, evaluating all possible paths simultaneously in an attempt to find the lowest possible energy state that maintains itself. In my mind, this behavior is analogous to quantum computers where all states are evaluated simultaneously (for the purists, greatly simplified).

Via this exercise in the physical world, nature solved a mathematical problem by finding the shortest distance between a set of points. Can nature also similarly identify the shortest loop through a set of points for our friend, the traveling salesman?

Comparing the problems

The Traveling Salesman problem has the following properties (where I equate the edge cost to the distance between cities):

  1. Requirement to create a loop (in contrast to Steiner Trees, which have no such requirement), and therefore a traversal order is implied.
  2. Each city has precisely two edges connected to it (where Steiner Trees have at least one).
  3. All available paths and their associated distances between cities are fixed (whereas the paths between nodes in Steiner Trees are undefined from the start, and the paths with associated distances are solved for).
  4. The number of cities cannot be changed (whereas Steiner Trees can increase the number of nodes by adding Steiner Points if it reduces the total distance).

As I see it, the primary difference is that Steiner Trees solve for the minimum total distance to connect all nodes, versus the Traveling Salesman problem must solve for the minimum loop distance by identifying a traversal order.

Another way to contrast is that Steiner Trees are unordered because a traversal order isn’t part of the solution, and the Traveling Salesmen problem is ordered because you must find the right loop through all nodes.


Is there a natural phenomena, similar to the soap film exercise that would provide a solution to a given Traveling Salesmen problem?

I’ve been pondering this for the past few days, and I think the problem’s complexity lies in the ordering. Unlike Steiner Trees where nature “solves” for minimum distance by finding the lowest energy at an instant, here it would need to solve for the minimum distance over every ordered permutation of nodes. That implies iterations and time dependency, which reminds us of why this is NP-hard.

If we find a natural phenomena where things are traversed in a specific order which happens to be the optimal distance, we have a chance. At the moment, nothing comes to mind.