旅行商问题实验报告
4页
算法设计与分析实验报告 姓名： xx 班级： xxxx 学号： xxxxxx 实验名称：旅行商问题实验目的：1.分支限界法按广度优先策略搜索问题的解空间树，在搜索过程中，对待处理的结点根据限界函数估算目标函数的可能取值，从中选取使目标函数取得极值（极大或极小）的结点优先进行广度优先搜索，从而不断调整搜索方向，尽快找到问题的解。2.分支限界法适用于求解最优化问题。实验程序：输入：图G=（V, E） 输出：最短哈密顿回路1. 根据限界函数计算目标函数的下界down；采用贪心法得到上界up;2. 计算根节点的目标函数并加入待处理的结点表PT;3. 循环直到某个叶子结点的目标函数值在表PT中取得极小值3.1i=表PT中具有最小值的结点；3.2对结点i的每个孩子结点x执行下列操作； 估算结点x的目标函数值lb； 若（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个顶点，此时，该部分解的目标函数值的计算方法（限界函数）如下： 分支限界法求解图上机心得与体会：时间复杂性分析：分支限界法实际上属于蛮力穷举法，当然不能指望它有很好的最坏时间复杂性，遍历具有指数阶个结点的解空间树，在最坏情况下，时间复杂性肯定为指数阶。
《旅行商问题实验报告》由会员M****1分享，可在线阅读，更多相关《旅行商问题实验报告》请在金锄头文库上搜索。
幼儿园各类突发事故应急预案汇编
东北财经大学22春《财务分析》离线作业二及答案参考5
为进一步规范公务用车
关于成立建筑保温材料公司方案
大连理工大学校园一卡通资金管理办法5篇
好婆婆典型事迹材料
2023年浙江省绍兴市上虞区崧厦街道双埠村社区工作人员考试模拟题及答案
教师成长经验反思
刘成德谈洪传太极拳
防坠落安全保障措施正式样本
最新【人教版】数学八年级上学期期末复习第13章轴对称试卷及答案
高考励志演讲稿：坚定信念超越自我
附件新乡市房地产市场报告
写六一儿童节的作文400字7篇
小学德育课教案
寒假打工社会实践心得体会12篇(暑假打工社会实践心得)
2023年江苏无锡江阴市残疾人联合会下属事业单位招考聘用特殊人才笔试参考题库含答案解析
幼师个人工作总结报告范文（3篇）.doc
第1课 俄国十月革命1
浅谈配合土建铝模板工艺的机电预埋施工2015.09.15
电话客服工作总结标准范本（4篇）.doc
2023-01-10 10页
销售员试用期工作总结范本（三篇）.doc
2022-11-01 8页
新建中学弘扬民族精神月活动方案
2022-07-21 6页
田庙乡精神文明建设现状与对策分析
2023-04-04 7页
2023保育员工作总结（2篇）.doc
2023-12-27 4页
转正个人自我鉴定范文合集六篇
2023-07-02 12页
永远讲不完的故事读后感15篇
2024-02-28 15页
2022年企业员工培训个人工作总结
2023-03-30 2页
电力员工个人工作总结
2023-10-23 7页
学生管理工作心得体会
2023-06-03 10页