| TSP最短路径的必要条件初探 |
| |
| 引用本文： | 洪玉振.TSP最短路径的必要条件初探[J].河海大学学报(自然科学版),2006,34(6):717-720. |
| |
| 作者姓名： | 洪玉振 |
| |
| 作者单位： | 河海大学商学院,江苏,南京,210098 |
| |
| 摘 要： | 对于被访问城市数为n的不对称旅行商问题,构造了一个n行和n列的方阵,每一行上的n个元素为同一个被访问城市;每一列上的n个元素为n个互不相同的被访问城市.依次从该方阵的第一列到第k列上各取出一个城市,同一行上不存在两个被取出的城市,这样取出的城市序列就构成了一条长度为k的路径.主要讨论最短路径的性质:如果一条长度为(n-1)的最短路径能被产生,则该路径上的任一长度为k的路径都为最短路径,k=1,2,…,n-2.该性质为旅行商问题算法研究的基础.
|
| 关 键 词： | TSP 顶点 方阵 路径 最短路径 |
| 文章编号： | 1000-1980（2006）06-0717-04 |
| 收稿时间： | 2005-06-20 |
| 修稿时间： | 2005-06-20 |
Necessary condition for shortest path of TSP |
| |
| HONG Yu-zhen.Necessary condition for shortest path of TSP[J].Journal of Hohai University (Natural Sciences ),2006,34(6):717-720. |
| |
| Authors: | HONG Yu-zhen |
| |
| Institution: | Business School, Hohai University, Nanjing 210098, China |
| |
| Abstract: | |
| |
| Keywords: | traveling salesman vertices square matrix path shortest path |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《河海大学学报(自然科学版)》浏览原始摘要信息 |
| 点击此处可从《河海大学学报(自然科学版)》下载免费的PDF全文 |
|
