改进的Prim算法在求解旅行商问题中的应用

作者：刘朝霞

来源：阴山学刊(自然科学版), 2015, 29(01): 8-19.

DOI：10.13388/j.cnki.ysajs.2015.01.002

• 最小生成树
• 旅行商问题
• Prim算法

旅行商问题是图论中一个典型的组合优化问题,它的问题描述与图论中最小生成树问题的描述具有很多相似之处,在一些情形下,可以用最小生成树形成的路径来获得旅行商问题的最短巡回路径。首先给出了最小生成树Prim算法,然后对其算法进行了改进,通过改进的Prim算法成功求解了旅行商问题。

• 出版日期2015
• 单位集宁师范学院