| 关于"TSP"的算法研究 |
| |
| 引用本文： | 郑自途.关于"TSP"的算法研究[J].天津理工大学学报,2002,18(3):50-54. |
| |
| 作者姓名： | 郑自途 |
| |
| 作者单位： | 天津理工学院,天津,300191 |
| |
| 摘 要： | n阶完全图 (边赋权 )的矩阵每行每列最小元素对应着一个次数为n的置换 ,若从这些最小元素组成的所有圈中每圈至少取出一个元素并令其为∞ ,那么仅包含这些元素的子矩阵可以经过初等变换将这些元素置于主对角线上形成一个新矩阵 ,其每行每列最小元素又对应一个新的置换 .在满足一定条件时 ,两个置换合成能够得到一个次数为n的循环置换 .运用这种方法 ,可使求TSP解的算法得到简化
|
| 关 键 词： | TSP 最小元素 组合 置换 合成 算法 |
| 文章编号： | 1004-2261(2002)03-050-05 |
| 修稿时间： | 2002年6月17日 |
An algorithm for the traveling salesman problem |
| |
| ZHENG Zi,tu.An algorithm for the traveling salesman problem[J].Journal of Tianjin University of Technology,2002,18(3):50-54. |
| |
| Authors: | ZHENG Zi tu |
| |
| Abstract: | In the matrix for a complete graph with n nodes,the mininum items in each row and column correspond to the permutation which time is n.Taking out at least one edge from each cycle corresponding to the all mininum items in matrix,then implement basic transformation to the sub matrix merely containing these items, forming the sub matrix which items are all defined infinite at diagonal.The minimum items in the rows and columns corresponding to the a new permutation of the new sub matrix.By compounding the two permutation obtained a cyclic permutation which time is n on definite condition.With this method,the simplified algorithm to Traveling Salesman Problem(TSP)by which the solutions can be obtained |
| |
| Keywords: | TSP mininum items combinations permutations compounding algorithm |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
