非完全图TSP问题研究

编号 zgly0001506390

文献类型 期刊论文

文献题名 非完全图TSP问题研究

作者 张家善 

作者单位 重庆工程职业技术学院财经与贸易学院 

母体文献 绿色科技 

年卷期 2016年05期

年份 2016 

分类号 F590 

关键词 TSP问题  非完全图  大M法  仿真 

文摘内容 指出了TSP问题是一种具有代表性的组合优化问题,在现实生活中有着广泛的应用。不同于完全图,非完全图TSP问题中存在着某些节点之间没有路径直接相连,使得处于该节点位置时,其路径选择受到一定限制。受运筹学中大M法思想的启发,提出了通过引入一个非常大的正数(即大M)来表示此类节点间的距离,从而将非完全图TSP问题转化成完全图TSP问题,降低了问题求解的难度,并且验证了该方法的有效性。