2015优化模型邮递员问题.ppt

网络优化模型 -中国邮递员问题 (Chinese Postman Problem) 主要内容 网络优化模型简介 中国邮递员问题及其网络模型 欧拉图及求欧拉回路的算法 扫雪问题 求解中国邮递员问题的算法 实践与思考 参考文献 网络优化模型简介 网络 = 赋(加)权图 网络优化问题, 即在网络中求权最大（或最小）的某类子网络 基本而重要的网络优化问题有: 最小树问题 最短路问题 网络流问题 中国邮递员问题 旅行售货员问题 匹配问题 中国邮递员问题及其网络模型 问题: 一名邮递员带着要分发的邮件从邮局出发，经过要分发的每条街道，送完邮件后又返回邮局．如果他必须至少一次走过他管辖范围内的每一条街道，如何选择投递路线，使邮递员走尽可能短的路程． 这个问题是由我国数学家管梅谷教授在1962年首次提出并研究的，因此在国际上称之为中国邮递员问题． 中国邮递员问题及其网络模型 网络模型： 在一个连通的赋权图G（V，E）中，求一条回路，使该回路包含G中的每条边至少一次，且该回路的权最小．（称此回路为最优回路或者中国邮路） 欧拉图及求欧拉回路的算法 欧拉行迹—含所有边恰好一次的行迹 欧拉回路—含所有边恰好一次的回路 欧拉图—存在欧拉回路的图 设G是连通图, 下列命题等价: (1) G是欧拉图. (2) 每个顶点的度数都是偶数. (3) G是两两无公共边的圈的并. 欧拉图及求欧拉回路的算法 求欧拉回路的算法(Fleury算法，1921年) 算法思想: “过河拆桥,尽量不走独木桥”. 即若已选定迹 , 从 中选取下一条边 使得 与 相关联, 且 不是 的桥, 除非无边可选. Fleury算法的复杂度是 欧拉图及求欧拉回路的算法 求欧拉回路的算法(回路算法) 算法思想: 首先得到一个回路C1, 再在剩下的图G- C1中求一条与C1有公共顶点的回路C2, 则C1与 C2构成一个更长的回路, 继续下去可得到含所有边恰好一次的回路. 回路算法的复杂度是 注意到上述两算法都是在连通欧拉图中求欧拉回路的算法. 扫雪问题（描述） 一场雪后，从位于地图(下图90B-1) *标记地点以西4英里的二处车库派出两辆扫雪车。求用两辆扫雪车扫清马路上的雪的有效的方法。 假设扫雪车可以利用高速公路进出扫雪区，扫雪车既不会发生故障也不停顿，在交叉路口不需特别的扫雪方法。图中的实线表示马里兰州威考密科县中扫雪区域中的二车道马路，虚线表示州属高速公路。 扫雪问题（图示） 扫雪问题分析 由于是二车道马路，所以相应的图是欧拉图。可以求出它的欧拉回路。假设只用一辆车清扫，那么只要沿着欧拉回路清扫即可（不重复）。 目前是两辆车，所以需要把该问题相应的图划分成总长度尽可能相等的两个子图（这是NPC问题。可先划分再逐步调整），每个子图是欧拉图，再分别清扫。 求解中国邮递员问题的算法 如果中国邮递员问题中的图是欧拉图，那么欧拉回路就是最优回路。 一般情形下（不是欧拉图），最优回路包含某些边至少两次。这时求最优回路的思想是：在图G中添加一些重复边使新图G*成为欧拉图，且使得所有添加的重复边的权和最小。再由G*的欧拉回路得到G的最优回路。 求解中国邮递员问题的算法 管梅谷首先提出的方法是奇偶点图上作业法（1962年） Edmonds，Johnson（1973年）给出有效算法。 复杂度为 求解中国邮递员问题的算法（ Edmonds，Johnson,1973年） 求解中国邮递员问题的算法（例） 求解中国邮递员问题的算法（例） 实践与思考 清扫街道问题（见下面问题） 利用 Edmonds和Johnson算法求解。 推广的中国邮递员问题： 混合图的中国邮递员问题，有各种限制的中国邮递员问题，动态网络的中国邮递员问题。 其他相关问题-旅行售货员问题，灾清巡视路线。 清扫街道问题 清扫街道问题 主要参考资料 图论, 王树禾 编著, 科学出版社，2004年 谢金星 、邢文训，《网络优化》 ，清华大学出版社，2003年。 谢政, 网络算法与复杂性理论?, 国防科技大学出版社，2003 年。 数学建模----方法与范例, 寿纪麟主编, 西安交通大学出版社, 1993年. (网络模型) 数学建模导论, 陈理荣主编, 北京邮电大学出版社,1999年 问题？ 谢谢! CUMCM1998-B 灾情巡视路线