当前位置：文档之家 › 中国邮递员问题 ppt课件

中国邮递员问题 ppt课件

  • 格式：ppt
  • 大小：1.90 MB
  • 文档页数：37

下载文档原格式

  / 37

合集下载

运筹学 中国邮递员问题

运筹学 中国邮递员问题

§4.中国邮递员问题（Chinese Postman Problem）1．问题的提出例5. 一个邮递员从邮局出发投递信件, 然后再返回邮局, 如果他必须至少一次地走过他负责投递范围内的每条街道, 街道路线如下图所示, 问选择怎样的路线才能使所走的路为最短?5 6 78问题的图论表述：在赋权G=[V, E]上找一条经每条边至少一次的权最小的圈。

1960年山东师范学院管梅谷教授首先提出此问题，并设计了一个“奇偶点表上作业法”，后来发现此法不是多项式算法，1973年，Edmonds和Johnson给出一个多项式算法。

2．哥尼斯堡七桥问题18世纪在哥尼斯堡城(今俄罗斯加里宁格勒)的普莱格尔河上有7座桥，将河中的两个岛和河岸连结，如下图所示。

城中的居民经常沿河过桥散步，于是提出了一个问题：能否一次走遍7座桥，而每座桥只许通过一次，最后仍回到起始地点。

3．Euler圈Euler圈：经图G的每条边的简单圈Euler图：具有Euler圈的图Euler图非Euler图下面讨论的图G允许有重边，且重边被认为是有区别的边。

伪Euler 圈：经图G 的每条边至少一次的圈点v 的次：与点V 关联的边的数目奇(偶)点：该点的次为奇(偶)数命题1：G 的奇点个数为偶数命题2：G 中有伪Euler 圈 ⇔ G 无奇点中国邮递员问题可表述为：在图G 中找一条权最小的伪Euler 圈。

对于邮递员来说，有些街道可能会重复走，原问题便转化为尽可能少走重复的 街道。

我们将这些重复的边组成的集合称可行集，即找最小的可行集。

命题3：E *是最小可行集 ⇔ωωμμμ()()()()*()*()e e e E E E e E E ≤∑∑∀μ∈∩∈∩\初等圈重复的边 非重复的边4．算法思路由命题1，简单图G 的奇点个数为偶数，可设为v 1 , v 2 , …, v 2k , 对每个1≤ i ≤k, 找v 2i − 1 至v 2i 的链p i ，将p i 的边重复一次。

中国邮递员问题

中国邮递员问题

管梅谷
管梅谷教授。 上海市人。1957年毕业于华 东师范大学数学系。历任 山东师范大学讲师、副教 授、教授、校长，中国运 筹学会第一、二届常务理 事，山东省数学学会第四 届副理事长，山东省运筹 学会第一届副理事长，山 东省世界语协会理事长。 是第六届全国政协委员。 从事运筹学及其应用的研 究，对最短投递路线问题 的研究取得成果。所提模 型在国外称为中国投递问 题。
求解。
推广的中国邮递员问题： 混合图的中国邮递员问题，有各种限制 的中国邮递员问题，动态网络的中国邮 递员问题。 其他相关问题-旅行售货员（TSP）问题， 灾清巡视路线。

谢谢!
v1 2 5 v2 5 9 v3 v4 图2 3 v8
4
3
v7
6
v9 4 4 4
v6
4
v5

这样就得到初始方案.在这个图中，没有奇点， 故称它为欧拉图。对应于这个可行方案，重复 边总权为51。
思考



这样的可行方案是不是只有一种呢？ 在确定一个可行方案后，怎么判断这个方案是 否为最优方案？ 若不是最优方案，如何调整这个方案？

欧拉图及求欧拉回路的算法
欧拉行迹—含所有边恰好一次的行迹 欧拉回路—含所有边恰好一次的回路 欧拉图—存在欧拉回路的图

设G是连通图, 下列命题等价: (1) G是欧拉图. (2) 每个顶点的度数都是偶数. (3) G是两两无公共边的圈的并.
欧拉图及求欧拉回路的算法
求欧拉回路的算法(Fleury算法，1921年) 算法思想: “过河拆桥,尽量不走独木桥”. 即若已选定迹 Wi v0e1v1e2 eivi , 从 G Wi 中选 取下一条边 ei 1 使得ei 1 与 vi 相关联, 且ei 1 不是 G Wi 的桥, 除非无边可选.

中国邮递员问题

中国邮递员问题

（割边）
FE算法复习：
(1)任取 v0属于V(G),令W0=v0. (2)设行迹Wi=v0v1v2…vi已选定，则从E(G)-E(W)中 选一条边ei+1,使得ei+1与vi相关联，且非必要时， ei+1 不要选G-E(W)的桥（所谓桥是一条删除后使连通图 不再连通的边）。 (3)反复执行(2), 直至每边e属于E(G)皆入选为止。

情况2：加权图G中有奇次顶时中国邮路问 题的解法（某些边要通过两次）
解法步骤：设G是连通加权图 1）求G中奇次顶集合V0； 2）对V0中的每个顶对u,v,用Dijkstra算法求距离d(u,v); 3)构造加权完全图K|V0|,完全图中顶点即为V0中顶点，边uv 之权为d(u,v); 4）求加权图K|V0|的总权最小的完备匹配M。 5）在G中求M中同一边之端点间的最短轨。 6）把G中在（5）求得的每条最短轨之边变成同权倍边，得 Euler图G’. 7)用FE算法求G’的一条Euler回路W’,W’即为中国邮路。 实例探讨

中国邮递员问题--邮递员从选好邮件去投递，然后返回邮 局，必须经过由他负责的每条街道至少 一次，怎么走耗时最少？
情况 1：邮路可抽象为 Euler图，则所有路经过恰好一次。 情况 2：邮路抽象成的图 G中包含奇次顶。（有的路径需要 重复走）
情况1：仍要遵循一定规则走
定理6.3
若G是Euler图，FE算法终止时得 到的W是Euler回路。
本质：此算法能实现无重复边的一笔画，且
回到出发点。

证明思路 （1）证明是闭行迹。 （2）证明能够经过一切边。（反证不能经过一切边）
基本概念复习
行迹：各边相异的道路。 Euler行迹：在图G中含一切边的行迹。 Euler回路：含一切边的闭行迹。 Euler图：若G中存在Euler回路。

运筹学最短路邮递员问题PPT课件

运筹学最短路邮递员问题PPT课件

从一点到任意点的最短路
• 木器厂有六个车间，办事员经常 要到各个车间了解生产进度。从 办公室到各车间的路线由图1给出。
找出点1（办公室）到其它各点 （车间）的最短路
11
27
2
2
1 5 3 5 55 7
3
1
4
3
1
6
7
5
12
2
权wij(dij)
2
距离、价格 2
15
3
点（vi）
边eij或记为（vi，vj） 13
3
5
3
3 0 v1
v2
3
v6
2.5
2
53
1
2
v3
4 3
4
v7 2
v4
v9
4 v8
41
v5
3
5
3
3 0 v1
v2
3
v6
2.5
2
53
1
2
v3
4 3
4
v7 2
v4
v9
4 v8
42
6 v5
3
5
3
v2
3
6
3
v6
2.5
0
v1
2
53
1
2
v3
4 3
4
v7 2
v4
v9
4 v8
43
6 v5
3
5
3
v2
3
6
3
v6
2.5
最短路问题不仅可以求解交通图中两点之间的最短距离，实际 中很多问题也可变为最短路问题加以求解。例如设备更新问题，厂 区合理布局问题等。兹举一例：
例1（设备更新问题）某企业使用一台设备，在每年年底，企业 都要决策下年度是购买一台新设备呢？还是继续使用这台设备。若 购买新的，就要支付一笔购置费；如果使用旧设备，只要支付维修 费，而维修费随着设备的使用年限延长而增加。现根据以往统计资 料已经估算出设备在各年初的价格和不同使用年限的修理费用，分 别如表1、表2所示。

中国邮递员问题(第五版)

中国邮递员问题(第五版)

中国邮递员问题引言H T T P ://W W W .588K U .C O M /P P Tu 中国邮递员问题是由山东师范大学管梅谷同志1960年首先提出的。

u 该问题涉及著名的的哥尼斯堡(Königsberg)七桥问题。

u 这是数学中为数不多的几个以“中国”命名的问题或定理之一。

u 七桥问题是图论和拓扑学的起源。

引言1哥尼斯堡七桥问题2欧拉图及判定定理3Fleury算法4中国邮递员问题5奇偶点图上作业法6理论根据（选讲）哥尼斯堡(Königsberg)今称加里宁格勒，建城于1255年，是位于波罗的海海岸的俄罗斯海港城市与加里宁格勒州的首府。

加里宁格勒州位于波兰北方、立陶宛西南，原为德国东普鲁士一部分，现为俄罗斯的外飞地。

图1 加里宁格勒图2 哥尼斯堡七桥示意图有一条普雷格尔(Pregel)河流经哥尼斯堡，河上有七个桥。

一个散步者能否从某处出发走遍七个桥且每个桥只走一次，最后回到出发点？哥尼斯堡七桥问题大数学家欧拉在1736年解决了这个问题。

欧拉Euler(1707-1783)莱昂哈德·欧拉（Leonhard Euler，1707年4月15日－1783年9月18日）u瑞士数学家和物理学家，近代数学先驱之一。

u欧拉是18世纪数学界最杰出的人物之一。

u欧拉是科学史上最多产的一位杰出的数学家，据统计他那不倦的一生，共写下了886本书籍和论文。

u30岁左右右眼几乎完全失明，60岁左右左眼又几乎完全失明。

u在1775年，他平均每周就完成一篇数学论文。

u1783年9月18日于俄国彼得堡去逝。

n 将上图中A，B，C和D这四个区域各看成一个顶点，两区域之间有一个桥相连，就将相应的两个顶点连一条边，得到一个图。

AB CD图3 七桥问题对应图欧拉Euler(1707-1783)的走法为一个欧拉通路。

n如果进一步该走法还回到出发点，则称之为欧拉环游（回路）。

n具有欧拉环游的图称之为欧拉图。

中国邮递员问题

中国邮递员问题
? 这个问题就是一笔画问题。
12
管梅谷
管梅谷教授。
上海市人。1957年毕业于华 东师范大学数学系。历任 山东师范大学讲师、副教 授、教授、校长，中国运 筹学会第一、二届常务理 事，山东省数学学会第四 届副理事长，山东省运筹 学会第一届副理事长，山 东省世界语协会理事长。 是第六届全国政协委员。 从事运筹学及其应用的研 究，对最短投递路线问题 的研究取得成果。所提模 型在国外称为中国投递问 题。
? 定理：任何一个图中的奇点个数必为偶 数。
? 推论：连通的多重图有尤拉链，当且仅 当图中有两个奇点。
8
欧拉图及求欧拉回路的算法
? 欧拉行迹—含所有边恰好一次的行迹 ? 欧拉回路—含所有边恰好一次的回路 ? 欧拉图—存在欧拉回路的图
? 设G是连通图, 下列命题等价: (1) G是欧拉图. (2) 每个顶点的度数都是偶数. (3) G是两两无公共边的圈的并.
? 一笔画问题：从某一点开始画画，笔不离纸， 各条线路仅画一次，最后回到原来的出发点。
5
v1 a
b
c
v2
v3
v4
图1
图2
? 图1和图2当中哪一个图满足：从图中任何一点出 发，途径每条边，最终还能回到出发点？
? 试想：一个图应该满足什么条件才能达到上面要
求呢？
6
一笔画问题
? 凡是能一笔画出的图，奇点的个数最多 有两个。始点与终点重合的一笔画问题， 奇点的个数必是0。
13
中国邮递员问题
在一个连通的赋权图G（V，E）中，求一 条回路，使该回路包含G中的每条边至少 一次，且该回路的权最小．（称此回路 为最优回路或者中国邮路）
14
求解中国邮递员问题的算法
如果中国邮递员问题中的图是 欧拉图，那么欧拉回路就是最优回路。

运筹学最短路邮递员问题PPT课件


•
新的T（vj）=min{老的T（vj），p（vi）+ ωij }
• 若T（vj）= p（vi）+ ωij ，则记k（vj ）=vi（前点标记）;
• 3°找出具有最小T标号的点，将其标号改为p标号。若vt 已获得p
标号，则已找到最短路，由k（vt）反向追踪，就可找出vs 到vt 的最
短路径，p（vt）就是vs 到vt 的最短距离。否则，转2°。
p（v2）
=3 3
p（v1） v1
p（v=30）
=4
6
v2
51 1
v4
7 4
v5
v3 3 2
5
v7
26 v6 9 15
v8
T（v4）=min{6,4+1}=5, k（v4 ）=v3
T（v6）=min{7,4+2}=6, k（v6 ）=v3
目前，点v4 具有最小T标号，将其标号改为p标号： p（v4）=5；
向继续前进，则最先到达终点vt 的流所走过的路径一定是最短的。
为了实现这一想法，对假想流依次到达的点，依次给予p标号，表
示vs到这些点的最短距离。对于假想流尚未到达的点给予T标号，
表示vs到这些点的最短距离的估计值。具体作法如下：
• 1°标p（vs）=0，其余点标T（vi）=+∞;
• 2°由刚刚获得p标号的vi 点出发，改善它的相邻点vj 的T标号,即
对于点v2 ：d（v2）=min｛16+31,22+23,30+18,41｝=41， v对2→于v点6 v；1 ：d（v1）=min｛16+41,22+31,30+23,41+18,59｝
试确定一个五年内的设备更新计划，使五年内总支出最小。

中国邮递员问题——欧拉巡回

要求1）的解法1 由于是双车道，因此可将每条边看成来回两条 异向弧，此时，图是有向欧拉图，可用hierholzer算 法在有向图上求出有向欧拉巡回。 10 v2 6 v3 v1 6 v6 5 v12 8 v4 5 7 v7 4 3 3 v5 4 9 6 5 v9 1 v10 2 v15
2 v8 3
v11 1 1 v13 v14
基本概念与基本结论
无向图的情形
设G=(V,E)是连通无向图。 G=(V,E)是连通无向图 是连通无向图。 1）巡回：经过G的每边至少一次的封闭路线。 巡回：经过G的每边至少一次的封闭路线。 2）欧拉巡回：经过G的每边正好一次的巡回。 欧拉巡回：经过G的每边正好一次的巡回。 3）欧拉图：存在欧拉巡回的图。 欧拉图：存在欧拉巡回的图。 4）欧拉道路：经过G的每边正好一次的道路。 欧拉道路：经过G的每边正好一次的道路。 5）最佳巡回：加权连通图的边权总和最小的巡回。 最佳巡回：加权连通图的边权总和最小的巡回。
求欧拉图欧拉巡回的算法
Fleury算法 Fleury算法 是欧拉图。 设G是欧拉图。 V(G) = {v0,v1,…,vn} , E(G) = {e1,e2,…,em} 1) 任选顶点为v0 ，置途径W= v0 。 任选顶点为v 置途径W= 2) 设途径W= v0 e1v1… ei vi已经选定，则按下述条件 设途径W= 已经选定， 中选取e 从E - {e1,e2,…, ei}中选取ei+1。 相关联。 （a） ei+1与vi相关联。 除非没有别的选择，否则一定要使e （b） 除非没有别的选择，否则一定要使ei+1不是 G - {e1,e2,…, ei}的割边。 的割边。 3 ) 当第2步不能执行时，算法停止。 当第2步不能执行时，算法停止。 停止后， 即是所求欧拉回路。 停止后，W 即是所求欧拉回路。

中国邮递员问题——欧拉巡回


案例1：双车道公路扫雪模型
深度优先搜索法遍历求解
威廉王迷宫
c
f
b
d e
g
l
i
j
h
k
x
a
案例1：双车道公路扫雪模型
深度优先搜索法遍历求解
要求1）的解法2（续）
扫雪车行驶规则： 1. 从起点出发，优先选择未作业过的路段； 2. 到达交差路口时，若身后路面的两个车道都已 铲且前面还有未作业过的路段，或前方路段都 未作业过，则驶入最靠右边的路段继续作业； 否则，身后路面只铲了一个车道，应掉头铲另 一个车道。 3. 行驶到一头不通的道路尽头应掉头，在反向车 道上作业。
求添加的重复边权和近可能小； 2) 在G*中求一条欧拉巡回。
走两条重复边相当于原图的边走两遍。
结论：若连通图G正好有两个奇次顶点u,v，沿u到v 的一条最短路径添加重复边得到欧拉图G*, 则G*的 欧拉巡回便是G的最佳巡回。
求解中国邮递员问题的算法
最小权对集法（Edmonds) 设G是连通加权图。 1) 求G的所有奇次顶点之间的最短路径及其
迷宫任务：从迷宫入口处出发，每个走廊都要搜索，最后 再从入口出来．
案例1：双车道公路扫雪模型
深度优先搜索法遍历求解
要求1）的解法2（续）
迷宫法则： 1）沿着未走过的通道尽可能远地走下去，走到死胡 同或那里已无末走过的走廊可选时，沿原路返回； 2）到达路口，若有未走过的走廊时，沿这一走廊尽 可能远地走下去，…，最后即可按索退全部走廊 和厅室，再由入口处出迷宫．
法在有向图上求出有向欧拉巡回。
v1
10
v2
6
v3
6
8
v4 5
3 v5
v6
v7
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

中国邮递员问题
管梅谷教授首先提出的方法是奇偶点图上作业 法（1962年）
Edmonds，Johnson（1973年）给出有效算法。
复杂度为 O(|V(G)|2|E(G)|)
中国邮递员问题
中国邮递员问题
解决这样的问题，可以采用奇偶 点图上作业法：如果在配送范围 内，街道中没有奇点，那么他就 可以从配送中心出发，走过每条 街道一次，且仅一次，最后回到 配送中心，这样他所走的路程也 就是最短的路程。
原来的问题可以叙述为在一个有奇点的图中， 要求增加一些重复边，使新图不含奇点，并且 重复边的总权为最小。
我们把使新图不含奇点而增加的重复边简称为 可行（重复边）方案，使总权最小的可行方案 为最优方案。
现在的问题是第一个可行方案如何确定？ 在确定一个可行方案后，怎么判断这个方案是
否为最优方案？ 若不是最优方案，如何调整这个方案？
Fleury算法的复杂度是 O(| E(G)|2)
中国邮递员问题
求欧拉回路的算法(回路算法)
算法思想: 首先得到一个回路C1, 再在剩
下的图G- C1中求一条与C1有公共顶点的
回路C2, 则C1与 C2构成一个更长的回路,
继续下去可得到含所有边恰好一次的回
路. 回路算法的复杂度是
O(|
E(G) |)
这个问题就是一笔画问题。
中国邮递员问题
管梅谷教授。
上海市人。1957年毕业于华 东师范大学数学系。历任 山东师范大学讲师、副教 授、教授、校长，中国运 筹学会第一、二届常务理 事，山东省数学学会第四 届副理事长，山东省运筹 学会第一届副理事长，山 东省世界语协会理事长。 是第六届全国政协委员。 从事运筹学及其应用的研 究，对最短投递路线问题 的研究取得成果。所提模 型在国外称为中国投递问 题。
中国邮递员问题
求欧拉回路的算法(Fleury算法，1921年) 算法思想: “过河拆桥,尽量不走独木桥”.
即若已选定迹 W iv0e1v1e2 eivi, 从G Wi 中选 取下一条边e i 1 使得e i 1 与 v i 相关联, 且e i 1 不是 G Wi 的桥, 除非无边可选.
奇点：那个点的角度来看，数有多少条线从连接着那 个点，如果连接那个点的线的数量是奇数条，那这个 点就是奇点，反之，就是偶点。
在一个多重边的连通图中，从某个顶点 出发，经过不同的线路，又回到原出发 点，这样的线路必是尤拉图，即能一笔 画出的图必是尤拉图。
中国邮递员问题
定理：连通的多重图G是尤拉图，当且仅 当G中无奇点。
中国邮递员问题
在一个连通的赋权图G（V，E）中，求一 条回路，使该回路包含G中的每条边至少 一次，且该回路的权最小．（称此回路 为最优回路或者中国邮路）
中国邮递员问题
如果中国邮递员问题中的图是欧拉 图，那么欧拉回路就是最优回路。
一般情形下（不是欧拉图），最优 回路包含某些边至少两次。这时求最优 回路的思想是：在图G中添加一些重复边 使新图G*成为欧拉图，且使得所有添加 的重复边的权和最小。再由G*的欧拉回 路得到G的最优回路。
定理：任何一个图中的奇点个数必为偶 数。
推论：连通的多重图有尤拉链，当且仅 当图中有两个奇点。
中国邮递员问题
欧拉行迹—含所有边恰好一次的行迹 欧拉回路—含所有边恰好一次的回路 欧拉图—存在欧拉回路的图
设G是连通图, 下列命题等价: (1) G是欧拉图. (2) 每个顶点的度数都是偶数. (3) G是两两无公共边的圈的并.
中国邮递员问题
对于有奇点的街道图，该怎么办呢？ 这时就必须在每条街道上重复走一次或多次。
中国邮递员问题
如图所示。
v1 2 v3
5 v5
3
4
26 8
v2
4 v4
4 v6
如果在某条路线中，边[vi,vj]上重复走几次， 我们就在图中vi,vj之间增加几条边，令每条 边的权和原来的权相等，并把所增加的边，称 为重复边，于是这条路线就是相应的新图中的 尤拉图。
中国邮递员问题
中国邮递员问题
(Chinese Postman Problem)
中国邮递员问题
七桥问题与一笔画 中国邮递员问题 欧拉图及求欧拉回路的算法 求解中国邮递员问题的算法
中国邮递员问题
18世纪著名古典数学问 题之一。在哥尼斯堡的 一个公园里，有七座桥 将普雷格尔河中两个岛 以及岛与河岸连接起来 (如图)。问是否可能从 这四块陆地中任一块出 发，恰好通过每座桥一 次，再回到起点？
一笔画问题：从某一点开始画画，笔不离纸， 各条线路仅画一次，最后回到原来的出发点。
v1 a
b
c
v2
v3
v4
图1
图2
图1和图2当中哪一个图满足：从图中任何一点出 发，途径每条边，最终还能回到出发点？
试想：一个图应该满足什么条件才能达到上面要 求呢？
中国邮递员问题
凡是能一笔画出的图，奇点的个数最多 有两个。始点与终点重合的一笔画问题， 奇点的个数必是0。
欧拉于1736年研究并解决了 此问题， 他用点表示岛和陆
地，两点之间的连线表示连 接它们的桥，将河流、小岛 和桥简化为一个网络，把七 桥问题化成判断连通网络能 否一笔画的问题。之后他发 表一篇论文，证明了上述走 法是不可能的。并且给出了 连通网络可一笔画的充要条 件这一著名的结论。
中国邮递员问题
举个例子
车辆从某配送中心 （v1）出发，给街道
v1 2
边上的超市
5
（v2,v3,v4,vຫໍສະໝຸດ ,v6,v7,v8,v9）送货，如 图1所示。
v2 6
5
9 v3
v8 4
3 v9 4
4 4
v4 图1
v7 3
v6 4
v5
中国邮递员问题
显然街区图上有奇点（4个），不满足“一笔画” 的条件，则必然有一些街道要被重复走过（添 加重复边）才能回到原出发点。此时得到的图 就无奇点。
上述两算法都是在连通欧拉图中求欧拉 回路的算法.
中国邮递员问题
一个邮递员送信，要走完他负责投递的 全部街道，投完后回到邮局，应该怎样 走，使所走的路程最短？
这个问题是我国管梅谷同志1960年首先 求出来的，因此在国际上通称为中国邮 递员问题。在物流活动中，经常会遇到 这样的问题，如：每天在大街小巷行驶 的垃圾车、洒水车、各售货点的送货车 等都需要解决一个行走的最短路程问题。