6.4.5 以最短路为基础汇总网路上的流
1
32
4 5
电路交换网
1
32
4 5
传输网
? 在电路网中每两点之间都有中继电路群需求，但并不是任
两点都有物理传输链路
? 根据两点间最短传输路径将该两点间的电路需求量加载到
这条传输路径上去：设 a25=10 是节点 2 和 5 之间的电路需
求，节点 2 和 5 之间的最短传输路径为 2?1?3?5，则加载过
程为, T21=T21+10,T13=T13+10,T35=T35+10； Tij 是传输链路
i?j 上加载的电路数；当所有点间电路都加载完则算法结束
6.5 欧拉回路和中国邮递员问题
? 中国邮递员问题 (Chinese Postman Problem,CPP)是由我国
管梅谷教授于 1962年首先提出并发表的
? 问题是从邮局出发，走遍邮区的所有街道至少一次再回到
邮局，走什么路由才能使总的路程最短？
? 如果街区图是一个偶图，根据定理 3，一定有欧拉回路，
CPP 问题也就迎刃而解了
? 若街区图不是偶图，则必然有一些街道要被重复走过才能
回到原出发点
? 显然要在奇次点间加重复边
? 如何使所加的边长度最少
? 归结为求奇次点间的最小
匹配 ( minimum weighted
match) — 由 Edmons 给出
多项式算法 (1965)
A
B
C D
解中国邮递员问题的步骤
0、将图中的所有悬挂点依次摘去
1、求所有奇次点间的最短距离和最短路径
2、根据奇次点间的最短距离求最小完全匹配
3、根据最小完全匹配和最短路径添加重复边
4、将悬挂点逐一恢复，并加重复边
5、根据得到的偶图，给出欧拉回路的若干种走法
1
3
2
4
5
9
8
7
6
0
5
5 4
3
4
4
42
6
6 2
1
3
2
4
5
9
8
7
6
5
5 4
3
4
4
42
6
6
解中国邮递员问题的步骤
2 4 6 8
2 - 5 3 5
4 - 5 5,7
6 - 5,9
8 -
转接矩阵
2 4 6 8
2 0 10 7 10
4 0 7 8
6 0 7
8 0
最短距离矩阵
1
5
9
5
5 4
3
4
4
42
6
6
2
1
2
4
5
96
0
8
74
6
2
3
0
3
8
7
添
加
重
复
边
找
出
所
有
基
本
回
路
6.6 哈密尔顿回路及旅行推销员问题
6.6.1 哈密尔顿回路 ( Hamiltonian circuit)
? 连通图 G(V,E)中的回路称为 哈密尔顿回路,若该回路包括图中
所有的点。显然哈密尔顿回路有且只有 n条边，若 |V|=n
? 连通图具有哈密尔顿回路的充分必要条件是什么？这个问题是
由爱尔兰数学家 哈密尔顿 1859年 提出的，但至今仍未解决
? 欧拉回路是对边进行访问的问题，哈密尔顿回路是对点进行访
问的问题
? 搜索哈密尔顿回路的难度是 NP-complete
? 任两点间都有边的图称为 完全图 (或全连接图 )
? 完全图中有多少个不同的哈密尔顿回路？
? 完全图中有多少个边不相交的哈密尔顿回路？
? 最小哈密尔顿回路问题 (NP-complete)
? 哈密尔顿路径,包含图中所有点的路径
? 为什么说找两点间的最长路是非常困难的问题？
(n?1)!/2
(n?1)/2
6.6.2 旅行推销员问题 (Traveling Salesman Problem)
? 旅行推销员问题 (TSP)：设 v1,v2,...,vn 为 n 个已知城市，城市
之间的旅程也是已知的，要求推销员从 v1出发，走遍所有城
市一次且仅一次又回到出发点，并使总旅程最短
? 这种不允许点重复的旅行推销员问题就是最小哈密尔顿回路
问题
? 一般旅行推销员问题 (GTSP)：允许点重复的 TSP
? 当网路边权满足三角不等式时，一般旅行推销员问题就等价
于最小哈密尔顿回路问题
? 当网路边权不满足三角不等式时，只要用两点间最短路的距
离代替原来的边权，就可以满足三角不等式，在此基础上求
最小哈密尔顿回路
典型的应用,
? 乡邮员的投递路线
? 邮递员开邮箱取信的路线问题
? 邮车到各支局的转趟问题
TSP 的启发式算法 (Heuristic algorithm)
? 穷举法,指数算法
? 分支定界法,隐枚举法
? 二交换法 (two-option,Lin’s algorithm)
– 哈密尔顿回路可以用点的序列表示
– 从任一个哈密尔顿回路 (即任何一个序列 )出发
– 按照一定顺序试图交换相邻两个点的顺序，若路程减少则完
成交换，继续下一个交换；若没有改善，则不进行本次交换，
尝试下一个交换；若所有的相临交换都试过而不能改善，则
算法结束，得到一个局部最优点
? 模拟退火 (Simulated Annealing)
– 随机地采用二交换法
– 当交换后没有使目标函数改善，也可能以玻尔兹曼分布概率
被接受，但这种概率是随模拟的温度下降而减少的
– 发挥了计算机的优点，尽量减少陷入局部极值点
– 模拟物理机制
二交换法举例
2
3
45
1
2311
2
6
10
1
3 1
817
2
45
2311
2
6
10
1
1
31
初始解,1-2-3-4-5
? 1-3-2-4-5
1
23
1
2
6
10
13
2
3
45
1-3-2-4-5 ? 1-3-4-2-5
2
3
45
1
1
2 10
13
1-3-4-2-5 ? 1-3-4-5-2 ?
? 5-3-4-2-1 ? ? 3-1-4-2-5 ?
算法复杂度
? Prim算法
– i=1 n ? 1 次比较，最多 n ? 1 次赋值
– i=2 2(n ? 2) 次比较，最多 2(n ? 2) 次赋值
– i=k k(n ? k) 次比较，最多 k(n ? k) 次赋值
)1(31)12()1(622 )1(2)(2 2
1
1
?????????
?
?
nnnnnnnnknk
n
k
? Dijkstra算法
– i=1 n ? 1 次临时标记，永久标记 n ? 1 次比较和赋值
– i=2 n ? 2 次临时标记，永久标记 n ? 2 次比较和赋值
– i=k n ? k 次临时标记，永久标记 n ? k 次比较和赋值
)(.)( 1525
1
1
????
?
?
nnkn
n
k
Prim算法的改进
增加一个辅助记录型数组，用以记录当前 V 中各节点到 V的最小边，
minedge[i].cost 记录该边的权值,minedge[i].vex 记录该边 V 中的
顶点。若 minedge[i].cost<0 则表明 i 点进入集合 V
for i:=2 to n do begin minedge[i].vex:=1; minedge[i].cost:=w[1,i] end;
for i:=1 to n ? 1 do
begin
mi:=maxint;
for j:=2 to n do if (minedge[j].cost>0) and (minedge[j].cost<mi) then
begin k:=j; mi:=minedge[j].cost end;
minedge[k].cost:= ?minedge[k].cost; {找到 k，将 k 加入集合 V}
for j:=2 to n do if (w[k,j]<minedge[j].cost) then
begin
minedge[j].cost:=w[k,j];
minedge[j].vex:=k;
end;
end; { 该算法复杂度 约为 5n(n-1) }
匹配问题 (Matching Problem)
定义,图中一组边的集合，当图中的每个节点最多只与
该集合中的一条边相关联，则该边集就成为 匹配 。
1,两部图 的匹配问题
? 图中的节点可分为两个集合,X,Y,X 与 Y 之间有边相连，
但 X 内部和 Y 内部无关联边，称为两部图
– 运输问题实际上是两部图的最小费用最大流问题
– 任务分配问题实际上是两部图的最小完全匹配问题
2,非 两部图 的匹配问题
(1) 最大基数匹配 (maximum cardinality matching)
(2) 最大权匹配 (maximum weight matching)
(3) 最小完全匹配 (minimum weight perfect matching)
(4) 最优分数匹配 (optimal fractional matching)
两部图的最小完全匹配 ?? 匈亚利算法
? 任务分配问题的抽象就是两部图的最小完全匹配问题
? 匈亚利算法 (Hungarian method)由 Kuhn教授提出, 它实际
上是主对偶算法的先驱
? 匈亚利算法借助于效率矩阵和两部图来完成运算
? 任务分配问题的 效率矩阵对应的是两部图的边权 {cij},对偶
问题的解对应的是每条边的两个端点 {ai,bj}；对偶约束为
ai,＋ bj ? cij
? 匈亚利算法的实质是通过构造 对偶问题的可行解, 得到一
个 等值边子图, 即所有 ai,＋ bj ＝ cij 的边构成的图；然后在
等值边子图 上求最大基数匹配；当得到原问题的完全匹配,
则算法结束
? 对偶问题的可行解 ? 等值边子图 ? 满足互补松弛定理求
原问题的解 (部分可行解 )? 检验 ? 扩充 等值边子图 ?
最大基数匹配
? 最大基数匹配是基于 交错树的算法
? 敞露点, 根, 交错链, 外点, 内点, 增广链
– 尚未匹配的节点称为 敞露点
– 以敞露点为根, 由非匹配边和匹配边交替构成的链称为
交错链
– 交错链 的根为外点, 其后内点与外点交替；外点是交错
链的生长点
– 以内点结束的交错链称为 增广链, 因为反转该链上各边
的匹配状态可使匹配的边数增加一条
???í?÷????
?ù ???? ???? ??????
??????
匈亚利算法步骤
1 令所有 ai＝ 0
2 在效率矩阵中找每列最小值 qj,令 bj＝ qj,故 ? i,j,满足
ai＋ bj ? cij
3 在满足 ai＋ bj ＝ cij 的边构成的等值子图中求最大基数匹配；
若达到完全匹配则结束, 否则到下一步
4 对敞露点求每列的最小松弛量
sj＝ min i* {ci*j－ ai*－ bj }
5 求最大增广量
S＝ 0.5 ? min j {sj}
7 增广等值子图,
? j,bj ＝ bj ＋ S
? i*(敞露点 ),ai*＝ ai*＋ S； ? i (非敞露点 ),ai＝ ai － S
? 返回到第 3 步
匈亚利算法举例
b
a
1 2 1 2
* 0 3 3 5 3
0 3 ( 2 ) 5 2
0 ( 1 ) 5 1 6
* 0 4 6 4 10
s l a c k 2 1 3 1
nbour 1 1 4 1
S * = 0, 5
*
*
匈亚利算法举例
*
b
a
1, 5 2, 5 1, 5 2, 5
0,5 3 ( 3 ) 5 3
- 0, 5 3 2 5 ( 2 )
- 0, 5 ( 1 ) 5 1 6
* 0, 5 4 6 4 10
s l a c k 2 3 2 7
nbour 4 4 4 4
S * = 1
匈亚利算法举例
b
a
2, 5 3, 5 2, 5 3, 5
- 0, 5 3 ( 3 ) 5 3
- 1, 5 3 2 5 ( 2 )
- 1, 5 1 5 ( 1 ) 6
1, 5 ( 4 ) 6 4 10
s l a c k
nbour
任务分配问题、匹配问题和 TSP的关系
? 三个问题都有一个 n?n 正权值的边权矩阵
? 三个问题的解都可以用代数置换 (permutation)表示
???
?
???
?
???
?
???
?
15423
54321 54321
54321 iiiii
? i1,i2,i3,i4,i5 是 1,2,3,4,5 的任一排列，表示元素位置
的交换
? 轮换，全轮换，对换
? TSP的解必须是一个全轮换
? 任务分配问题的解可以是任一个置换
? 匹配的解必须是 n/2 个对换
? 任务分配问题是匹配问题的松弛问题
6.7 选址问题
? 使所选地址到最远的服务对象距离尽可能小 —— 中心点
? 使所选地址到各服务对象的总距离最小 —— 中位点
? 有时间限制的多用中心点，如乡邮局
? 总资源约束的多用中位点，如电话交换局
6.7.1 各点之间的距离
? 节点到节点间的最短距离，称为节点 — 节点距离
? 边上某点到节点的最短距离，称为点 — 节点距离
? 节点到某边上最远一点的距离，称为节点 — 边距离
? 边上一点到另一边上最远点的距离，称为点 — 边距离
1 6
2 5
7 3 4
2
1
11
1
3
2
1,边上某点到节点的最短距离
– dij 代表 vi 与 vj 间的最短距离,ars 代表边 (r,s)的边长，
令 h 为边 (r,s)上一点的 百分位, 0? h?1
– 边上对应 h 的一点到 vj 的最短距离为
d[h(r,s),j]=min[h?ars+drj,(1?h)?ars+dsj]
2,节点到某边上最远一点的距离
– 指定节点 j，它到边 (r,s)上对应 h百分位点有两条路，最
远点必使两条路一样长，故有
d[j,(r,s)]=0.5[djr+ djs+ ars]
3,边上指定一点到其他边上最远点的距离
– h 是边 (r,s)上指定的百分位点，另一边为 (u,t)
d[h(r,s),(u,t)]=min[h?ars+d[r,(u,t)],(1?h)?ars+d [s,(u,t)] ]
6.7.2 中心的选择
? 中心：以节点 — 节点距离为基础，大中取小 (max min)
? 一般中心：以节点 — 边距离为基础，大中取小
? 绝对中心：以点 — 节点距离为基础，大中取小
? 一般绝对中心：以点 — 边距离为基础，大中取小
? 左图的中心是 v1；而三个节点都是一般中心
? 类似也有四种中位点：
– 中位点
– 一般中位点
– 绝对中位点
– 一般绝对中位点
3
3
2 1
2
5 4
2
1
4
3
3
2
1
5
2
7
例 6.7.1~6.7.2
m a x m i n ? m i n
0 2 3 4 4 4 ? 13
2 0 1 5 2 5 10 ?
3 1 0 6 3 6 13
4 5 6 0 3 6 18
4 2 3 3 0 4 ? 12
编号 1 2 3 4 5 6
边
( i,j ) ( 1,2 ) ( 1,4 ) ( 2,3 ) ( 2,5 ) ( 3,5 ) ( 4,5 )
边长 2 4 1 2 5 3
max m i n ? m i n
2 4 3 4 6 5, 5 6 2 4, 5
2 5, 5 1 2 4 5 5, 5 ? 1 9, 5 ?
3 6, 5 1 3 4 6 6, 5 2 3, 5
5, 5 4 6 5 7 3 7 3 0, 5
4 5, 5 3 2 4 3 5, 5 ? 2 1, 5
中心
一般中心
中位点
一般中位点
1
32
4 5
电路交换网
1
32
4 5
传输网
? 在电路网中每两点之间都有中继电路群需求，但并不是任
两点都有物理传输链路
? 根据两点间最短传输路径将该两点间的电路需求量加载到
这条传输路径上去：设 a25=10 是节点 2 和 5 之间的电路需
求，节点 2 和 5 之间的最短传输路径为 2?1?3?5，则加载过
程为, T21=T21+10,T13=T13+10,T35=T35+10； Tij 是传输链路
i?j 上加载的电路数；当所有点间电路都加载完则算法结束
6.5 欧拉回路和中国邮递员问题
? 中国邮递员问题 (Chinese Postman Problem,CPP)是由我国
管梅谷教授于 1962年首先提出并发表的
? 问题是从邮局出发，走遍邮区的所有街道至少一次再回到
邮局，走什么路由才能使总的路程最短？
? 如果街区图是一个偶图，根据定理 3，一定有欧拉回路，
CPP 问题也就迎刃而解了
? 若街区图不是偶图，则必然有一些街道要被重复走过才能
回到原出发点
? 显然要在奇次点间加重复边
? 如何使所加的边长度最少
? 归结为求奇次点间的最小
匹配 ( minimum weighted
match) — 由 Edmons 给出
多项式算法 (1965)
A
B
C D
解中国邮递员问题的步骤
0、将图中的所有悬挂点依次摘去
1、求所有奇次点间的最短距离和最短路径
2、根据奇次点间的最短距离求最小完全匹配
3、根据最小完全匹配和最短路径添加重复边
4、将悬挂点逐一恢复，并加重复边
5、根据得到的偶图，给出欧拉回路的若干种走法
1
3
2
4
5
9
8
7
6
0
5
5 4
3
4
4
42
6
6 2
1
3
2
4
5
9
8
7
6
5
5 4
3
4
4
42
6
6
解中国邮递员问题的步骤
2 4 6 8
2 - 5 3 5
4 - 5 5,7
6 - 5,9
8 -
转接矩阵
2 4 6 8
2 0 10 7 10
4 0 7 8
6 0 7
8 0
最短距离矩阵
1
5
9
5
5 4
3
4
4
42
6
6
2
1
2
4
5
96
0
8
74
6
2
3
0
3
8
7
添
加
重
复
边
找
出
所
有
基
本
回
路
6.6 哈密尔顿回路及旅行推销员问题
6.6.1 哈密尔顿回路 ( Hamiltonian circuit)
? 连通图 G(V,E)中的回路称为 哈密尔顿回路,若该回路包括图中
所有的点。显然哈密尔顿回路有且只有 n条边，若 |V|=n
? 连通图具有哈密尔顿回路的充分必要条件是什么？这个问题是
由爱尔兰数学家 哈密尔顿 1859年 提出的，但至今仍未解决
? 欧拉回路是对边进行访问的问题，哈密尔顿回路是对点进行访
问的问题
? 搜索哈密尔顿回路的难度是 NP-complete
? 任两点间都有边的图称为 完全图 (或全连接图 )
? 完全图中有多少个不同的哈密尔顿回路？
? 完全图中有多少个边不相交的哈密尔顿回路？
? 最小哈密尔顿回路问题 (NP-complete)
? 哈密尔顿路径,包含图中所有点的路径
? 为什么说找两点间的最长路是非常困难的问题？
(n?1)!/2
(n?1)/2
6.6.2 旅行推销员问题 (Traveling Salesman Problem)
? 旅行推销员问题 (TSP)：设 v1,v2,...,vn 为 n 个已知城市，城市
之间的旅程也是已知的，要求推销员从 v1出发，走遍所有城
市一次且仅一次又回到出发点，并使总旅程最短
? 这种不允许点重复的旅行推销员问题就是最小哈密尔顿回路
问题
? 一般旅行推销员问题 (GTSP)：允许点重复的 TSP
? 当网路边权满足三角不等式时，一般旅行推销员问题就等价
于最小哈密尔顿回路问题
? 当网路边权不满足三角不等式时，只要用两点间最短路的距
离代替原来的边权，就可以满足三角不等式，在此基础上求
最小哈密尔顿回路
典型的应用,
? 乡邮员的投递路线
? 邮递员开邮箱取信的路线问题
? 邮车到各支局的转趟问题
TSP 的启发式算法 (Heuristic algorithm)
? 穷举法,指数算法
? 分支定界法,隐枚举法
? 二交换法 (two-option,Lin’s algorithm)
– 哈密尔顿回路可以用点的序列表示
– 从任一个哈密尔顿回路 (即任何一个序列 )出发
– 按照一定顺序试图交换相邻两个点的顺序，若路程减少则完
成交换，继续下一个交换；若没有改善，则不进行本次交换，
尝试下一个交换；若所有的相临交换都试过而不能改善，则
算法结束，得到一个局部最优点
? 模拟退火 (Simulated Annealing)
– 随机地采用二交换法
– 当交换后没有使目标函数改善，也可能以玻尔兹曼分布概率
被接受，但这种概率是随模拟的温度下降而减少的
– 发挥了计算机的优点，尽量减少陷入局部极值点
– 模拟物理机制
二交换法举例
2
3
45
1
2311
2
6
10
1
3 1
817
2
45
2311
2
6
10
1
1
31
初始解,1-2-3-4-5
? 1-3-2-4-5
1
23
1
2
6
10
13
2
3
45
1-3-2-4-5 ? 1-3-4-2-5
2
3
45
1
1
2 10
13
1-3-4-2-5 ? 1-3-4-5-2 ?
? 5-3-4-2-1 ? ? 3-1-4-2-5 ?
算法复杂度
? Prim算法
– i=1 n ? 1 次比较，最多 n ? 1 次赋值
– i=2 2(n ? 2) 次比较，最多 2(n ? 2) 次赋值
– i=k k(n ? k) 次比较，最多 k(n ? k) 次赋值
)1(31)12()1(622 )1(2)(2 2
1
1
?????????
?
?
nnnnnnnnknk
n
k
? Dijkstra算法
– i=1 n ? 1 次临时标记，永久标记 n ? 1 次比较和赋值
– i=2 n ? 2 次临时标记，永久标记 n ? 2 次比较和赋值
– i=k n ? k 次临时标记，永久标记 n ? k 次比较和赋值
)(.)( 1525
1
1
????
?
?
nnkn
n
k
Prim算法的改进
增加一个辅助记录型数组，用以记录当前 V 中各节点到 V的最小边，
minedge[i].cost 记录该边的权值,minedge[i].vex 记录该边 V 中的
顶点。若 minedge[i].cost<0 则表明 i 点进入集合 V
for i:=2 to n do begin minedge[i].vex:=1; minedge[i].cost:=w[1,i] end;
for i:=1 to n ? 1 do
begin
mi:=maxint;
for j:=2 to n do if (minedge[j].cost>0) and (minedge[j].cost<mi) then
begin k:=j; mi:=minedge[j].cost end;
minedge[k].cost:= ?minedge[k].cost; {找到 k，将 k 加入集合 V}
for j:=2 to n do if (w[k,j]<minedge[j].cost) then
begin
minedge[j].cost:=w[k,j];
minedge[j].vex:=k;
end;
end; { 该算法复杂度 约为 5n(n-1) }
匹配问题 (Matching Problem)
定义,图中一组边的集合，当图中的每个节点最多只与
该集合中的一条边相关联，则该边集就成为 匹配 。
1,两部图 的匹配问题
? 图中的节点可分为两个集合,X,Y,X 与 Y 之间有边相连，
但 X 内部和 Y 内部无关联边，称为两部图
– 运输问题实际上是两部图的最小费用最大流问题
– 任务分配问题实际上是两部图的最小完全匹配问题
2,非 两部图 的匹配问题
(1) 最大基数匹配 (maximum cardinality matching)
(2) 最大权匹配 (maximum weight matching)
(3) 最小完全匹配 (minimum weight perfect matching)
(4) 最优分数匹配 (optimal fractional matching)
两部图的最小完全匹配 ?? 匈亚利算法
? 任务分配问题的抽象就是两部图的最小完全匹配问题
? 匈亚利算法 (Hungarian method)由 Kuhn教授提出, 它实际
上是主对偶算法的先驱
? 匈亚利算法借助于效率矩阵和两部图来完成运算
? 任务分配问题的 效率矩阵对应的是两部图的边权 {cij},对偶
问题的解对应的是每条边的两个端点 {ai,bj}；对偶约束为
ai,＋ bj ? cij
? 匈亚利算法的实质是通过构造 对偶问题的可行解, 得到一
个 等值边子图, 即所有 ai,＋ bj ＝ cij 的边构成的图；然后在
等值边子图 上求最大基数匹配；当得到原问题的完全匹配,
则算法结束
? 对偶问题的可行解 ? 等值边子图 ? 满足互补松弛定理求
原问题的解 (部分可行解 )? 检验 ? 扩充 等值边子图 ?
最大基数匹配
? 最大基数匹配是基于 交错树的算法
? 敞露点, 根, 交错链, 外点, 内点, 增广链
– 尚未匹配的节点称为 敞露点
– 以敞露点为根, 由非匹配边和匹配边交替构成的链称为
交错链
– 交错链 的根为外点, 其后内点与外点交替；外点是交错
链的生长点
– 以内点结束的交错链称为 增广链, 因为反转该链上各边
的匹配状态可使匹配的边数增加一条
???í?÷????
?ù ???? ???? ??????
??????
匈亚利算法步骤
1 令所有 ai＝ 0
2 在效率矩阵中找每列最小值 qj,令 bj＝ qj,故 ? i,j,满足
ai＋ bj ? cij
3 在满足 ai＋ bj ＝ cij 的边构成的等值子图中求最大基数匹配；
若达到完全匹配则结束, 否则到下一步
4 对敞露点求每列的最小松弛量
sj＝ min i* {ci*j－ ai*－ bj }
5 求最大增广量
S＝ 0.5 ? min j {sj}
7 增广等值子图,
? j,bj ＝ bj ＋ S
? i*(敞露点 ),ai*＝ ai*＋ S； ? i (非敞露点 ),ai＝ ai － S
? 返回到第 3 步
匈亚利算法举例
b
a
1 2 1 2
* 0 3 3 5 3
0 3 ( 2 ) 5 2
0 ( 1 ) 5 1 6
* 0 4 6 4 10
s l a c k 2 1 3 1
nbour 1 1 4 1
S * = 0, 5
*
*
匈亚利算法举例
*
b
a
1, 5 2, 5 1, 5 2, 5
0,5 3 ( 3 ) 5 3
- 0, 5 3 2 5 ( 2 )
- 0, 5 ( 1 ) 5 1 6
* 0, 5 4 6 4 10
s l a c k 2 3 2 7
nbour 4 4 4 4
S * = 1
匈亚利算法举例
b
a
2, 5 3, 5 2, 5 3, 5
- 0, 5 3 ( 3 ) 5 3
- 1, 5 3 2 5 ( 2 )
- 1, 5 1 5 ( 1 ) 6
1, 5 ( 4 ) 6 4 10
s l a c k
nbour
任务分配问题、匹配问题和 TSP的关系
? 三个问题都有一个 n?n 正权值的边权矩阵
? 三个问题的解都可以用代数置换 (permutation)表示
???
?
???
?
???
?
???
?
15423
54321 54321
54321 iiiii
? i1,i2,i3,i4,i5 是 1,2,3,4,5 的任一排列，表示元素位置
的交换
? 轮换，全轮换，对换
? TSP的解必须是一个全轮换
? 任务分配问题的解可以是任一个置换
? 匹配的解必须是 n/2 个对换
? 任务分配问题是匹配问题的松弛问题
6.7 选址问题
? 使所选地址到最远的服务对象距离尽可能小 —— 中心点
? 使所选地址到各服务对象的总距离最小 —— 中位点
? 有时间限制的多用中心点，如乡邮局
? 总资源约束的多用中位点，如电话交换局
6.7.1 各点之间的距离
? 节点到节点间的最短距离，称为节点 — 节点距离
? 边上某点到节点的最短距离，称为点 — 节点距离
? 节点到某边上最远一点的距离，称为节点 — 边距离
? 边上一点到另一边上最远点的距离，称为点 — 边距离
1 6
2 5
7 3 4
2
1
11
1
3
2
1,边上某点到节点的最短距离
– dij 代表 vi 与 vj 间的最短距离,ars 代表边 (r,s)的边长，
令 h 为边 (r,s)上一点的 百分位, 0? h?1
– 边上对应 h 的一点到 vj 的最短距离为
d[h(r,s),j]=min[h?ars+drj,(1?h)?ars+dsj]
2,节点到某边上最远一点的距离
– 指定节点 j，它到边 (r,s)上对应 h百分位点有两条路，最
远点必使两条路一样长，故有
d[j,(r,s)]=0.5[djr+ djs+ ars]
3,边上指定一点到其他边上最远点的距离
– h 是边 (r,s)上指定的百分位点，另一边为 (u,t)
d[h(r,s),(u,t)]=min[h?ars+d[r,(u,t)],(1?h)?ars+d [s,(u,t)] ]
6.7.2 中心的选择
? 中心：以节点 — 节点距离为基础，大中取小 (max min)
? 一般中心：以节点 — 边距离为基础，大中取小
? 绝对中心：以点 — 节点距离为基础，大中取小
? 一般绝对中心：以点 — 边距离为基础，大中取小
? 左图的中心是 v1；而三个节点都是一般中心
? 类似也有四种中位点：
– 中位点
– 一般中位点
– 绝对中位点
– 一般绝对中位点
3
3
2 1
2
5 4
2
1
4
3
3
2
1
5
2
7
例 6.7.1~6.7.2
m a x m i n ? m i n
0 2 3 4 4 4 ? 13
2 0 1 5 2 5 10 ?
3 1 0 6 3 6 13
4 5 6 0 3 6 18
4 2 3 3 0 4 ? 12
编号 1 2 3 4 5 6
边
( i,j ) ( 1,2 ) ( 1,4 ) ( 2,3 ) ( 2,5 ) ( 3,5 ) ( 4,5 )
边长 2 4 1 2 5 3
max m i n ? m i n
2 4 3 4 6 5, 5 6 2 4, 5
2 5, 5 1 2 4 5 5, 5 ? 1 9, 5 ?
3 6, 5 1 3 4 6 6, 5 2 3, 5
5, 5 4 6 5 7 3 7 3 0, 5
4 5, 5 3 2 4 3 5, 5 ? 2 1, 5
中心
一般中心
中位点
一般中位点
