TSP实验报告.doc
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2012 年 第一 学期研究生课程考核 (实验报告、研究报告) 考 核 科 目:算法分析与复杂性理论 学生所在学院:计算机科学与技术学院 学生所在学科:计算机应用技术 姓 名: 学 号: 学 生 类 别: 研究生 一、实验目的 1. 通过TSP算法的具体实现,加深对算法复杂分析的理解。 2. 通过TSP算法的具体实现,提高对NP完全问题的认识。 3. 通过TSP算法的具体实现,理解不确定性算法。 4. 通过TSP算法的具体实现,理解不确定性算法。 二、实验环境 实验平台:Visual C++ 6.0 编程语言:C++ 编程电脑配置: 三、实验内容描述 TSP(Travelling Salesman Problem)又称货郎担或巡回售货员问题,在运筹学、管理科学及工程实际中具有广泛的 用途。及工程实际中具有广泛的用途。TSP问题是组合优化中的著名难题,一直受到人们 的极大关注。由于其NP难题性质,至今尚未完全解决。此问题可以抽象描述为: 给出一个n个顶点网络(有向或无向),要求找出一个包含所有n个顶点的具有最小耗 费的环路。其中,任何一个包含所有n个顶点的环路被称作一个旅行。 对于旅行商问题,顶点表示旅行商所要旅行的城市(包括起点)。边上权值给出了在 两个城市旅行所需的路程。旅行表示当旅行商游览了所有城市后再回到出发点时所走的 路线。 四、实验原理 许多研究表明,应用蚁群优化算法求解TSP问题优于模拟退火法、遗传算法、神经网 络算法、禁忌算法等多种优化方法。 为说明该算法,引人如下的标记: m表示蚁群中蚂蚁的数量;表示城市i和城市j之间的距离;表示t时刻位于城 市i的蚂蚁数,显然应满足,表示t时刻在ij连线上的信息数量。在算法的初 始时刻,将m只蚂蚁随机地放到n座城市上,此时各路径上的信息量相等,设。每只 蚂蚁根据路径上保留的信息量独立地选择下一个城市。在时刻t,蚂蚁k从城市i转移到城 市j 的概率为 其中,表示蚂蚁走下一步允许选择的所有城市,列表 纪录了当前蚂蚁k所走过的城市,当所有n个城市都加入到中时,蚂蚁k便完成 了一次循环,此时蚂蚁走所走过的路径便是问题的一个解。是一个启发式因子,表 示蚂蚁从城市i转移到城市j的期望程度,在蚂蚁算法中,通常取 城市ij之间距离的倒数。α和β分别表示路径上信息量和启发示因子的重要程度。 当所有蚂蚁完成一次循环后,各路径上的信息量要根据下面的公式进行调整: 其中表示路径上信息的蒸发系数;表示信息的保留系数;表示本次 循环路径ij上信息的增量。 表示第k只蚂蚁在本次循环中留在路径ij上的信息量,如果蚂蚁k没有经过路径,则 的值为零,表示为 其中,Q为常数,表示第k只蚂蚁在本次循环中所走过的路径的长度。 五、实验结果与实验分析 1. a280: 公布最优解:2579 2. eil51: 公布最优解:426 3. eil76: 公布的最优解:538 4. Eil101: 公布的最优解:629 5. kroA100: 公布的最优解:21282 通过分析运算结果,我看到编写的程序的执行结果和目前公布的最优值之间还存在着 较大的差距。分析原因,主要是因为没有解决好路径的交叉。 六、复杂度分析 假设:n是城市数量,m是蚂蚁数量,T是迭代次数 时间复杂度 time=n*(n-1)*m*T/2 m一般是n的2/3,那就让m=n*2/3 T一般是n的倍数,那就让T=k*n 于是 time=n*(n-1)*n*2/3*n*k/2 time=n*(n-1)*n*n*k/3 n->无穷大的时候,(此时k会远小于n) time就约等于 n^4 空间复杂度 space=3*nxn+n*m space=3*n*n+n*n*2/3 space=n*n*(3+2/3) n->无穷大的时候,space约等于n^2 六、实验体会 因为我是非计算机专业学生,所以编程能力很差,一开始对于这些问题根本无从下手 ,于是自己又重新学习了遍谭浩强的C编程书,后来又学习了一下VC++,但是对于VC++还 是不太熟悉,多亏了同学和我们组的组员的帮助,再加上借鉴已完成同学的程序,并且 这些同学给予了耐心的知道,使我的编程能力有了很大的提升,最后能把自己的平台勉 强完成很是感谢大家,在以后的学习中希望我们互帮互助共同进步,我会加倍努力,提 升自己。 ----------------------- TSP实验报告全文共7页,当前为第1页。 TSP实验报告全文共7页,当前为第2页。 TSP实验报告全文共7页,当前为第3页。 TSP实验报告全文共7页,当前为第4页。 TSP实验报告全文共7页,当前为第5页。 TSP实验报告全文共7页,当前为第6页。 TSP实验报告全文共7页,当前为第7页。
- 一个大写的文盲2023-12-27资源很实用,内容详细,值得借鉴的内容很多,感谢分享。
- mym121527102024-01-03资源内容总结地很全面,值得借鉴,对我来说很有用,解决了我的燃眉之急。
- 2201_752927982023-06-20感谢大佬分享的资源给了我灵感,果断支持!感谢分享~
- 粉丝: 168
- 资源: 3万+
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助