Name
Abstract | ||
|---|---|---|
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 Boruvka'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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.imavis.2008.06.016 | Image Vision Comput. |
Keywords | Field | DocType |
euclidean tsp problem,graph pyramid solution strategy,near-optimal solution,tsp problem sequentially,computationally hard problem,smaller number,approximate solution,optimal solution,hierarchical representation,borůvka’s minimum spanning tree,approximative graph pyramid solution,large number,traveling salesman problem,tour solution,graph pyramids,human problem solving,pattern recognition,data structure,top down,bottom up,minimum spanning tree | Graph,Data structure,Mathematical optimization,Travelling salesman problem,Pyramid,Euclidean geometry,Spatial structure,Approximate solution,Mathematics,Minimum spanning tree | Journal |
Volume | Issue | ISSN |
27 | 7 | Image and Vision Computing |
Citations | PageRank | References |
5 | 0.62 | 21 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yll Haxhimusa | 1 | 233 | 20.26 |
| Walter G. Kropatsch | 2 | 896 | 152.91 |
| Zygmunt Pizlo | 3 | 158 | 22.63 |
| Adrian Ion | 4 | 222 | 21.11 |