Preprint D130/2016
Solving the Traveling Salesman
Marc Mads
Keywords: TSP | Traveling Salesman Problem | P=NP | P vs NP | Problema do caheiro viajante

-----NP-hard version-----

*Get a matrix with the values;

*Sum the numbers of the matrix lines, generating one sum per line (The line has the distance from one city to others);

*Find the cities that have the 3 biggest sums and connect the cities with it other (E.g. A-B-C-A);

*The previous step will generate rows (E.g. AB; AC; BC);

*For every next city (that will be the biggest remaining sum, coming from the sums made in the second step):

     -for all the already generated rows:

          --sum the distance from the actual city to both of the row cities and subtract the row size (Generating a cost).

     -get the row with the smallest cost delete this row and add 2 new ones, from the actual city to the cities that were forming the deleted row.

-----NP-complete version-----

*Just do the steps from the NP-hard version and at the end sum the the path to see if it is smaller than the given number.


Anexos: