基于启发式算法的tsp问题开题报告

全文总字数：6336字

1. 研究目的与意义

旅行商问题(travelingsalesmanproblem，tsp)是一个经典的组合优化问题。

经典的tsp可以描述为：一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要经过所有城市后，回到出发地。

应如何选择行进路线，以使总的行程最短。

2. 国内外研究现状分析

tsp的历史很久,最早的描述是1759年欧拉研究的骑士周游问题,即对于国际象棋棋盘中的64个方格,走访64个方格一次且仅一次,并且最终返回到起始点.tsp由美国rand公司于1948年引入,该公司的声誉以及线形规划这一新方法的出现使得tsp成为一个知名且流行的问题.同样的问题,在中国还有另一个描述方法：一个邮递员从邮局出发,到所辖街道投邮件,最后返回邮局,如果他必须走遍所辖的每条街道至少一次,那么他应该如何选择投递路线,使所走的路程最短?这个描述之所以称为中国邮递员问题（chinese postman problem cpp）因为是我国学者管梅古教授于1962年提出的这个问题并且给出了一个解法.计算机科学的两大基础目标，就是发现可证明其执行效率良好且可得最佳解或次佳解的算法。

而启发式算法则试图一次提供一个或全部目标。

例如它常能发现很不错的解，但也没办法证明它不会得到较坏的解；它通常可在合理时间解出答案，但也没办法知道它是否每次都可以这样的速度求解。

3. 研究的基本内容与计划

本文主要通过对启发式算法当中的遗传算法、蚁群算法、模拟退火算法的研究、实现、比较，给出能较好地平衡算法执行次数和运算结果最优化的实现方法。

模拟退火算法的思想借鉴于固体的退火原理，当固体的温度很高的时候，内能比较大，固体的内部粒子处于快速无序运动，当温度慢慢降低的过程中，固体的内能减小，粒子的慢慢趋于有序，最终，当固体处于常温时，内能达到最小，此时，粒子最为稳定。

模拟退火算法便是基于这样的原理设计而成。

4. 研究创新点

利用matlab编辑tsp问题所涉及的数学模型。

重点分析和讨论遗传算法、蚁群算法模拟退火算法。

利用mat1ab语言完成对求解tsp的最优算法编程，通过三个实例测试各种算法的优缺点，进而给出了在算法执行次数和运算结果最优化之间有良好平衡的实现算法。