Graph Pyramid Solution of Travelling Salesman Problem
Introduction
Traveling salesperson problem (TSP) is a combinatorial optimization task of finding the shortest tour of n cities given the intercity costs. When the costs between cities are Euclidean distances, the problem is called Euclidean TSP (ETSP). TSP as well as ETSP belongs to the class of difficult optimization problems called NPhard and NPcomplete if posed as a decision problem [1]. The straightforward approach by using brute force search would be using all possible permutations for finding the shortest tour. It is impractical for large n since the number of permutations is (n1)!/2.
Because of the computational intractability of TSP, researchers concentrated their efforts on finding approximating algorithms. Good approximating algorithms can produce solutions that are only a few percent longer than an optimal solution and the time of solving the problem is a loworder polynomial function of the number of cities [2, 3, 4]. The last few percent to reach optimality are computationally the most expensive to achieve.
It is by now well established that humans produce closetooptimal solutions to ETSP problems in time that is (on average) proportional to the number of cities [5, 6, 7]. This level of performance can not be reproduced by any of the standard approximating algorithms. Some approximating algorithms produce smaller errors but the time complexity is substantially higher than linear, other algorithms are relatively fast but produce substantially higher errors. It is therefore of interest to identify the computational mechanism used by the human brain.
A simple way to present ETSP to a subject is to show n cities as points on a computer screen and ask the subject to produce a tour by clicking on the points. In the Figure 1 (a), an ETSP example of 10 cities is shown; in (b) the solution given by a human, and in (c) by the optimal solver. The tours produced by the subjects are, on average, only a few percent longer than the shortest tours (in the Figure 1 (b) the cross depicts the starting position and the arrow the orientation used by the subject). The solution time is a linear function of the number of cities [5, 6]. Two attempts to emulate human performance by a computational model were undertaken in [5, 6]. In [5], authors attempt to formulate a new approximating algorithm for ETSP motivated by the failure to identify an existing algorithm that could provide a good fit to the subjects' data. The main aspects of the models in [5, 7, 13] are its
 (multiresolution) pyramid architecture, and
 a coarse to fine process of successive tour approximations.
(a)  (b)  (c) 
10 city problem 
They showed that performance of this model (proportion of optimal solutions and average solution error) is statistically equivalent to human performance. Pyramid algorithms have been used extensively in both computer and human vision literature (e.g. [8]), but not in problem solving. The work of [5, 9] was the first attempt to use pyramid algorithms to solve the ETSP. One of the most attractive aspects of pyramid algorithms, which make them suitable for problems such as early vision or ETSP, is that they allow to solve (approximately) global optimization tasks without performing a global search. A similar pyramid algorithm for producing approximate ETSP solutions with emphasis on tradeoff between computational complexity (speed) and error in the solution (accuracy) and not on modeling human performance is formulated in [4, Chapter 5], and [10].↑
Approximating TSP by MST based Graph Pyramid
The Model
In the graph pyramid framework, the TSP input is represented by graphs where cities are represented by vertices, and the intercity neighborhoods by edges. Each vertex of the constructed input graph must have at least two edges for the TSP tour to exist. A level (k) of the graph pyramid consists of a graph G_{k}. Moreover the graph is attributed, G=(C,N,w_{v},w_{e}), where w_{e}:N→ R^{+} is a weighted function defined on edges N. The weights w_{e} are Euclidean distances in the ETSP and w_{v}:C → R^{+} is a weighted function defined on cities C. I.e. each vertex (city) has as a weight its position in the Cartesian coordinate system. Finally, the sequence G_{k}, 0 < k < h is called irregular graph pyramid.
Let G_{0}=(C,N,w_{v},w_{e}) be the input graph, with weights on edges given as distances in L_{2} space. The goal of the TSP is to find an nonempty ordered sequence of vertices and edges (v_{0},e_{1},v_{1},...,v_{k1},e_{k},v_{k},...,v_{0}) over all vertices of G_{0} such that all the edges and vertices are distinct, except the start and the end vertex v_{0}. This tour is called the optimal tour t_{opt} and the sum of edge weights in this tour is minimal, i.e.

We use local to global and global to local processes in the graph pyramid to find a good solution t^{*}, approximating the ETSP. The main idea is to use:
 bottomup processes to reduce the size of the input, and
 topdown refinement to find an (approximate) solution.
Approximating ETSP Solution by an MST Graph Pyramid
Input: Attributed graph G_{0}=(C,N,w_{v},w_{e}), and parameters r and s
 partition the input space by preserving approximate location:
create graph G_{0}  reduce number of cities bottomup until the graph contains s vertices:
build graph pyramid G_{k}, k=0,...,h, where s=G_{h}, and such that a father can have maximum of r childrens  find the optimal tour t_{a} for the graph G_{h}
 refine solution topdown until all vertices at the base level are processed:
refine t_{a} until level 0 is reached
The main idea in step (b) is that cities being close neighbors are put into a cluster and considered as a single city at reduced resolution. By doing this recursively one produces a pyramid representation of the problem. It is well known that the human visual system represent images on multiple level of scales and resolution [11,12]. In Figure 2. this step is illustrated for two levels of the pyramid.
(a) Bottomup reduction of resolution ⇑  (b) Initial tour t_{a} 
r=4 and s=3 
The main idea in step (d) is using the tour t_{a} found at level h of the graph pyramid as the first approximation of the TSP tour t^{*}. This tour is then refined using the pyramid structure already built. The refinement process starts by choosing (randomly) a vertex v in the tour t_{a}. Using the parentchild relationship, this vertex is expanded into the subgraph G'_{h1}. In this subgraph a path between vertices (children) is found that makes the overall path t'_{a} the shortest one (see Figure 3. a). Since the number of children from a father in G'_{h} cannot be larger than r, a complete search is a plausible approach to find the path with the smallest contribution in the overall length of the tour t'_{a}.
(a) Topdown refinement of t_{a} in t'_{a} ⇓  (b) The flow of processing ⇓ 
For more details consult reference [14].↑
References

Local Search in Combinatorial Optimization.
Johnson, D.S., McGeoch, L.A.
In: The Traveling Salesman Problem: A Case Study in Local Optimization. John Wiley and Sons (1997) 215310 
Graph Theory  An Algorithmic Approach.
Christofides, N.
Academic Press, New York, London, San Francisco (1975) 
The Traveling Salesman Problem.
Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B.
Wiley, New York (1985) 
The traveling salesman problem and its variations.
Gutin, G., Punnen, A.P.
Kluwer (2002) 
The travelling salesman problem: A hierarchical model.
Graham, S.M., Joshi, A., Pizlo, Z.
Memory and Cognition 28 (2000) 11911204 
A model of human performance on the traveling salesperson problem.
MacGregor, J.N., Ormerod, T.C., Chronicle, E.P.
Memory and Cognition 28 (2000) 11831190 
Pyramid algorithms as models of human cognition.
Pizlo, Z., Li, Z.
In: Proceedings of SPIEIS&T Electronic Imaging, Computational Imaging, SPIE (2003) 112 
A Pyramid Framework for Early Vision.
Jolion, J.M., Rosenfeld, A.
Kluwer (1994) 
Problem solving in human beings and computers.
Pizlo, Z., Joshi, A., Graham, S.M.
Technical Report CSD TR 94075, Department of Computer Sciences, Purdue University (1994) 
Polynomialtime approximation schemes for euclidean tsp and other geometric problems.
Arora, S.
Journal of the Association for Computing Machinery 45 (1998) 753782 
Scanning from coarse to fine spatial scales in the human visual system after the onset of a stimulus.
Watt, R.J.
Journal of the Optical Society of America 4 (1987) 20062021 
An exponential pyramid model of the timecourse of size processing.
Pizlo, Z., Rosenfeld, A., Epelboim, J.
Vision Research 35 (1995) 10891107 
Traveling Salesman Problem: a Foveating Pyramid Model.
Z. Pizlo, E. Stefanov, J. Saalweachter, Z. Li, Y. Haxhimusa and W. G. Kropatsch
Journal of Problem Solving, 1(1):83101, October 2006. Purdue University Press. []
Pyramid Solution of Travelling Salesman Problem (TSP)
This tool allows to solve the Traveling Salesman problem in a coarse to fine strategy.
References
Approximating TSP by MST based Graph Pyramid.
Y. Haxhimusa, W. G. Kropatsch, Z. Pizlo, A. Ion, and A. Lehrbaum.
In the International Graphbased Representation for Pattern Recognition Workshop, June 2007, Alicante, Spain. [] 
MST based Pyramid Model of TSP.
W. G. Kropatsch, Y. Haxhimusa, and Z. Pizlo.
In the 39th Annual Meeting of Mathematical Psychology , August 2006, Vancouver, Canada. [abstract] []
 Source code (April, 25 2007  Andreas Lehrbaum)
↑
MST Pyramid Solution of Travelling Salesman Problem  Demo
A demostration of the minimum spanning tree solution strategy in solving the travelling salesman problem.
Start the demostration or Start the application. In order for the program to start you need to install Java Web Start, if the application does not start please read me.
Usage notice
↑