数学建模题目3

《数学模型及数学软件》上机报告专业：姓名：学号：地点及机位编号：日期时间：2016年5月20日一、上机训练题目或内容旅行商问题(TSP,TravelingSalesmanProblem)：有N个城市，要求从其中某个问题出发，唯一遍历所有城市，再回到出发的城市，求最短的路线。使用模拟退火算法计算第1个城市到第𝑛城市之间的最短距离，各个城市坐标处理后如下表1：表1各个城市的坐标编号123456789100.66830.61950.40.24390.17070.22930.51710.87320.68780.84880.25360.26340.44390.14630.22930.7610.94140.65360.52190.3609二、数学模型或求解分析或算法描述旅行商问题属于所谓的完全问题，精确的解决TSP只能通过穷举所有的路径组合，其时间复杂度是。使用模拟退火算法可以比较快的求出TSP的一条近似最优路径。（使用遗传算法也是可以的，我将在下一篇文章中介绍）模拟退火解决TSP的思路：1.产生一条新的遍历路1径，计算路径1的长度12.若1，则接受1为新的路径，否则以模拟退火的那个概率接受1，然后降温3.重复步骤1，2直到满足退出条件三、结果或结论通过以上计算我们得到的结果如图1。图1最短路径的轨迹