Approximative graph pyramid solution of the E-TSP

作     者：Haxhimusa, Yll Kropatsch, Walter G. Pizlo, Zygmunt Ion, Adrian 

作者机构：Purdue Univ Dept Psychol Sci Coll Liberal Arts Lafayette IN 47907 USA Vienna Univ Technol Fac Informat Inst Comp Aided Automat Pattern Recognit & Image Vienna Austria 

出 版 物：《IMAGE AND VISION COMPUTING》 (Image Vision Comput)

年 卷 期：2009年第27卷第7期

页      面：887-896页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 0702[理学-物理学] 

基　　金：Direct For Computer & Info Scie & Enginr Div Of Information & Intelligent Systems Funding Source: National Science Foundation 

主　　题：Hierarchical representation Graph pyramids Human problem solving Traveling salesman problem Boruvka's minimum spanning tree 

摘      要：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. (C) 2008 Elsevier B.V. All rights reserved.