Computer Engineering and Applications ›› 2007, Vol. 43 ›› Issue (20): 22-24.

• 博士论坛 • Previous Articles     Next Articles

N-dimension connectivity map algorithm for TSP

DENG Juan1,CHEN Xin-meng2

  

  1. 1.Remote Sensing Information and Engineering School,Wuhan University,Wuhan 430079,China
    2.Computer School,Wuhan University,Wuhan 430072,China
  • Received:1900-01-01 Revised:1900-01-01 Online:2007-07-11 Published:2007-07-11
  • Contact: DENG Juan

旅行商问题的N维空间联通图算法与分析

邓 娟1,陈莘萌2   

  1. 1.武汉大学 遥感信息与工程学院,武汉 430079
    2.武汉大学 计算机学院,武汉 430072
  • 通讯作者: 邓 娟

Abstract: The Traveling Salesman Problem(TSP) is one of the most classical combinatorial optimization problems.Tremendous algorithms have been developed for it.It investigates the relationships among the n points in N-Dimension space(Rn) and propose N-Dimension Connectivity Map Algorithm(nDCM).This algorithm transforms n points (v1(x11,x12),v2(x21,x22),…,vn(xn1,xn2)) to (v1(x11,x12,…,x1n),v2(x21,x22,…,x2n),…,vn(xn1,xn2,…,xnn))in Rn and finds out the spatial relationship betweenand vj the other n-1 points(i=1,2,…,n),then builds a Rn-Connectivity Map(n×n) to solve the problem.It also demonstrates the results of nDCM algorithm and obtains some practical conclusions that may give guidance to further research for the TSP.

Key words: TSP, N-Dimension Space, Rn-Connectivity Map

摘要: 旅行商问题(Traveling Salesman Problem,TSP)是组合优化中典型的NP难问题之一。和现有算法的基于局部分析或通过反复迭代逐步达到满意解的方式不同,作者首次提出了在N维欧氏空间Rn中求解TSP问题的N维空间联通图算法(Rn-Connectivity Map Algorithm,nDCM Algorithm)。该算法根据R2中n点(v1(x11,x12),v2(x21,x22),…,vn(xn1,xn2))之间的距离关系(dist2ijn×n,将它们转换Rn中的点(v1(x11,x12,…,x1n),v2(x21,x22,…,x2n),…,vn(xn1,xn2,…,xnn))并通过对点vi与其余n-1个点的空间结构关系(i=1,2,…,n)进行分析,计算得到反映TSP整体空间分布的(dist2ijn×n,即Rn-联通图((Connectivity Map)n×n),从而以较高的效率求得TSP问题的满意解。首次从空间结构分析的角度给出了TSP问题的N维空间联通图算法以及由此得到的有实际指导意义的结论。

关键词: 旅行商问题, N维空间, Rn-联通图