摘要
旅行商问题是图论中一个典型的组合优化问题,它的问题描述与图论中最小生成树问题的描述具有很多相似之处,在一些情形下,可以用最小生成树形成的路径来获得旅行商问题的最短巡回路径。首先给出了最小生成树Prim算法,然后对其算法进行了改进,通过改进的Prim算法成功求解了旅行商问题。
Traveling salesman problem is a typical combinatorial optimization problem in graph theory , which has many similarities to the minimum cost spanning tree problem description of the problem .In some cases , the shortest tour path can be path formed by the minimum spanning tree to obtain the traveling salesman problem .This paper gives Prim algorithm , and the algorithm is improved , the improved Prim algorithm successfully solves the traveling salesman problem .
出处
《阴山学刊（自然科学版）》
2015年第1期8-10,19,共4页
Yinshan Academic Journal(Natural Science Edition)
关键词
最小生成树
旅行商问题
PRIM算法
minimum cost spanning tree
traveling salesman problem
Prim algorithm
