Approximative graph pyramid solution of the E-TSP

• Published in: Image and vision computing 2009-06, Vol.27 (7), p.887-896
• Main Authors: Haxhimusa, Yll, Kropatsch, Walter G., Pizlo, Zygmunt, Ion, Adrian
• Format: Article
• Language: English
• Subjects: Borůvka’s minimum spanning tree; Graph pyramids; Hierarchical representation; Human problem solving; Traveling salesman problem
• ISSN: 0262-8856; 1872-8138
• DOI: 10.1016/j.imavis.2008.06.016

The traveling salesman problem (TSP) is difficult to solve for input instances with large number of cities. Instead of finding the solution for an input with a large number of cities, the problem is transformed into a simpler form containing smaller number of cities, which is then solved optimally. Graph pyramid solution strategies, using Borůvka’s minimum spanning tree step, convert, in a bottom-up processing, a 2D Euclidean TSP problem with a large number of cities into successively smaller problems (graphs) with similar layout and solution, until the number of cities is small enough to seek the optimal solution. Expanding this tour solution in a top-down manner, to the lower levels of the pyramid, leads to an approximate solution. The new model has an adaptive spatial structure and it simulates visual acuity and visual attention. The model solves the TSP problem sequentially, by moving attention from city to city, and the quality of the solutions is similar to the solutions produced by humans. The graph pyramid data structures and processing strategies provide good methods for finding near-optimal solutions for computationally hard problems. Isolating processing used by humans to solve computationally hard problems is of general importance to psychology community and might lead to advances in pattern recognition.