节点文献

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

The Optimal Solution to the Matrix Type of TSP

  • 推荐 CAJ下载
  • PDF下载
  • 不支持迅雷等下载工具，请取消加速工具后下载。

【作者】 郝志峰； 刘海； 林智勇；

【Author】 HAO Zhifeng1,2,LIU Hai3,LIN Zhiyong4(1.Dept.of Applied Mathematics,College of Science,South China University of Technology,Guangzhou Guangdong 510640,China;2.Open Lab.of Computer Science, Institute of Software,Chinese Academic of Science,Beijing 100080,China;3.Deptof Computer Science,City University of Hongkong,Hongkong,China;4Deptof Computer Science,Guangdong Polytechnic Normal University,Guangzhou Guangdong 510633,China)

【机构】 华南理工大学理学院应用数学系； 香港城市大学计算机科学系； 广东职业技术师范学院计算机科学系 广东广州510640； 中国科学院软件研究所计算机科学开放实验室； 北京100080； 香港； 广东广州510633；

【摘要】 针对一类特殊的平面TSP问题,其中所有城市的位置都规整地排成矩阵,每一行(每一列)相邻城市的距离相等;对行距等于列距以及行距不等于列距的其中一种情况,都分别给出了最优算法和证明,而对行距不等于列距的另一种情况也给出了三个算法以及它们的比较。

【Abstract】 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.

【关键词】 旅行商问题； 矩阵式旅行商问题； 算法；
【Key words】 TSP； Matrix Type； Algorithms；
【基金】 国家自然科学基金(19901009);教育部"优秀青年教师"资助计划;广东省自然科学基金(970472,000463);广东省教育厅"千百十工程"优秀人才培养基金;中国科学院软件研究所计算机科学开放实验室资助项目(SYSKF0105)
  • 【文献出处】 计算机应用研究 ,Application Research of Computers , 编辑部邮箱 ,2003年04期
  • 【分类号】O224
  • 【被引频次】4
  • 【下载频次】264
知网节下载
节点文献中： 

本文链接的文献网络图示:

本文的引文网络
二级参考文献(0)
参考文献(0)
共引文献(0)
节点文献
同被引文献(0)
引证文献(0)
二级引证文献(0)