DM-专题8：带权图及其应用

∑ 边的权和 w(H ) = w(e) 为H的权. 类似地，若 e∈E(H )
∑ 若P(u,v)是赋权图G中从u到v的路,称 w(P) = w(e) e∈E ( P )
称为路P的权．
2) 在赋权图G中，从顶点u到顶点v的具有最小权
的路P*(u,v)，称为u到v的最短路．
固定起点的最短路
最短路是一条路径，且最短路的任一段也是最短路． 假设在u0-ui的最短路中只取一条，则从u0到其 余顶点的最短路将构成一棵以u0为根的树．
u1
u4
u6
u8
u3
u7
中国邮递员问题 (Chinese Postman Problem)
求邮递员走遍管区所有街道的最短回路
B5 C
3
5
A 8 14 10
D
4
9
F6 E
管梅谷(Guan Mei-gu), 1962, 中国
15
2013/4/25
是欧拉图吗?
B5 C
3
5
A 8 14 10
D
4
9
F6 E
26
2013/4/25
有效(efficient)算法
复杂度是多项式函数的算法 易解(tractable)问题: 有多项式复杂度算法的问题,如欧拉回
路,匹配,中国邮递员问题等
难解(intractable)问题: 没有多项式复杂度算法的问题, 如哈 密顿回路, 着色, 货郎问题等(目前还是猜想)
27
2013/4/25
16
2013/4/25
能变成欧拉图吗?
B5 C
3
5
A 8 14 10
D
4
9
F6 E
B5 C
3
5
A 8 14 10
D
4
9
F6 E
13
17
2013/4/25
重复的边要最短
B5 C
3
5
A 8 14 10
D
4
9
F6 E
B5 C
3
5
A 8 14 10
D
4
9
F6 E
18
2013/4/25
有多对奇数度顶点怎么办?
⎢4 ∞ ∞ ∞ 3 6 0 2⎥
⎢ ⎣
8
7
∞∞∞
4
2
0
⎥ ⎦
因G是无向图，故W是对称阵．
迭代 次数
1 2 3 4 5 6 7 8 最后标记 l (v)
z (v)
l(ui )
u0 u1 u2 u3 u4 u5 u6 u7
０∞ ∞ ∞ ∞ ∞ ∞ ∞
１2
∞7 ∞4
8
2
4 7 ∞4
8
3 7 ∞4 8
694 8
5 6 7
8
6 10 12
7 10 12
8
9 12
12
最后标记:
l(v)
02
17
3
6 9 12
z (v)
u1 u1
u1 u6
u2
u5
u4
u5
最后标记:
l (v) z (v)
l(ui )
u1
u2
u3 u4
u5
u6
u2
7
3
u6
u2
u5
6 9 12 u5 u4 u5
因此, 可采用树生长的过程来求指定顶点到其余顶点 的最短路．
Dijkstra 算法：求 G 中从顶点 u0 到其余顶点的最短路 设 G 为赋权有向图或无向图，G 边上的权均非负．
对每个顶点，定义两个标记（ l(v) ， z(v) ），其中: l(v) ：表从顶点 u0 到 v 的一条路的权． z(v) ：v 的父亲点，用以确定最短路的路线
2013/4/25
旅行商问题 (Travling Salesperson Problem)
给定n个城市之间的所有距离, 求走遍所有城市的最短路线
B5 C
3
5
A 8 14 10
D
4
9
F6 E
货郎担问题, 巡回售货员问题, TSP
– 给定带权完全图G=<V,E,W>,求最短哈密顿回路
25
2013/4/25
31
2013/4/25
最小权匹配法
定理: 设最小权匹配法所得近似解长度为Kn Tn* ≤ Kn ≤ 1.5 Tn*
32
2013/4/25
中国邮递员问题 (易解) 旅行商问题 (难解)
总结
33
2013/4/25
28
2013/4/25
最邻近法(Nearest Neighbor)
在尚未到达过的城市中选取与当前城市最邻近的城市作为下 一个要访问的城市
设问题规模为n时最短哈密顿回路长度为Tn*, 用最近邻法所 得近似解长度为Nn
29
2013/4/25
最小生成树
T是G=<V,E,W>的生成树 (1) W(T)——T各边权之和 (2) 最小生成树——G的所有生成树中权最小的
计算复杂度(complexity)
算法工作时需要的计算资源(如时间,空间等)量T, 随输入规模 n扩大而增加的函数关系, 如T(n)=n2, T(n)=2n等
输入规模(input size): 反映输入大小的量, 如图的顶点数n, 边数m等
最坏情形(worst-case): 在所有规模为n的输入上, 算法工作 所需要的最大资源量
第八章 带权图及其应用
8.1 最短路问题 8.3 中国邮递员问题 8.6 旅行商问题
1
2013/4/25
带权图(weighted graph)
G=<V,E,W>, W: E→R, W(e)称为e的权
B5 C
3
5
A 8 14 10
D
4
9
F6 E
2
2013/4/25
公路边的数字为该路段的公里数.
最短路问题及算法
A2 B1 C1 D2 E
1
6
5
3
I 2H
4
G2 F
19
2013/4/25
中国邮递员问题解法
(1) 求带权图G所有奇数度顶点之间的短程线 (2) 用所有奇数顶点和短程线做带权完全图K (3) 求K的最小完美匹配M (4) 用M给G沿短程线加重复边得G* (5) 求G*的欧拉回路Γ
多项式时间算法! (易解问题)
最短路问题是图论应用的基本问题，很多实际 问题，如线路的布设、运输安排、运输网络最小费 用流等问题,都可通过建立最短路问题模型来求解.
•最短路的定义 •最短路问题的两种方法：Dijkstra和Floyd算法 .
1) 求赋权图中从给定点到其余顶点的最短路. 2) 求赋权图中任意两点间的最短路.
定义 1) 若H是赋权图G的一个子图，则称H的各
G1
6
5
3
I 2H
4
G2 F
B2 K5 7
H4
D 57
G
A2 B1 C1 D2 E
G* 1
6
5
3
I 2H
4
G2 F
23
2013/4/25
最优路线及其长度
A2 B1 C1 D2 E
1
6
5
3
I 2H
4
G2 F
B2 58
D 57
H4 G
A2 B1 C1 D2 E
1
6
5
3
I 2H
4
G2 F
最优路线Γ=ABCDEFGH24BCDGHIA, W(Γ)=35
⎜ ⎜ ⎝
0
3 0
⎟ ⎟ ⎠
因 G 是无向图，故 W 是对称阵．
迭代
l(ui )
次数
u1 u2 u3 u4 u5 u6 u7
u8
１ ０ ∞ ∞ ∞ ∞ ∞ ∞ ∞
2 0 ２ １ ８ ∞ ∞ ∞ ∞
3
2
8
∞ ∞ 10 ∞
4
8
3 ∞ 10 ∞
求最小生成树的一个算法 避圈法（Kruskal）设G=<V,E,W>，将G中非环边按权从小 到大排序：e1, e2, …, em. (1) 取e1在T中 (2) 查e2，若e2与e1不构成回路，取e2也在T 中，否则弃e2. (3) 再查e3,…, 直到得到生成树为止.
30
最小生成树法
定理: 设最小生成树法所得近似解长度为Hn Tn* ≤ Hn ≤ 2Tn*
20
2013/4/25
求奇数度顶点之间短程线
A2 B1 C1 D2 E
1
6
5
3
I 2H
4
G2 F
B2 57
D 57
H4 G
21
2013/4/25
求奇数度顶点之间最小完美匹配
A2 B1 C1 D2 E
1
6
5
3
I 2H
4
G2 F
B2 57
D 57
H4 G
22
2013/4/25
重复边总长最短
A2 B1 C1 D2 E
（2）更新 l(v) 、 z(v) ： ∀v ∈ S = V \ S ,若 l(v) > l(u) + W(u,v) 则令 l(v) = l(u) + W(u,v) , z(v) = u
（3） 设 v * 是使 l(v) 取最小值的 S 中的顶点，则令 S=S∪{ v * }， u ← v*
（4） 若 S ≠ φ，转 2，否则，停止. 用上述算法求出的 l(v) 就是 u0 到 v 的最短路的权，从 v 的父亲标记
TSP的复杂度
目前还不知道TSP是否有多项式时间算法, 大多数学者认为没 有.