Using an electronic amoeba to quickly find an approximate solution to traveling salesman problem

The traveling salesman problem is about a salesman that has to start from a specific town and after visiting a number of towns only once, he/she has to return to the starting town. The real problem is to minimize the total length of the trip. It has been shown that this problem is NP-complete, which practically means that this is a very difficult problem to solve with a computer. However, Kenta Saito, Masashi Aono, and Seiya Kasai from Japan have shown that an electronic amoeba can give an approximate solution to this problem in linear time. Practically, this means that the new approach can transform a difficult problem to an easy one. The Japanese researchers reported their findings in a paper in scientific reports.


Δημοφιλείς αναρτήσεις από αυτό το ιστολόγιο

New and Notable Books

The Rolf Nevanlinna Prize

Everything is computable...