当前位置:首页 >> 政史地 >> 图论与网络优化 讲稿(4)PPT

图论与网络优化 讲稿(4)PPT


引例: 1 哥尼斯堡七桥问题 哥尼斯堡位于前苏联的加里宁格勒, 历史上曾经是德国东普鲁士省的省会, 普雷格尔河横穿城堡,河中有两个小岛, 共有七座桥连接两岸和小岛。

哥尼斯堡人在寻找一条路线从某点出发经 过每个桥一次回到出发点。

欧拉将其概括为数学模型 ,“七桥”问 题变为“一笔画”问题。
A

C

r />
D

B

2 欧拉图和中国邮递员问题 欧拉图:如果从某点出发能经过图的每 个边恰好一次再回到出发点,那么称此图为 欧拉图。图为欧拉图的充要条件是每个点的 度是偶数。 1962年中国组合数学家管梅谷教授提出 了著名的“中国邮递员问题”:一个邮递员 从邮局出发,要走完他所管辖的每一条街道, 然后返回邮局。那么如何选择一条尽可能短 的路线

3 哈密顿环球旅行问题 十二面体的20个顶点代表世界上20个城市, 能否从某个城市出发在十二面体上依次经过每个 城市恰好一次最后回到出发点?

哈密顿圈(环球旅行游戏)

一: 图论的基本概念
图论中的“图”并不是通常意义下的几何图 形或物体的形状图, 而是以一种抽象的形式来表 达一些确定的事物之间的联系的一个数学系统. 定义1 一个有序二元组(V, E ) 称为一个图, 记 为G = (V, E ), 其中 ① V称为G的顶点集, V≠?, 其元素称为顶点或 结点, 简称点; ② E称为G的边集, 其元素称为边, 它联结V 中的两个点, 如果这两个点是无序的, 则称该边为 无向边, 否则, 称为有向边. 如果V = {v1, v2, … , vn}是有限非空点集, 则称 G为有限图或n阶图.

如果E的每一条边都是无向边, 则称G为无向 图(如图1); 如果E的每一条边都是有向边, 则称G 为有向图(如图2); 否则, 称G为混合图. 图 1 并且常记 V = {v1, v2, … , vn}, |V | = n ; E = {e1, e2, … , em}(ek=vivj ) , |E | = m. 图 2

称点vi , vj为边vivj的端点. 在有向图中, 称点vi , vj分 别为边vivj的始点和终点.

有边联结的两个点称为相邻的点, 有一个公共 端点的边称为相邻边. 边和它的端点称为互相关联. 常用d(v)表示图G中与顶点v关联的边的数目, d(v) 称为顶点v的度数. 用N(v)表示图G中所有与顶点v 相邻的顶点的集合.

d(v1)= d(v3)= d(v4)=4, d(v2)=2.

定理1:在简单图中,所以点的度的和等于边 数的两倍.

定理2(握手定理):在简单图中,奇数点的 个数为偶数.

定义2 若将图G的每一条边e都对应一个实数F (e), 则称F (e)为该边的权, 并称图G为赋权图(网络), 记为G = (V, E , F ).

定义3 设G = (V, E)是一个图, v0, v1, …, vk∈V, 且?1≤i≤k, vi-1vi∈E, 则称v0 v1 … vk是G的一条通 路. 如果通路中没有相同的边, 则称此通路为道路. 始点和终点相同的道路称为圈或回路. 如果通路 中既没有相同的边, 又没有相同的顶点, 则称此通 路为路径, 简称路.
定义4 任意两点均有通路的图称为连通图. 定义5 连通而无圈的图称为树, 常用T表示树.

图的矩阵表示
邻接矩阵: 对无向图 ,其邻接矩阵
,其中:

例 一摆渡人欲将一只狼,一头羊,一篮菜从河 西渡过河到河东.由于船小,一次只能带一物过河, 并且狼与羊,羊与菜不能独处.给出渡河方法. 解:用四维0-1向量表示(人,狼,羊,菜)在河 西岸的状态(在河西岸则分量取1,否则取0),共有 24 =16 种状态.在河东岸的状态类似记作. 由题设,状态(0,1,1,0),(0,0,1,1),(0,1,1,1)是不 允许的,从而对应状态(1,0,0,1), (1,1,0,0), (1,0,0,0) 也是不允许的. 以可允许的10个状态向量作为顶点,将可能互 相转移的状态用线段连接起来构成一个图. 根据此图便可找到渡河方法.

(1,1,1,1) (1,1,1,0) (1,1,0,1) (1,0,1,1) (1,0,1,0) (0,0,0,0) (0,0,0,1) (0,0,1,0) (0,1,0,0) (0,1,0,1)

(0,1,0,1) (0,1,0,0) (0,0,1,0) (0,0,0,1) (0,0,0,0) (1,0,1,0) (1,0,1,1) (1,1,0,1) (1,1,1,0) (1,1,1,1) 河西=(人,狼,羊,菜) 河东=(人,狼,羊,菜) 将10个顶点分别记为A1, A2, …, A10 ,则渡河问 题化为在该图中求一条从A1到A10的路. 从图中易得到两条路: A1 A6 A3 A7 A2 A8 A5 A10; A1 A6 A3 A9 A4 A8 A5 A10.

二: 最短路与最小生成树
定义1 设P(u, v) 是赋权图G = (V, E , F) 中从 点u到v的路径, 用E(P) 表示路径P(u, v)中全部边的 集合, 记

F ( P) ?

e?E ( P )

? F (e)

则称F (P)为路径P(u, v) 的权或长度(距离).
定义2 若P0 (u, v) 是G 中连接u, v的路径, 且 对任意在G 中连接u, v的路径P (u, v)都有 F (P0)≤F(P), 则称P0 (u, v) 是G 中连接u, v的最短路.

重要性质:
若v0 v1 … vm 是图G中从v0到vm的最短路, 则 ?1≤k≤m, v0v1 … vk 必为G中从v0到vk的最短路. 即:最短路是一条路,且最短路的任一段也 是最短路. 求非负赋权图G中某一点到其它各点最短路, 一般用Dijkstra标号算法;求非负赋权图上任意两 点间的最短路,一般用Floyd算法.这两种算法均 适用于有向非负赋权图.

Dijkstra标号算法
开始,先给v1标上P标号P(v1)= 0,其余各点 标上T标号T(vj)=+∞(j≠1)。

① 如果刚刚得到P标号的点是vi,那么,对于 所有这样的点 将其T标号修改为:min[T(vj),P(vi)+wij]。 ② 若G中没有T标号,则停止。否则,把点 的T标号修改为P标号,然后再转入①。 其中, 满足

Floyd算法 ? 某些问题中,要求网络上任意两点间的最短路,如例15 就是这样。这类问题可以用Dijkstra算法一次改变起点的 办法计算,但比较繁琐。这里介绍的Floyd方法(1962) 可直接求出网络中任意两点间的最短路。 ? 为计算方便,令网络的权矩阵为 。 其中

?

算法基本步骤为:

?

首先介绍矩阵的两种运算:

例:某县下属7个乡镇,各乡镇所拥有的人口数 a(vi)(i=1,2,…,7),以及各乡镇之间的距离 wij(i,j=1,2,…,7)如图所示。现在需要设立 一个中心邮局,为全县所辖的7个乡镇共同服务。 问该中心邮局应该设在哪一个乡镇(顶点)?

图10.2.3

解: 第1步:用标号法求出每一个顶点vi 至其他各个
顶点vj的最短路径长度dij(i,j = 1,2,…,7),并 将其写成如下距离矩阵

? d11 ? ? d 21 ?d ? 31 D ? ? d 41 ?d ? 51 ? d 61 ? ? d 71

d12

d13

d14

d15

d16

d 22 d 23 d 24 d 25 d 26 d 32 d 33 d 34 d 35 d 36 d 42 d 43 d 44 d 45 d 46 d 52 d 53 d 54 d 55 d 56 d 62 d 63 d 64 d 65 d 66 d 72 d 73 d 74 d 75 d 76

3 5 d17 ? ? 0 ? ? 0 2 d 27 ? ? 3 ? 2 0 d 37 ? ? 5 ? ? d 47 ? ? 6.3 3.3 2 ? ? 9.3 6.3 5 d 57 ? ? ? 4.5 1.5 3.5 d 67 ? ? 6 3 5 ? d 77 ? ?

6.3 9.3 4.5 3.3 6.3 1.5 2 0 3 5 3 0 3.5 1.8 4.8 0

1.8 4.8

3.3 6.3 1.5

6 ? ? 3 ? 5 ? ? 3.3 ? 6.3 ? ? 1.5 ? ? 0 ?

第2步:以各顶点的载荷(人口数)加权,求每 一个顶点至其他各个顶点的最短路径长度的加权和
S (v1 ) ? ? a(v j )d1 j ? 122 .3
j ?1 7

S (v 2 ) ? ? a(v j )d 2 j ? 71 .3
j ?1

7

S (v3 ) ? ? a(v j )d 3 j ? 69 .5
j ?1
7

7

S (v 4 ) ? ? a(v j )d 4 j ? 69 .5
j ?1

S (v5 ) ? ? a(v j )d 5 j ? 108 .5
j ?1

7

S (v6 ) ? ? a(v j )d 6 j ? 72 .8
j ?1

7

S (v7 ) ? ? a(v j )d 7 j ? 95.3
j ?1

7

第3步:判断。因为
S ?v3 ? ? S ?v4 ? ? min
i

? a?v ?d
7 j j ?1

ij

? 69.5

所以,v3和v4都是图10.2.3的中位点。即:中 心邮局设在点v3或点v4都是可行的。

最小生成树
由树的定义不难知道, 任意一个连通的p, q图 (p个顶点q条边)G适当去掉q - p +1条边后, 都可以 变成树, 这棵树称为图G的生成树. 设T是图G的一棵生成树, 用F(T)表示树T中所 有边的权数之和, F(T)称为树T的权. 一个连通图G的生成树一般不止一棵, 图G的 所有生成树中权数最小的生成树称为图G的最小 生成树. 求最小生成树问题有很广泛的实际应用. 例 如, 把n个乡镇用高压电缆连接起来建立一个电网, 使所用的电缆长度之和最短, 即费用最小, 就是一 个求最小生成树问题.

求连通图G的最小生成树T的算法(Kruskal避 圈法):将图G中的边按权从小到大逐条考察, 按 不构成圈的原则加入到T 中,直到 q(T ) = p(G) -1 为止. 例如右图,其 中p(G) = 8. 其最小生成树 如下:

类似地,可定义连通 图G 的最大生成树.

破圈法

例用破圈法求下图的最小树.

算法2 步骤如下: 1) 从图G中任选一棵树T1. 2) 加上一条弦e1,T1+e1中 立即生成一个圈. 去掉此 圈中最大权边,得到新 树T2,以T2代T1,重复2)再 检查剩余的弦,直到全 部弦检查完毕为止. 再加上弦e7,得到圈 v4v5v2v4, 先求出上图的一棵生成树. 加以弦 e2,得到的圈v1v3v2v1, 去掉最大的权边e6,得到一棵 新树;如此重复进行,直到全 去掉最大的权边e2,得到一棵新 树仍是原来的树;

e2

e7 2

全部的弦均已试过,得最小树.

有序二元树 定义:若一个树的出度为二,有方向即有父 子,兄弟之分,则称其为有序二元树. 有序二元树编码: (1)根不标码. (2)兄弟有序,左为兄,标0,右为弟,标1. (3) 从根到叶的轨上依次抄出各点之码,称 为该叶的前缀码. (4)全树的叶从左到右抄出前缀码叫做该树 的前缀码,中间用逗号隔开.

U1

0

1
0

1 0

1 11 z

0

1 001 g

0
010 h 011 i

1

0 100 n

1
101 x

0 0000 a

1
0001 f

11 010 011 101 011 100 001 0000 0001 0000 100 001 0000 001

Huffman树 定义:以U0为根, U1·· Un为叶的有序二元 ·· 树, Ui代表的实物出现的概率为Pi, P1+ P2+···Pn=1, Pi的码长为它的0,1的 ··· 个数,计为Li,使得 P1 Li1+ P2 L2+···Pn Lin=min ··· 则称该有序二元树为Huffman树

构造Huffman树 例:求带权0.2,0.2,0.3,0.3的Huffman树
0.4 0.4

0.6

0.2

0.2

0.3

0.3

0.2

0.2

0.3

0.3

v

0.4

0.6

0.2

0.2

0.3

0.3

u

例:画出带权0.1, 0.1, 0.1, 0.1, 0.2,0.4的Huffman树。 例:画出带权0.2, 0.17, 0.13, 0.1, 0.1 ,0.8,0.06, 0.06,0.07,0.03 的Huffman树
0.1

0.4

0.4

0.2

0.2

0.2

0.4

0.1

0.1

0.1

二部图
定义1 设X,Y 都是非空有限集,且X∩Y =? , E ?{xy|x∈X,y∈Y}, 称G =(X, Y, E)为二部图. 二部图可认为是有限简单无向图. 色数:2 如果X中的每个点都与Y中的每个点邻接,则 称G =(X, Y, E)为完备二部图. 若F:E→R +,则称G =(X, Y, E, F )为二部赋 权图. 二部赋权图的权矩阵一般记作 A=(aij )|X|×|Y | , 其中aij = F (xi yj ).

定义2 设G =(X, Y, E)为二部图,且M ? E.若 M中任意两条边在G中均不邻接,则称M是二部图 G的一个匹配. 定义3 设M是二部图G的一个匹配,如果G的 每一个点都是M中边的顶点,则称M是二部图G的 完美匹配; 如果G中没有另外的匹配M0 ,使|M0|>|M|, 则称M是二部图G的最大匹配.(NP问题) 在二部赋权图G =(X, Y, E, F )中,权数最大的 最大匹配M称为二部赋权图G的最佳匹配. 显然,每个完美匹配都是最大匹配,反之不一 定成立.

工作安排问题之一 给n个工作人员x1, x2, … , xn安排n项工作y1, y2, … , yn. n个工作人员中每个人能胜任一项或 几项工作, 但并不是所有工作人员都能从事任何 一项工作. 比如x1能做y1, y2工作, x2能做y2, y3, y4工 作等. 这样便提出一个问题, 对所有的工作人员能 不能都分配一件他所能胜任的工作? 我们构造一个二部图G = ( X, Y, E ), 这里X = {x1, x2, … , xn},Y = { y1, y2, … , yn}, 并且当且仅当 工作人员xi胜任工作yj时, xi与yj才相邻. 于是, 问题转化为求二部图的一个完美匹配. 因为 |X|=|Y|, 所以完美匹配即为最大匹配.

求二部图G = ( X, Y, E )的最大匹配算法(匈牙 利算法,P149)迭代步骤: 从G的任意匹配M开始. ① 将X中M的所有非饱和点都给以标号0和 标记*, 转向②.

M的非饱和点即非M的某条边的顶点.
② 若X中所有有标号的点都已去掉了标记*, 则M是G的最大匹配. 否则任取X中一个既有标号 又有标记*的点xi , 去掉xi的标记*, 转向③. ③ 找出在G中所有与xi邻接的点yj , 若所有 这样的yj都已有标号, 则转向②, 否则转向④.

④ 对与xi邻接且尚未给标号的yj都给定标号i. 若所有的 yj 都是M的饱和点,则转向⑤,否则 逆向返回. 即由其中M的任一个非饱和点 yj 的标 号i 找到xi ,再由 xi 的标号k 找到 yk ,…,最后由 yt 的标号s找到标号为0的xs时结束,获得M-增广路 xs yt … xi yj , 记P ={xs yt , … , xi yj },重新记M为 M⊕P,转向①.

M⊕P = M∪P \ M∩P, 是对称差.
⑤ 将yj在M中与之邻接的点xk ,给以标号 j 和标记*, 转向②.

例 求下图所示二部图G的最大匹配.

解 ① 取初始匹配M0 ={x2 y2 , x3 y3 , x5 y5} (上图粗线所示). ② 给X中M0的两个非饱和点x1,x4都给以标 号0和标记* (如下图所示).

② 给X中M0的两个非饱和点x1,x4都给以标号 0和标记* (如下图所示).

③ 去掉x1的标记*, 将与x1邻接的两个点y2, y3 都给以标号1. 因为y2, y3都是M0的两个饱和点,所 以将它们在M0中邻接的两个点x2, x3都给以相应 的标号和标记* (如下图所示).

③ 去掉x1的标记*, 将与x1邻接的两个点y2, y3 都给以标号1. 因为y2, y3都是M0的两个饱和点,所 以将它们在M0中邻接的两个点x2, x3都给以相应 的标号和标记* (如下图所示).

④ 去掉x2的标记*, 将与x2邻接且尚未给标号 的三个点y1, y4, y5都给以标号2 (如下图所示).

④ 去掉x2的标记*, 将与x2邻接且尚未给标号 的三个点y1, y4, y5都给以标号2 (如下图所示).

⑤ 因为y1是M0的非饱和点, 所以顺着标号逆 向返回依次得到x2, y2, 直到x1为0为止.于是得到 M0的增广路x1 y2x2 y1, 记P = {x1 y2 , y2x2 , x2 y1}. 取 M1 = M0⊕P = {x1 y2 , x2 y1 , x3 y3 , x5 y5}, 则M1是比 M多一边的匹配(如下图所示).

⑤ 因为y1是M0的非饱和点, 所以顺着标号逆 向返回依次得到x2, y2, 直到x1为0为止.于是得到 M0的增广路x1 y2x2 y1, 记P = {x1 y2 , y2x2 , x2 y1}. 取 M1 = M0⊕P = {x1 y2 , x2 y1 , x3 y3 , x5 y5}, 则M1是比 M多一边的匹配(如下图所示).

⑥ 再给X中M1的非饱和点x4给以标号0和标记 *, 然后去掉x4的标记*, 将与x4邻接的两个点y2, y3 都给以标号4.

因为y2, y3都是M1的两个饱和点, 所以将它们 在M1中邻接的两个点x1, x3都给以相应的标号和标 记* (如下图所示).

⑦ 去掉x1的标记*, 因为与x1邻接的两个点y2, y3都有标号4, 所以去掉x3的标记*. 而与x3邻接的两个点y2, y3也都有标号4, 此时 X中所有有标号的点都已去掉了标记*(如下图所 示), 因此M1是G的最大匹配.

G不存在饱和X的每个点的匹配, 当然也不存 在完美匹配.

工作安排问题 给n个工作人员x1, x2, … , xn安排n项工作y1, y2, … , yn. 如果每个工作人员工作效率不同, 要 求工作分配的同时考虑总效率最高. 我们构造一个二部赋权图G = ( X, Y, E , F ), 这里X = {x1, x2, … , xn},Y = { y1, y2, … , yn}, F(xi yj ) 为工作人员xi胜任工作yj时的工作效率. 则问题转化为:求二部赋权图G的最佳匹配.

在求G 的最佳匹配时, 总可以假设G为完备二 部赋权图.若xi与yj不相邻, 可令F(xi yj )=0. 同样地, 还可虚设点x或y,使|X|=|Y|.如此就将G 转化为完 备二部赋权图,而且不会影响结果.

定义 设G =(X, Y, E, F)为完备的二部赋权图, 若L:X ∪Y →R + 满足: ?x∈X, y∈Y, L(x) + L(y)≥F(xy), 则称L为G的一个可行点标记,记相应的生成子图 为GL =(X, Y, EL , F),这里 EL ={xy∈E|L(x) + L (y) = F (xy)}. 求完备二部赋权图G = (X, Y, E, F )的最佳匹 配算法迭代步骤(P152):(KM算法) 设G =(X, Y, E, F)为完备的二部赋权图,L是 其一个初始可行点标记,通常取 L(x) = max {F (x y) | y∈Y}, x∈X, L(y) = 0, y∈Y.

M是GL的一个匹配. ① 若X的每个点都是饱和的,则M是最佳匹配. 否则取M的非饱和点u∈X,令S ={u},T =?,转向②. ② 记NL(S)={v|u∈S,uv∈GL}. 若NL(S)= T, 则 GL没有完美匹配, 转向③. 否则转向④. ③ 调整标记, 计算 aL=min{L(x) + L (y) - F (xy)|x∈S, y∈Y\T}. 由此得新的可行点标记
? L (v ) ? a L , v ? S , 令L = H, GL = GH , ? H (v) ? ? L(v) ? aL , v ? T , 重新给出GL的一个 ? c c 匹配M, 转向①. ? L(v), v ? S ? T .

④ 取y∈NL (S)\T , 若y是M的饱和点, 转向⑤. 否则, 转向⑥. ⑤ 设x y∈M, 则令S = S ∪{ x }, T = T ∪{ y }, 转向②. ⑥ 在GL中的u - y路是M- 增广路, 设为P, 并 令 M = M⊕P, 转向①.

欧拉图和中国邮递员问题 欧拉图:如果从某点出发能经过图的每 个边恰好一次再回到出发点,那么称此图为 欧拉图。图为欧拉图的充要条件是每个点的 度是偶数。 1962年中国组合数学家管梅谷教授提出 了著名的“中国邮递员问题”:一个邮递员 从邮局出发,要走完他所管辖的每一条街道, 然后返回邮局。那么如何选择一条尽可能短 的路线

v0 , v{e?vR,;vi1 ), {e2 (vi1 , vi2 ),? ? ?,{er (vir ?1 , vir )} R ? 0 1( 0

弗罗莱(Fleur y)算法
弗罗莱(Fleur y)算法思想-解决欧拉回路 Fleur y算法: 任取v0∈V(G),令P0=v0; 设Pi=v0e1v1e2…e i vi已经行遍,按下面方法 从中选取ei+1: (a)ei+1与vi相关联; (b)除非无别的边可供行遍,否则ei+1不应 该为G i=G-{e1,e2, …, e i}中的桥(所谓桥是 一条删除后使连通图不再连通的边); (c)当(b)不能再进行时,算法停止。

这个问题可以转化为:给定一个具有非负权的赋 权图G, (1)用添加重复边的方法求G的一个Euler赋权母图 G*,使得
min
e?E ( G* )\ E ( G )

?

w(e)

(2)求G*的Euler 回路。 这个问题可以由Fleur y算法和1973年著名组合数学 家J. Edmonds和Johnson 给出的一个好的算法解决。

算法步骤如下: (1)若G中无奇点,令G*=G,转2,否则转3; (2)求G*中的欧拉回路,结束; (3)求G中所有奇点对之间的最短路径; (4)以G中奇点集V’为顶点集,边(v i, v j)的权为 之间最短路径的权,得完全带权图K2k; (5) 求K2k中最小权完美匹配M; (6)将M中边对应的各最短路径中的边均在G中 加重复边,得欧拉图G*,转2。

V4

1

U1 2

1
3

1

U6
3 2 1 2

3
V3

2 U2 1 2 V1

U5

1 4 U4

U3
1 2 V2

5

G

奥数题: 设邮递员从邮局A出发,沿方格形街路走 遍所有街路后回到邮局,若方形路的每条 路长为1(千米),问邮递员至少要走多少 路程? A

Hamilton图
1) 98年全国大学生数学建模竞赛B题“最佳灾
情巡视路线”中的前两个问题是这样的:

今年(1998年)夏天某县遭受水灾. 为考察灾情、
组织自救,县领导决定,带领有关部门负责人到 全县各乡(镇)、村巡视. 巡视路线指从县政府 所在地出发,走遍各乡(镇)、村,又回到县政

府所在地的路线.

1)若分三组(路)巡视,试设计总路程最 短且各组尽可能均衡的巡视路线. 2)假定巡视人员在各乡(镇)停留时间T=2 小时,在各村停留时间t=1小时,汽车行驶速度V =35公里/小时. 要在24小时内完成巡视,至少应分 几组;给出这种分组下最佳的巡视路线.

公路边的数字为该路段的公里数.

2) 问题分析: 本题给出了某县的公路网络图,要求的是在不 同的条件下,灾情巡视的最佳分组方案和路线. 将每个乡(镇)或村看作一个图的顶点,各乡 镇、村之间的公路看作此图对应顶点间的边,各条 公路的长度(或行驶时间)看作对应边上的权,所 给公路网就转化为加权网络图,问题就转化图论中 一类称之为旅行售货员问题,即在给定的加权网络 图中寻找从给定点O出发,行遍所有顶点至少一次 再回到点O,使得总权(路程或时间)最小.

本题是旅行售货员问题的延伸-多旅行售货员问题. 本题所求的分组巡视的最佳路线,也就是m条 经过同一点并覆盖所有其他顶点又使边权之和达到 最小的闭链(闭迹). 如第一问是三个旅行售货员问题,第二问是四 个旅行售货员问题. 众所周知,旅行售货员问题属于NP完全问题, 即求解没有多项式时间算法. 显然本问题更应属于NP完全问题. 有鉴于此, 一定要针对问题的实际特点寻找简便方法,想找到
解决此类问题的一般方法是不现实的,对于规模较大 的问题可使用近似算法来求得近似最优解.

旅行售货员问题
定义设G=(V,E)是连通无向图,包含图G的每个 顶点的路称为G的哈密尔顿路(Hamilton路或H路). 包含图G的每个顶点的圈,称为G的哈密尔顿圈 (或Hamilton圈或H圈). 含Hamilton圈的图称为哈密尔顿图(或Hamilton 图或H图).

旅行售货员问题或货郎担问题.
一个旅行售货员想去访问若干城镇,然后回 到出发地.给定各城镇之间的距离后,应怎样计划 他的旅行路线,使他能对每个城镇恰好经过一次 而总距离最小? 它可归结为这样的图论问题:在一个赋权完 全图中,找出一个最小权的H圈,称这种圈为最优圈.

但这个问题是NP-hard问题,即不存在多项式 时间算法.也就是说,对于大型网络(赋权图),目前还 没有一个求解旅行售货员问题的有效算法,因此 只能找一种求出相当好(不一定最优)的解.

一个可行的办法 :
是先求一个H圈,然后适当 修改,以得到具有较小权的另 一个H圈.

定义 若对于某一对i和j,有 则圈Cij将是圈C的一个改进. 二边逐次修正法: 在接连进行一系列修改之后,最后得一个圈,不能 再用此方法改进了,这个最后的圈可能不是最优的, 但是它是比较好的,为了得到更高的精度,这个

程序可以重复几次,每次都以不同的圈开始. 这种 方法叫做二边逐次修正法.

例对下图16的K6,用二边逐次修正法求 较优H圈.

较优H圈: C3 ? v1v4v5v6v2v3v1 其权为W(C3)=192

分析: 找出的这个解的好坏可用最优H圈的权 的下界与其比较而得出.即利用最小生成树可得最 优H圈的一个下界,方法如下: 设C是G的一个最优H圈,则对G的任一顶点v, C-v是G-v的路,也G-v是的生成树.如果T是G-v的 最小生成树,且e1是e2与v关联的边中权最小的两条 边,则w(T)+w(e1)+w(e2)将是w(C)的一个下界. 取v=v3,得G-v3的一 最小生成树(实线),其 权w(T)=122,与v3关联 的权最小的两条边为 v1v3和v2v3,故w(C) ? w(T)+w(v1v3)+w(v2v3) =178.故最优H圈的权 应满足178 ? w(C)? 192.

6. 最佳灾情巡视路线的模型的建 立与求解

问题转化为在 给定的加权网 络图中寻找从 给定点O出发, 行遍所有顶点 至少一次再回 回到点O ,使得 总权(路程或时 时间)最小,即 最佳旅行售货 员问题.

因二边逐次修正法的结果与初始圈有关,故本算法 最佳旅行售货员问题是NP—完全问题,采用一种 第2),3),4)步分别用三种方法产生初始圈,以保 近似算法求其一个近似最优解,来代替最优解. 证能得到较优的计算结果. 算法一 求加权图的最佳旅行售货员回路近似算法: 1) 用图论软件包求出G中任意两个顶点间的最短路, 构造出完全图 G? ? (V , E?), ?( x, y ) ? E?, ? ( x, y )

? min dG ( x, y ); 2) 输入图 G? 的一个初始H圈;

3) 用对角线完全算法(见[3])产生一个初始圈; 4) 随机搜索出 G? 中若干个H圈,例如2000个; 5) 对第2),3),4)步所得的每个H圈,用二边逐次 修正法进行优化,得到近似最优H圈; 6) 在第5)步求出的所有H圈中,找出权最小的一个, 此即要找的最优H圈的近似解.

问题一 若分为三组巡视,设计总路程最短且各 组尽可能均衡的巡视路线. 此问题是多个售货员的最佳旅行售货员问题.

4)

此问题包含两方面:a)对顶点分组, b)在每组中 求(单个售货员)最佳旅行售货员回路. 因单个售货员的最佳旅行售货员回路问题不存 故多 也不 存在多项式时间内的精确算法.

而图中节点数较多,为53个,我们只能去寻求 一种较合理的划分准则,对图1进行粗步划分后,求 出各部分的近似最佳旅行售货员回路的权,再进一

进一步进行调整,使得各部分满足均衡性条件3).
从O点出发去其它点,要使路程较小应尽量走 O点到该点的最短路. 故用软件包求出O点到其余顶点的最短路. 这些最短路构成一棵O为树根的树. 将从O点出发的树枝称为干枝.

由上述分组准则,我们找到两种分组形式如下: 准则1 尽量使同一干枝上及其分枝上的点分在同一组. 在分组时应遵从准则: 从O点出发到其它点共有6条干枝,它们的名称 分组1:(⑥,①),(②,③),(⑤,④) 准则2 应将相邻的干枝上的点分在同一组; 分别为①,②,③,④,⑤,⑥. 分组2:(①,②),(③,④),(⑤,⑥) 准则3 尽量将长的干枝与短的干枝分在同一组.

分组1极不均衡,故考虑分组2.

分组2:(①,②),(③,④),(⑤,⑥) 对分组2中每组顶点的生成子图,用算法一求出 近似最优解及相应的巡视路线. 在每个子图所构造的完全图中,取一个尽量包含 上图中树上的边的H圈作为其第2)步输入的初始圈.

分组2的近似解
小组 名称 I II III O—P—28—27—26—N—24—23—22—17—16—I—15— I—18—K—21—20—25—M—O O—2—5—6—L—19—J—11—G—13—14—H—12—F— 10—F—9—E—7—E— 8—4—D—3—C—O O—R—29—Q—30—32—31—33—35—34—A—B—1—O 路 线 总路线 长度 191.1 241.9 125.5 558.5 路线的 总长度

因为该分组的均衡度

.

所以此分法的均衡性很差. 为改善均衡性,将第Ⅱ组中的顶点C,2,3,D,4 分给第Ⅲ组(顶点2为这两组的公共点),重新分 分组后的近似最优解见表2.

表2 编号 I II III 路 线

(单位:公里) 路线 长度 191.1 路线总 长 度

O—P—28—27—26—N—24—23—22—17—16—I— 15—I—18—K—21—20—25—M—O O—2—5—6—7—E—8—E—9—F—10—F—12—H —14—13—G—11—J—19—L—6—5—2—O O—R—29—Q—30—32—31—33—35—34—A—1— B—C—3—D—4—D—3—2—O

216.4 192.3

599.8

因该分组的均衡度

所以这种分法的均衡性较好.

问题二 当巡视人员在各乡(镇)、村的停留
停留时间一定,汽车的行驶速度一定,要在24小时内

完成巡视,至少要分几组及最佳旅行的巡视路线.

?

由于T=2小时,t=1小时,V=35公里/小时,需访问 的乡镇共有17个,村共有35个. 计算出在乡(镇)及 村的总停留时间为17 ? 2+35=69小时,要在24小时 内完成巡回,若不考虑行走时间,有: 69/i<24(i为 分的组数). 得i最小为4,故至少要分4组.

由于该网络的乡(镇)、村分布较为均匀,故有可 能找出停留时间尽量均衡的分组,当分4组时各组停 停留时间大约为69/4=17.25小时,则每组分配在路 路途上的时间大约为24-17.25=6.75小时.而前面讨 论过,分三组时有个总路程599.8公里的巡视路线, 分4组时的总路程不会比599.8公里大太多,不妨以 599.8公里来计算.路上约用599.8/35=17小时,若平 均分配给4个组,每个组约需17/4=4.25小时<6.75小 小时,故分成4组是可能办到的.

现在尝试将顶点分为4组.分组的原则:除遵从 前面准则1、2、3外,还应遵从以下准则: 准则4 尽量使各组的停留时间相等. 用上述原则在下图上将图分为4组,同时计算 各组的停留时间,然后用算法一算出各组的近似最 最佳旅行售货员巡回,得出路线长度及行走时间, 从而得出完成巡视的近似最佳时间. 用算法一计 计算时,初始圈的输入与分三组时同样处理.

这4组的近似最优解见表3.

表3 组名 I II III IV 路 线

(路程单位:公里;时间单位:小时) 路 线 总长度 195.8 199.2 159.1 166 停留 时间 17 16 18 18 行走 时间 5.59 5.69 4.54 4.74 完成巡视 的总时间 22.59 21.69 22.54 22.74

O—2—5—6—7—E—8—E—11—G—12—H—12 —F—10—F—9—E—7—6—5—2—O O—R—29—Q—30—Q—28—27—26—N—24—23 —22—17—16—17—K—22—23—N—26—P—O O—M—25—20—21—K—18—I—15—14—13—J —19—L—6—M—O O—R—A—33—31—32—35—34—B—1—C—3 — D—4—D—3—2—O

表3 组名 I II III IV 路 线

(路程单位:公里;时间单位:小时) 路 线 停留 时间 17 16 18 18 行走 时间 5.59 5.69 4.54 4.74 完成巡视 的总时间 22.59 21.69 22.54 22.74 总长度 195.8 199.2 159.1 166

O—2—5—6—7—E—8—E—11—G—12—H—12 —F—10—F—9—E—7—6—5—2—O O—R—29—Q—30—Q—28—27—26—N—24—23 —22—17—16—17—K—22—23—N—26—P—O O—M—25—20—21—K—18—I—15—14—13—J —19—L—6—M—O O—R—A—33—31—32—35—34—B—1—C—3 — D—4—D—3—2—O

表3符号说明:加有底纹的表示前面经过并停留过, 此次只经过不停留;加框的表示此点只经过不停留. 该分组实际均衡度 4.62%

可看出,表3分组的均衡度很好,且完全满足24 小时完成巡视的要求.

最小费用流
? 最小费用流算法

规划形式 算法步骤 算例 算法复杂性

问 题

线性规划形式

对偶规划

算法步骤

算例

计算的迭代过程(1)
a

1,2,0

3,4,0
1,2,0
t

(?, ?)
s

a

s

t

3,1,0
b

1,2,0

b

a

(?, ?)
t s

a

(+s,2)
t

s

b

b

a

a
s t s b

(+s,2)
t

(?, ?)
b

(+a,2)

计算的迭代过程(2)
a a

(?, ?)
s t s t

b

(+s,2)

b

1,2,2
s

a

3,4,0
t

(+a,2)
s

a

(+b,2)
t

1,2,2
b

3,1,0

1,2,2

b

a a s t

(-b,1)
t

(?, ?)
s

b b

(+s,1)

计算的迭代过程(3)
(-b,1)
a

(?, ?)
t

a

s

s

t

b

(+a,1)
b

(+s,1)

a

s

t

b

算法复杂性

工程项目管理中的关键路径及其算法 定理 若有向图G中不存在有向回路,则可以 将G 的结点重新编号为u1, u2, …, un,使得对任意 的边ui uj∈E(G),都有i< j . 各工序最早启动时间算法步骤: ① 根据定理对结点重新编号为u1, u2, …, un . ② 赋初值 ?(u1)= 0. ③ 依次更新 ?(uj ),j = 2, 3, … , n . ?(uj )= max{?(ui )+ ?(ui ,uj )|uiuj∈E(G)}. ④ 结束. 其中?(uj )表示工序 uj 最早启动时间,而?(un)即 ?(vn)是整个工程完工所需的最短时间.

B 6

D 2 2

2
A 关键路径?

2 2

F H 3 2

2

3

4

4

8 I C E 4 G ?(A)=0, 6 8 ?(B)=?(C)=2, K M 8 ?(D)=8, L 3 ?(E)=max{2+3,8+2}=10,J ?(F)=?(G)=?(H)=?(D)+2=10, ?(J)=?(G)+8=18, ?(I)=max{?(G)+8,?(H)+4}=18, ?(L)=?(J)+3=21, ?(K)=max{?(E)+4,?(H)+4}=14, ?(M)=?(K)+8=22, ?(N)=max{?(F)+3,?(I)+2,?(L)+5,?(M)+6}=28.

此例不 必重新 N 编号, 只要按 字母顺 5 序即可.

通过以上计算表明: 这项工程至少需要28天才能完成. 关键路径(最长路径): A→B→D→E→K→M→N A→B→D→H→K→M→N 工序A,B,D,E,H,K,M不能延误,否则将影响工 程的完成. 但是对于不在关键路径上的工序, 是否允许 延误?如果允许, 最多能够延误多长时间呢? 各工序允许延误时间t(uj )等于各工序最晚启 动时间?(uj )减去各工序最早启动时间?(uj ). 即 t(uj )=?(uj )-?(uj ).

最晚启动时间算法步骤(已知结点重新编号): ① 赋初值 ?(un )=?(un). ② 更新 ?(uj ),j = n - 1, n - 2, … , 1.

?(uj )= min{?(ui )- ?(ui ,uj )|uiuj∈E(G)}.
③ 结束.

顺便提一句,根据工序uj允许延误时间t(uj )是 否为0,可判断该工序是否在关键路径上.

B 6

D 2

2
A 2

2 2

F H 3

3 ?(N)=28, 8 I ?(M)=28-6=22, C E 4 G 5 6 8 ?(L)=28-5=23, K ?(K)=?(M)-8=14, M 8 L 3 ?(J)=?(L)-3=20,?(I)=28-2=26, J ?(H)=min{?(K)-4,?(I)-4}=10, ?(F)=28-3=25, ?(G)=min{?(J)-8,?(I)-8}=12, ?(E)=?(K)-4=10, ?(D)=min{?(E)-2,?(F)-2,?(G)-2,?(H)-2}=8, ?(C)=?(E)-3=7,?(B)=?(D)-6=2,?(A)=0.

2

4

4

2

N

各工序允许延误时间如下:

t(A)=t(B)=t(D)=t(E)=t(H)=t(K)=t(M)=0, t(C)=5,t(F)=15,t(G)=2,t(I)=8,t(J)=2, t(L)=2.

PERT图 在PERT(Programme evaluation and review technique)图中, 采用有向边表示工序, 其权值表 示该工序所需时间. 如果工序ei完成后ej才能开始, 则令vk 是ei的终点, ej 的始点. 根据这种约定, 前例的PERT图如下: 些 D F 算 法对 H 与于 B G I A G D H L M 图 J C 类图 似 K 一 E

PERT , PT .

PT图要比PERT图好一些. PT图的结点数基 本上是固定的,这是最重要的一点,容易编程计算. 另外PT图比PERT图更加灵活,它能适应一些 额外的约束. 例如下图中 bj ? (i )/2 ? (i ) + t vi vj vi vj vj v0 ⑴ ⑵ ⑶ ⑴ 表示工序vi完成一半之后vj就可以开始.

⑵ 表示工序vi完成后经过t 时刻vj才开始.
⑶ 表示在时间bj 之后工序vj才能开始,其中v0 表示虚拟结点.


更多相关文档:

4.图论(组合优化)实验

搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS 百度文库 教育专区 高等教育 ...图论与网络优化 讲稿(4)... 暂无评价 96页 免费喜欢此文档的还喜欢 ...

PPT高级应用4

PPT高级应用4_其它技巧_PPT制作技巧_实用文档。优质 PPT 使用制作指南(四)实例...添加企业的固定信息 为了让企业文化讲稿具有明确的企业标志, 可以在演示文稿中...

图论总结(超强大)

搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS ...4/33 [ADN.cn][library]summary 图论总结 2013-...[3]谢金星,清华大学数学科学系<<网络优化>>讲义 ...

四个重在党课讲稿

党课讲稿 14页 免费 党课讲稿 4页 免费 党课讲稿 4页 2财富值 党课讲稿(最新...网络办学、远程教育等方式,促进干部教 育培训资源的优化配置;要采取“走出去”...

新视野大学英语unit 4 讲稿

搜试试 3 帮助 全部 DOC PPT TXT PDF XLS 百度文库 教育专区 外语学习 英语...新视野大学英语unit 4 讲稿_英语学习_外语学习_教育专区。Leading in Questions ...

心理讲稿4

搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS ...心理讲稿4_教育学_高等教育_教育专区。心灵鸡汤全集...优化爱——定心——回归身体,并交待了自爱、定心...

第4版讲稿:第二章 选题

搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS ...第4讲稿:第二章 选题_院校资料_高等教育_教育专区...能不能进行优化?如何进行优化? 【例2-5】5种疼痛...

网络拓扑讲稿

网络拓扑讲稿 暂无评价|0人阅读|0次下载|举报文档1...拓扑学是几何学的一个分支,它是从图论演变过来的。...4、树型:树型拓扑结构是从总线型拓扑演变而来的,...

第四章网络计划技术

搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS ...(4)可以利用计算机进行管理和优化; 2、缺点: 对于...网络计 划方法的理论属于“图论” 。 早在 2000 ...

第4讲定语从句的讲稿

搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS 百度文库 专题推荐 北师大二附...第​4​讲​定​语​从​句​的​讲​稿 暂无评价|0人阅读|...
更多相关标签:
图论与网络最优化算法 | 图论与网络优化 | 图论与组合优化 | 图论与组合最优化 | 网络优化ppt | 图论ppt | 离散数学图论ppt | 北邮 图论及其应用ppt |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com