# Neural networks efficiently solve traveling salesmen problems?

I occasionally read papers that show neural networks solving traveling salesmen problems and multi traveling salesmen problems efficiently?

1) Is there any analysis of the meaning of efficiency of algorithms for networks that allowed to grow in size with the problem they are supposed to solve?

2) What are the earliest papers solving the TSP with NN this?

3) Is the meaning of efficiency used in these papers is the same as the usual one, in fact, and works only in this problem specifically?

These problems are NP hard. So I suspect I'm not sure what these papers mean by efficient.

The neural network postulated have a sufficiently vast number of interacting elements and in effect do the combinatorics strictly, for each special case. But if so, while this is fast and doesn't grow much with the size of the problem growing, is this really comparable to the normal meaning of PT as fast or efficient?

In these cases it seems the time efficiency is obtained by resource inefficiency: by making the network enormous and simulating all the possible worlds then maximizing. So, while time to compute doesn't grow much as the problem grows, the size of the physical computer grows enormously for larger problems; how fast it computes is then, it seems to me, not a good measure of efficiency of the algorithm in the common meaning of efficiency. In this case the resources themselves only grow as fast as the problem size, but what explodes is the number of connections that must be built. If we go from 1000 to 2000 neurons to solve a problem twice as large and requiring exponentially as much time to solve, the algorithms requiring only twice as many neurons to solve in PT seem efficient, but really, there is still an enormous increase in connections and coefficients that need be built for this to work.

Is my above reasoning incorrect?

• It might be helpful if you could link to some of the papers you are referring to. – mindcrime Feb 26 '17 at 9:29
• I suggest searching Traveling Salesman Neural Networks. There are many such papers ... and each states there are earlier ones. Part of the question is (2) What is the earliest such paper you know of?'' Searching I find one from 1988, dozens in the 1990s, more each year later. A lot of these papers today come from China, are in conference proceedings. Knuth (and others, e.g., in Information Science) write today that many special algorithms that solve a few NPc, NPh problems, but fail to solve others, often size interval dependent. I would like to understand: Is this is one of those things? – Guido Jorg Feb 26 '17 at 18:07