The Travelling Salesman Problem (TSP) may be defined as: given a list of cities and the costs to move between pairs of cities, find the shortest path that starts from any city, visits all the others and returns back to the city started with. The problem can be modelled as a graph problem in which the cities are the verteces of the graph and the costs between pairs of cities are the costs associated to the edges of the graph.
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.
For n cities (or verteces) there are a total of (n-1)! possible paths (or routes or possibilities). Recall that n! = n*(n-1)*...*2*1 and 0!=1. Also there are a total of (n-1)*n/2 pairs of cities (or edges). Each possibility is made up of n edges. The total cost of a possibility is equal to the sum of the individual costs of the n edges constituting it.
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! .
A question is: given an arbitrary possibility, what are the n edges of all the (n-1)*n/2 edges that add up to form its cost? The naive algorithm above is all about finding the answer to this question prior to computing the cost of that given possibility.
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! .
Previously there was no consideration of the time taken to answer each of the two questions. That is for the first question some time is taken to know the n edges associated to a given possibility. For the second question some time is taken to know the 2*(n-2)! possibilities associated to a given edge. Actually it is here that comes the reason why the converse-approach algorithm is slower than the naive algorithm.
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 edge' is relative to the list containing all the edges arranged in lexicographical order. That is when arranged in the list, the index is the position in the list. The same thing applies for the 'index of a possibility'.
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
The algorithm is extremely complicated!