关于“TSP”的算法研究

An algorithm for the traveling salesman problem

n阶完全图 (边赋权 )的矩阵每行每列最小元素对应着一个次数为n的置换 ,若从这些最小元素组成的所有圈中每圈至少取出一个元素并令其为∞ ,那么仅包含这些元素的子矩阵可以经过初等变换将这些元素置于主对角线上形成一个新矩阵 ,其每行每列最小元素又对应一个新的置换 .在满足一定条件时 ,两个置换合成能够得到一个次数为n的循环置换 .运用这种方法 。

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