《网络优化及实例》.ppt

该【《网络优化及实例》 】是由【相惜】上传分享，文档一共【25】页，该文档可以免费在线阅读，需要了解更多关于【《网络优化及实例》 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。网络优化与优化算法编辑课件例:中国邮递员问题(CPP-ChinesePostmanProblem)(从邮局出发,经过投递区内每条街道至少一次,最后返回邮局)?由于这一问题是我国学者管梅谷教授1960年首先提出的,、网络优化及实例单向?双向?编辑课件欧拉把哥尼斯堡七桥问题转化为一个图论上的问题:给定一个图,问是否存在点不重的环游?编辑课件七桥问题答案的是否认的因为图中没有偶度顶点编辑课件有些问题目前找不到现成的软件也没有快速求解最优解的方法TSP〔TravelSalesManProblem〕问题例4设有城市集合,城市到城市的费用为求从指定城市出发,经过所有其他城市恰好一次,且使总费用最少的旅行路线。编辑课件?TSP问题可以通过枚举的方法用计算机求解不同的路线共有(n-1)!???!编辑课件二、最优算法与近似算法有一些问题在计算复杂性上被称做NP困难问题,对这一类问题寻找快速的近似算法是十分有意义的。全国数学建模竞赛题中有一些NP困难问题的例子,需要用现有的软件结合编程进行计算,这一类近似算法的设计需要较宽的数学知识面和较强的创新能力数学建模竞赛十分强调模型与算法的创新性编辑课件如:98年竞赛题B题是TSP问题的一个变形从县城出发分三个小组巡视受灾的地区各地的灾情,每个村镇所需要的停留时间以及行车速度,问如何设计各组的巡视路线才能以最快的速度掌握整个地区全部的受灾情况?编辑课件灾情巡视路线(CUMCM-1998B)多人TSP问题的扩展编辑课件考虑用一个图来代替县城结点,将问题转化为一个TSP问题:编辑课件