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?

  • 1
    $\begingroup$ It might be helpful if you could link to some of the papers you are referring to. $\endgroup$ – mindcrime Feb 26 '17 at 9:29
  • $\begingroup$ 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? $\endgroup$ – Guido Jorg Feb 26 '17 at 18:07

To the best of my knowledge there isn't any difference between the algorithmic methods and the NN methods. Those that can solve in polynomial time do not give a precise solution. Those that do give a precise solution do not solve in polynomial time. Of those that give a precise solution the fastest takes 2^Nth, but it blows up in terms of memory. The fastest good algorithm I believe is Concorde.

The efficient algorithms solve in polynomial time, don't blow up in terms of memory, and give a solution close to perfect, say, within 2-3%. Again, to the best of my knowledge, no NN has beat the best algorithmic solutions, but there are suggestions that some NN solution could be faster.


There is some recent work addressing this issue, to learn the conditional probability of an output sequence with elements that are discrete tokens corresponding to positions in an input sequence. see Pointer Networks


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.