旅行商问题实验报告.doc_第1页
旅行商问题实验报告.doc_第2页
旅行商问题实验报告.doc_第3页
旅行商问题实验报告.doc_第4页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

算法设计与分析实验报告 姓名： xx 班级： xxxx 学号： xxxxxx 实验名称：旅行商问题实验目的：1.分支限界法按广度优先策略搜索问题的解空间树，在搜索过程中，对待处理的结点根据限界函数估算目标函数的可能取值，从中选取使目标函数取得极值（极大或极小）的结点优先进行广度优先搜索，从而不断调整搜索方向，尽快找到问题的解。2.分支限界法适用于求解最优化问题。实验程序：输入：图G=（V, E） 输出：最短哈密顿回路1. 根据限界函数计算目标函数的下界down；采用贪心法得到上界up;2. 计算根节点的目标函数并加入待处理的结点表PT;3. 循环直到某个叶子结点的目标函数值在表PT中取得极小值3.1i=表PT中具有最小值的结点；3.2对结点i的每个孩子结点x执行下列操作； 3.2.1估算结点x的目标函数值lb； 3.2.2若（lb=up）,则将结点x加入表PT中，否则丢弃该结点；4.将叶子结点对应的最优值输出，回溯求得最优解的各个分量。实验分析：问题描述：TSP问题是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。271563134253984C= 3 1 5 8 3 6 7 91 6 4 25 7 4 38 9 2 3 采用贪心法求得近似解为：135421，其路径长度为1+2+3+7+3=16,这可以作为TSP问题的上界，把矩阵中每一行最小的两个元素相加再除以2，得到TSP问题的下界：(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14,于是得到目标函数的界14,16。一般情况下，假设当前已确定的路径为U=(r1, r2, , rk)，即路径上已确定了k个顶点，此时，该部分解的目标函数值的计算方法（限界函数）如下： 分支限界法求解图上机心得与体会：时间复杂性分析：分支限界法实际上属于蛮力穷举法，当然不能指望它有很好的最
人人文库> 全部分类> 应用文书 > 作业报告

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论