tsp问题(tsp)

摘要 大家好,我是小典,我来为大家解答以上问题。tsp问题,tsp很多人还不知道,现在让我们一起来看看吧!原发布者:tancydcTSP问题的求解摘要旅...

大家好,我是小典,我来为大家解答以上问题。tsp问题,tsp很多人还不知道,现在让我们一起来看看吧!

原发布者:tancydc

TSP问题的求解摘要旅行商问题(TravelingSalesmanProblem,TSP)代表一类组合优化问题,在计算机网络、公路交通分布等多种实际问题中都有重要意义。“旅行商问题”也常被称为“旅行推销员问题”,其实质为是指一名推销员要拜访多个地点时,如何找到在拜访每个地点一次后再回到起点的最短路径。针对该题求解经过30个城市旅行的最短路径问题,我们采用三种方法解决:法一:(模拟退火算法)借助Matlab程序采用模拟退火算法进行分析解决。即首先在固定温提条件下求出当前温度下的最短路径(局部最优解),然后改变温度后再次求局部最优后得到最终的最短路径(全局最优)法二:(遗传算法)借助Matlab程序采用遗传算法进行分析解决。即法三:(线性规划)找出该线性目标规划的目标函数及约束条件,借助Lingo软件求得该TSP问题的最短路径关键词:TSP问题模拟退火算法线性规划遗传算法一、问题重述1.1引言TSP是典型的组合优化问题,并且是一个NP-hard问题,TSP简单描述为:一名商人欲到n个不同的城市去推销商品,每2个城市i和j之间的距离为dij,如何选择一条路径使得商人每个城市走一遍后回到起点,所走的路径最短。用数学符号表示为:设n维向量s=(c1,c2,…,cn)表示一条路经,目标函数为:minn1C(c1,c2,…,cn)=d(ci,ci1)d(c1,cn)。i11.2问题提出题目给出30个城市的分布图象及具体坐标,要求出经过30

本文到此讲解完毕了,希望对大家有帮助。

郑重声明:本文版权归原作者所有,转载文章仅为传播更多信息之目的,如作者信息标记有误,请第一时候联系我们修改或删除,多谢。