网络优化及实例.ppt

网络优化与优化算法1ppt课件例:中国邮递员问题(CPP-ChinesePostmanProblem)(从邮局出发,经过投递区内每条街道至少一次,最后返回邮局)?由于这一问题是我国学者管梅谷教授1960年首先提出的,、网络优化及实例单向?双向?2ppt课件欧拉把哥尼斯堡七桥问题转化为一个图论上的问题:给定一个图,问是否存在点不重的环游?3ppt课件七桥问题答案的是否定的因为图中没有偶度顶点4ppt课件有些问题目前找不到现成的软件也没有快速求解最优解的方法TSP(TravelSalesManProblem)问题例4设有城市集合,城市到城市的费用为求从指定城市出发,经过所有其他城市恰好一次,且使总费用最少的旅行路线。5ppt课件TSP问题可以通过枚举的方法用计算机求解不同的路线共有(n-1)!!6ppt课件二、最优算法与近似算法有一些问题在计算复杂性上被称做NP困难问题,对这一类问题寻找快速的近似算法是十分有意义的。全国数学建模竞赛题中有一些NP困难问题的例子,需要用现有的软件结合编程进行计算,这一类近似算法的设计需要较宽的数学知识面和较强的创新能力数学建模竞赛十分强调模型与算法的创新性7ppt课件如:98年竞赛题B题是TSP问题的一个变形从县城出发分三个小组巡视受灾的地区各地的灾情,已知每个村镇所需要的停留时间以及行车速度,问如何设计各组的巡视路线才能以最快的速度掌握整个地区全部的受灾情况?8ppt课件灾情巡视路线(CUMCM-1998B)多人TSP问题的扩展9ppt课件考虑用一个图来代替县城结点,将问题转化为一个TSP问题:10ppt课件