作　　者： ;

机构地区： 华南理工大学工商管理学院

出　　处： 《华南理工大学学报（自然科学版）》 1994年第5期120-126,共7页

摘　　要： 本文对旅行售货员问题（ＴｒａｖｅｌｌｉｎｇＳａｌｅｓｍａｎＰｒｏｂｌｅｍ）提出了一种在对各城市之间路径进行排序的基础上，通过相应的路径关系数组变换，对有限条路径进行搜索，找出一个近似最优解的新算法。本文并给出了关于这个算法的时间复杂性估计，这个估计可以表达成为一个确定型的多项式。 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.

关 键 词： 游路问题 排序 算法复杂性 估计

领　　域： [理学] [理学]