算法设计分支界限法实验_第1页
算法设计分支界限法实验_第2页
算法设计分支界限法实验_第3页
算法设计分支界限法实验_第4页
算法设计分支界限法实验_第5页
全文预览已结束

下载本文档

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

文档简介

1、南阳理工学院算法设计与分析报告册开课学院:计算机与信息工程学院 实验项目：分支限界法实验 实验时间：实验地点：指导教师：学生姓名：学生学号： 1806905030专业班级：18大数据2019-2020学年第2学期一、实验目的了解分支限界法思想和类型掌握使用分支限界法求解问题的一般步骤能够针对实际问题，分析正确问题的解空间、解空间的组织结构、搜索的约束条件、限界条件，优先级。能够正确使用队列、优先队列正确编码。能够正确分析算法的时间复杂度和空间复杂度二、实验平台Windows操作系统或Linux操作系统Python3.xpyCharm 或 sublime 或 jupyter notebook三、

2、实验内容旅行售货员问题四、算法设计问题分析一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要 经过所有城市后，回到出发地。应如何选择行进路线，以使总的行程最短。问题建模该问题实质是在一个带权完全无向图中，找一个权值最小的Hamilton回路。 由于该问题的可行解是所有顶点的全排列，随着顶点数的增加，会产生组合爆炸， 它是一个NP完全问题。算法描述找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函 数值达到极大或极小的解，即在某种意义下的最优解。五、算法源码import math from heapq import * n = 4x = 1, 2, 3, 4#定义

3、图的字典形式G = 1:2:15, 3: 3, 4: 2,2:1:15, 3: 2.5, 4: 5,3:1:3, 2: 2.5, 4: 10,4:1:2, 2: 5, 3: 10#定义图的数组形式 graph =0, 15, 3, 2,15, 0, 2.5, 5,3, 2.5, 0, 10,2, 5, 10, 0bestcost = math.infnowcost = 0 #全局变量,现在的花费#设置节点美class Node:#构造函数,现在的花费,到目前的路径def _init_(self, w=math.inf, route=, cost=0): self.weight = w self.route = route self.cost = cost#重载比较，用于堆的排序def _lt_(self, other): return int(self.weight) = bestcost:continue#如果到了最后一个点,加上回去的路，并计算最小值if len(node.route) = 4: wholecost = graphnode.route1s + node.cost if wholecost i MvnMiEEJE* 、*八、实验总结了解了分支限界法思想和类型，掌握了如何使用分支限界法求解问题的一 般步骤，能够针对实际问题，分析正确问题的解空间、解空间的组

人人文库> 全部分类> 图纸下载 > 毕业设计

温馨提示

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

最新文档

评论

0/150

提交评论