Slashdot Mirror

← Back to Stories (view on slashdot.org)

Let Nature Solves NP-Complete Problem

Posted by timothy on from the unconventional-approaches dept.

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?"

6 of 48 comments (clear)

  1. I prefer the slime mould version... by SIGFPE · · Score: 4, Informative

    ...here

    --
    -- SIGFPE
  2. Shortest-path problems are easy ... by Daniel+Dvorkin · · Score: 4, Informative

    ... for computers too. Any decent book on algorithms will give you several elegant, easy-to-implement, blazingly fast methods. The TSP, like all NP problems, is much different. Thinking about the gas-tube device (which is a really cool idea, I must say) there's no way to apply it to the TSP. Electricity just doesn't work that way.

    --
    The correlation between ignorance of statistics and using "correlation is not causation" as an argument is close to 1.
  3. Re:that's it? by vipw · · Score: 3, Funny

    i'd like to think technology can do more than make maps for tourists. :)

  4. Re:shortest path IS np-complete NOT by gkatsi · · Score: 5, Insightful

    First, shortest path algorithms do NOT consider every possible route. Instead, they consider the best extention to an already known shortest path (starting with the shortest path to the beginning, which is obviously 0). [roughly -- Dijsktra's algorithm is slightly more complicated, but not much].

    Second, if the number of operations increases polynomially, how does the problem get classified as NP complete? Never mind the fact that a lower bound alone is not enough to put a problem in a specific class, if the complexity is actually O(n^2), then the problem is clearly in P, not NP.

    Other than a nice hack, this article does not describe any important breakthrough.

  5. Re:Question by Fantanicity · · Score: 3, Informative

    The current doesn't oscillate or travel solely along the path of least resistance.
    Electrons do not select anything. The current flows from start to finish along all possible paths; but because the shortest path has the least resistance (there is less material to flow through) more electrons get through that path per unit time than other paths - hence the current is higher.
    In this case, all paths will glow, the shortest path will glow the most. With the right balance of voltage and material, the shortest path can glow significantly more than other paths.

  6. Knotted String and Dijkstra by alacqua · · Score: 4, Interesting
    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.

    --

    Move on. There's nothing to see here.