Preprint D129/2016
Solving the traveling salesman and establishing P = NP
Marc Mad
Keywords: Traveling Salesman Problem | TSP | P=NP | P vs NP

Solving the TSP:
-----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: