The algorithm presented here solves the TSP to optimality. Basically it finds the possibilities associated to every edge. Precisely the algorithm takes the index of a given edge (from an ordered list of edges) and increments its cost into all the appropriate 2*(n-2)! possibilities which are associated to the edge. However this is only for the symmetric definition of the TSP. That is the definition where the two opposite edges between two verteces are joined to mean only one edge with one cost.

A quite simple naive solution to the TSP is to compute the costs of all possibilities and take the one with the smallest cost. Consider one operation is taken to add any two numbers. Then for one possibility it will take n operations to compute its cost (since it has n edges). Since there are (n-1)! possibilities, the total number of operations to compute all of them is n*(n-1)! = n! .

Now a converse question may be: given an arbitrary edge, what are the possibilities of all the (n-1)! possibilities to which the edge contributes in their costs? It is clear that there is no edge that contributes in the costs of all (n-1)! possibilities. Actually, any one edge contributes to the costs of 2*(n-2)! possibilities.

The converse-approach algorithm finds the answer to the converse question. It is a function that takes as input an arbitrary edge and then finds which 2*(n-2)! possibilities does the edge contributes in building up their costs. Basically the algorithm takes the index of a given edge (from an ordered list of edges) and increments its cost into all the appropriate 2*(n-2)! possibilities which are associated to it.

Consider one operation is taken to add any two numbers. Then for one edge it will take 2*(n-2)! operations to increment its cost into the appropriate 2*(n-2)! associated possibilities. Since there are (n-1)*n/2 edges, the total number of operations to compute all of them is 2*(n-2)! * (n-1)*n/2 = n! .

The algorithm is not yet fully developed. In its full development it is a complete mathematical equation (or function) having as input:

- the index of an arbitrary edge of all the (n-1)*n/2 edges

- the index of the 'possibility of interest' of all the 2*(n-2)! associated possibilities

The '

The output of the mathematical function is the index of the appropriate possibility of all (n-1)! overall possibilities. With this output, the cost of the inputted edge is incremented to the cost of the outputted possibility, outside the function.

Download the source code for the algorithm