模拟退火算法解决TSP问题15页.doc

智能优化方法课题报告 专业班级： 电子信息科学与技术12-3班 课题名称： 模拟退火算法解决TSP问题 指导教师： 姚 睿 学生姓名： 蒋文斌 学 号： 08123453 （课题设计时间：2015年3月28日2015年 4月13日）中国矿业大学计算机学院一、问题描述旅行商问题（Traveling monituihuolesman Problem，简称TSP）又名货郎担问题，是威廉哈密尔顿爵士和英国数学家克克曼(T.P.Kirkman)于19世纪初提出的一个数学问题，也是著名的组合优化问题。问题是这样描述的：一名商人要到若干城市去推销商品，已知城市个数和各城市间的路程（或旅费），要求找到一条从城市1出发，经过所有城市且每个城市只能访问一次，最后回到城市1的路线，使总的路程（或旅费）最小。TSP刚提出时，不少人认为这个问题很简单。后来人们才逐步意识到这个问题只是表述简单，