摘要
本文对旅行售货员问题（ＴｒａｖｅｌｌｉｎｇＳａｌｅｓｍａｎＰｒｏｂｌｅｍ）提出了一种在对各城市之间路径进行排序的基础上，通过相应的路径关系数组变换，对有限条路径进行搜索，找出一个近似最优解的新算法。本文并给出了关于这个算法的时间复杂性估计，这个估计可以表达成为一个确定型的多项式。
In this paper a novel algorithm principle for solving Travelling Salesman Problem is proposed. On the base of sorting the paths between each of the two cities and then through the array transformation of corresponding path relationship to search the limited paths, an approximate optimal solution is obtained. The estimation on the complexity of this algorithm is also deduced by the expression of a definite polynomial. The determination of search region will be reported in part(Ⅱ) of this paper.
出处
《华南理工大学学报（自然科学版）》
CSCD
1994年第5期120-126,共7页
Journal of South China University of Technology(Natural Science Edition)
关键词
游路问题
排序
算法复杂性
估计
s: travelling salesman problem
sorting
algorithms complexity
polynomial
