TSP问题是一个典型的NP-难问题,具有重要的理论价值和实际应用价值,多年来一直是学者们研究的热点。由于大多数学者认为NP-难问题不存在多项式时间内的完全算法,所以设计它的近似算法就具有相当重要的意义,而TSP问题也成为了衡量近似算法效率的主要标准。作者充分研究了目前的各种算法,分析了贪心算法和传统树算法以及其它近似算法的优劣,从以下方面做了主要工作:首先,设计了求解对称旅行商问题的树算法,该算法以构造完全图的最小生成树开始,保证生成树中较短的链作为TSP环游的组成部分,然后求出剩余点组成的完全图的最小完美匹配,把匹配边加入链中得到一条TSP环游。其次,设计了求解非对称旅行商问题的树算法,该算法先构造原图的一个最小有向生成图,把它转换成运输问题进行求解,再把解对应的弧加到有向图上,然后搜索出一条TSP环游。最后,基于对旅行商问题的思考,设计了两种近似算法对多旅行商问题进行求解,指出了尚需进一步思考的问题。