矩阵式旅行商问题的最优解  

The Optimal Solution to the Matrix Type of TSP

作　　者：郝志峰[1] 刘海[2] 林智勇[3] 

机构地区：[1]华南理工大学理学院应用数学系 [2]香港城市大学计算机科学系 [3]广东职业技术师范学院计算机科学系,广东广州510633

出　　处：《计算机应用研究》2003年第4期18-19,81,共3页Application Research of Computers

基　　金：国家自然科学基金(19901009);教育部"优秀青年教师"资助计划;广东省自然科学基金(970472;000463);广东省教育厅"千百十工程"优秀人才培养基金;中国科学院软件研究所计算机科学开放实验室资助项目(SYSKF0105)

摘　　要：针对一类特殊的平面TSP问题,其中所有城市的位置都规整地排成矩阵,每一行(每一列)相邻城市的距离相等;对行距等于列距以及行距不等于列距的其中一种情况,都分别给出了最优算法和证明,而对行距不等于列距的另一种情况也给出了三个算法以及它们的比较。This paper aim at a special type of planner TSP, the arrangement of all cities in this type like a Matrix,the distance between two cities in each row(or each column) is equal.We obtain the optimal algorithms and their prove for the following two conditions:row spacing equaling col width and one case of row spacing not equaling col width.For the other case of row spacing not equaling col width,we provide three algorithms and their comparison.

关 键 词：旅行商问题 矩阵式旅行商问题 算法 

分 类 号：O157[理学—数学] TP30[理学—基础数学]