Let Nature Solves NP-Complete Problem

An Anonymous Coward writes: "Why not? Here's a start: Tourist Map Illuminates shortest route Light up a gas-tube graph with electricity to find the shortest path between two points. Can they extend this to multiple vertices to instantly solve the NP-Complete traveling salesman problem?"

Comments

Question

[Lomby]

From my physics classes, I recall that electricity follows the line of least resistance.

Now, this means at every crossroad, the electron flow will select the road with the least electric resistance.

This leads to a kind of greedy algorithm, that possibly leads to a good approximation of the shortest path, but still an approximation.

Or does the current flow path oscillate to find the absolute resistance minimum, so it does not get stuck in a relative minimum?

Or do I miss something?

Knotted String and Dijkstra

[alacqua]

Here's two other amazing solutions. Knotted string and Dijkstra's algorithm.

There are several methods that can be used to solve this problem. One way is to make a model of the map by knotting together pieces of string whose lengths are proportional to the lengths of the roads. To find the shortest path, take hold of the knots corresponding to A and L - and pull tight!
-Introduction to Graph Theory, Robin J. Wilson

How can we find the shortest route from one location to another?... Dijkstra's Algorithm (Dijkstra [1959] and Whiting-Hillier [1960]) solves this problem quickly,...
-Introduction to Graph Theory, Douglas B. West

Check any book on graph theory or on algorithms for the details of Dijkstra's algorithm.

The setup with the tourist map is kind of cool but hardly a breakthrough for math or computer science.