Solving the Travelling Salesman Problem using state-space search

There are numerous approaches to solving the NP complete Travelling Salesman problem (TSP).
There are also different versions of TSP.  
The one that we are concerned with here seeks to find a minimum spanning cycle in a weighted, 
undirected graph.

Of course, a brute force approach that finds all spanning cycles and selects the cheapest from them 
will work but, for large graphs this approach will require too much compute time.  
Such an approach might employ a simple state-space search such as depth-first search.
A complete graph with only 21 nodes has 20 factorial spanning cycles (divide by 2 to account for the 
fact that abc and cba are the same cycle).  If a computer could find each one in one billionth of a 
second it would take 38.57 years to find them all.  A complete graph with 31 nodes would require
 4,205,556,503,871,623 years - that's 4,205 trillion years.

A "more-informed" state-space search would significantly reduce execution time.

Here is an approach that works substantially better that incorporates A* search.  Several heuristics 
to use with the A* search are given below.  The first uses an all-to-one shortest path algorithm 
(e.g. Dijkstra's algorithm).

First, use an algorithm such as Dijkstra's to find shortest paths from all nodes of the graph to the 
start node of the search tree and store the lengths of these paths in an array named SP.  
I.e., SP[9] would contain the length of the shortest path from node 9 to the node designated to be the 
start node of the search tree.

As stated above, the starting node of the search tree is one of the nodes in the graph.  
Selecting the node of least degree may work best to reduce the average branching factor.  
Although it might appear that the states in this state-space search are nodes of the graph the actual 
states are paths.
So the root node is actually the zero-length path consisting only of the root node.

The goal state is the spanning cycle of least cost.

The evaluation function for this search will be f(n) = g(n) + h(n).

g(n) is the length of the current path from the start state, s, to state n.
State n is a path that begins at node s and ends at node n.

h(n) is a heuristic function that estimates the length of the remainder of the minimal spanning cycle 
(if it exists) that extends the current state (a path from s to n) to the final state, the minimal 
spanning cycle.  

In order to successfully employ A* search, h(n) must be an underestimate of the actual length of the 
remainder of the minimal spanning cycle (if it exists) that extends the current state (a path from
 s to n) to the final state, the minimal spanning cycle.
Therefore, f(n) is an underestimate of a minimal spanning cycle from s to s that contains state n, 
a path from s to node n.

If one lets h(n)=0 then A* search becomes the simpler uniform cost search and is guaranteed to 
terminate with a solution to the TSP if one exists.  The advantage to using h(n)=0 rather than a 
better estimate for the distance from n to s that might sometimes overestimate the distance is that 
using h(n)=0 ensures that when a node, n, is expanded (i.e. when we generate the children of that 
node) we have found the shortest path from s to n.
This means that when we find a spanning cycle we have found the minimum spanning cycle.

Fortunately some functions that are better-estimators (more informed) than h(n)=0 also have this 
property.  In fact any estimator (heuristic) function that underestimates the distance will find a 
"best" solution when it finds its first solution.
  
Let h(n) = SP[n] since SP[n] is such a function.  Also, SP[n] has another special property that
makes it even more suitable.
Since SP[m] - SP[n] <= ShortestPath from m to n then the monotonicity or consistency condition 
is met and we know that using h(n)=SP[n] guarantees that no more states will be examined
than by any less-informed heuristic function (such as h(n) = 0).

================================================================================

Improving performance
Walks of Lengths 1 to n Heuristic

The better the heuristic (estimator) function, h, the faster the search will be provided h(n) 
underestimates the length of a path from n to s.  One problem with function SP is that it does
not take into account the number of nodes that must be traversed to reach s.

For example, if a graph, G, has 10 nodes and state n represents a path of 3 edges (4 nodes) from 
s to n then we need to estimate the length of a path of 7 edges (8 nodes) from n to s; not simply 
the shortest path from n to s, SP[n].

Let SP1[n, i] be the length of the shortest path of i edges from n to s.  If we could efficiently
compute SP1[n, i] then we could very nearly predict the correct path to take at each state and we
would have an order E (number of edges) algorithm.  Since it is not likely that we will be able to do this 
we shall define an underestimator of SP1, named SP2.

SP2[n, i] is the length of the shortest walk of length i from n to s where we allow repetition of 
nodes.  For example, path 5-2-3-2-1 would be allowed in the computation of SP[5, 4].  Clearly this
could not be part of the solution to a TSP but it serves to give the desired underestimate and is 
no less than SP[5].

SP2 can be computed using a dynamic programming approach in order N cubed.  Using SP2 in place of
SP for h should yield a much faster algorithm.

================================================================================

More performance improvement
Minimum Edgeweight heuristic

SP2 is not a good estimator since it allows traversing the same edge(s) more than once and, 
typically, creates walks that bounce back and forth between two nodes to take advantage of
a single low edge-weight.  It is possible to create a heuristic that uses unique edges.

Let minEdge[n] = the weight of the smallest edge incident with node n.
Now Let S = Sum(minEdge[i]) for all nodes, i.

The total weight of any spanning cycle <= S.

We now create an estimator (heuristic) function, T.
Let n be a state (i.e., a path in G from the start node to node n) in our state space search.
T(n) = Sum(minEdge[i]) for all nodes, i, that are not in state n (the path from s to node n).
T(n) is an underestimate of the length of the remainder of the minimal spanning cycle 
(if it exists) that extends the current state (a path from s to n) to the final state, the minimal 
spanning cycle.

We must be able to compute T(n) efficiently when we generate a new state (child) of a node.
Let cn be a child of node n.  Then T(cn) = T(n) - minEdge(n).

============================================================================

If one wants to use the shortest path (sp) heuristic then here is a substantial improvement to it.
 
s is the start node (and final node)
When at node n, which represent a path p = (s, n1, n2, ..., n) then, rather than making the heuristic 
h(n)=sp(n, s) instead find the node m (not a node on the path, p, above) which maximizes 
sp(n, m) + sp(m, s).  This is an underestimate of the length of any path from n to s that contains 
every node not in p.
======================================================================

An even better estimator
Dual Minimum Edgeweight heuristic

Let P = (v1, v2, v3, ...vn, v1) be a solution to the TSP for a Graph, G, with N nodes and E edges.
P is a sequence of edges {(v1, v2), (v2, v3), ..., (vn, v1)}

Every node of G appears in exactly 2 edges of P.
If we loop through all the nodes of G and compute the sum of all the edges in P the the final sum, S, 
will be twice the weight of the minimum spanning cycle since every edge will be counted twice.

We will use this fact to create a heuristic for the TSP.

Loop through all the nodes in G and sum the 2 least weight edges incident to each node.  Call the set 
of these edges E' and the sum of their weights, S'.
NOTE: E' may represent a disconnected graph.
Many of the edges of E' might not be in P but, clearly, S'/2 <= S/2 = weight(P).  Thus, S'/2 is an
underestimate of the weight of P, the solution to the TSP for G.
h(n) will be defined using this idea.
First, h(s) = weight(E')/2 = S'/2 where s is the node we select to start our search with.

When we generate the children of s we will recompute h for each child as follows.
Let c1 be a child of s.  When we generate c1 we create a new state, the path (s, c1).  In so doing
we consume two of the edges of E'; namely the edge leaving s and the edge entering c1.  (Actually, the 
leaving and entering are not important; only the fact that we have consumed one edge of s and one
of c1).  Now we reestimate the balance of the spanning cycle; the weight of the shortest path of length 
N-1 from c to s.  This will become h(c1).  
We do this by removing 2 edges, w and x, from E' and recomputing the weight of E'.

If weight(s, c1) = the least of a's 2 minimum edges then remove that edge from E' else remove the
larger of a's 2 edges from E'.  Repeating this for c1,
If weight(s, c1) = the least of c1's 2 minimum edges then remove that edge from E' else remove the
larger of c1's 2 edges from E'.
NOTE: There is no guarantee that (s, c1) is actually one of a's or c1's edges but, in that case, the 
estimate gets even better.
Now h(c1) = (S'-weight(w) - weight(x))/2.