江西财经大学：《运筹学》课程教学资源（PPT课件）第六章 图与网路分析（2/2）

6.4.5以最短路为基础汇总网路上的流 ① 电路交换网 传输网 4 ④⑤ 在电路网中每两点之间都有中继电路群需求,但并不是任 两点都有物理传输链路 根据两点间最短传输路径将该两点间的电路需求量加载到 这条传输路径上去:设a25=10是节点2和5之间的电路需 求,节点2和5之间的最短传输路径为2-1-3-5,则加载过 程为:T2=T21+10,T3=T13+10,735=73+10;T是传输链路 ij上加载的电路数;当所有点间电路都加载完则算法结束

6.4.5 以最短路为基础汇总网路上的流 1 2 3 4 5 电路交换网 1 2 3 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欧拉回路和中国邮递员问题 中国邮递员问题( Chinese postman problem,CPP)是由我国 管梅谷教授于1962年首先提出并发表的 问题是从邮局出发,走遍邮区的所有街道至少一次再回到 邮局,走什么路由才能使总的路程最短? 如果街区图是一个偶图,根据定理3,一定有欧拉回路 CPP问题也就迎刃而解了 若街区图不是偶图,则必然有一些街道要被重复走过才能 回到原出发点 显然要在奇次点间加重复边 如何使所加的边长度最少 归结为求奇次点间的最小 E 匹配( minimum weighted mtch)-由 emmons给出 多项式算法(1965) B

6.5 欧拉回路和中国邮递员问题 • 中国邮递员问题(Chinese Postman Problem, CPP)是由我国 管梅谷教授于1962年首先提出并发表的 • 问题是从邮局出发，走遍邮区的所有街道至少一次再回到 邮局，走什么路由才能使总的路程最短？ • 如果街区图是一个偶图，根据定理 3，一定有欧拉回路， CPP 问题也就迎刃而解了 • 若街区图不是偶图，则必然有一些街道要被重复走过才能 回到原出发点 • 显然要在奇次点间加重复边 • 如何使所加的边长度最少 • 归结为求奇次点间的最小 匹配( minimum weighted match) — 由Edmons 给出 多项式算法(1965) A B C D

解中国邮递员问题的步骤 0、将图中的所有悬挂点依次摘去 1、求所有奇次点间的最短距离和最短路径 2、根据奇次点间的最短距离求最小完全匹配 3、根据最小完全匹配和最短路径添加重复边 将悬挂点逐一恢复,并加重复边 5、根据得到的偶图,给出欧拉回路的若干种走法 ③2⑥4⑨ ①6④4⑦2@①

解中国邮递员问题的步骤 0、将图中的所有悬挂点依次摘去 1、求所有奇次点间的最短距离和最短路径 2、根据奇次点间的最短距离求最小完全匹配 3、根据最小完全匹配和最短路径添加重复边 4、将悬挂点逐一恢复，并加重复边 5、根据得到的偶图，给出欧拉回路的若干种走法 1 3 2 4 5 9 8 7 6 0 5 5 4 3 4 4 2 4 6 6 2 1 3 2 4 5 9 8 7 6 5 5 4 3 4 4 2 4 6 6

解中国邮递员问题的步骤 2468 468 0107102 535 2468 07 55,7 0 870 468 5,9 最短距离矩阵 转接矩阵 ③264⑨添③6 3 加重 ⑤48复 ④8 找出所有基本 边 回 ①6447,0①40路

解中国邮递员问题的步骤 2 4 6 8 2 - 5 3 5 4 - 5 5,7 6 - 5,9 8 - 转接矩阵 2 4 6 8 2 0 1 0 7 1 0 4 0 7 8 6 0 7 8 0 最短距离矩阵 1 5 9 5 5 4 3 4 4 2 4 6 6 2 1 2 4 5 6 9 0 8 4 7 6 2 3 0 3 8 7 添 加 重 复 边 找 出 所 有 基 本 回 路

6.6哈密尔顿回路及旅行推销员问题 6.6,1哈密尔顿回路( Hamiltonian circuil) 连通图G(V,E中的回路称为哈密尔顿回路,若该回路包括图中 所有的点。显然哈密尔顿回路有且只有n条边,着n 连通图具有哈密尔顿回路的充分必要条件是什么?这个问题是 由爱尔兰数学家哈密尔顿1859年提出的,但至今仍未解决 欧拉回路是对边进行访问的问题,哈密尔顿回路是对点进行访 问的问题 ·搜索哈密尔顿回路的难度是NP- complete 任两点间都有边的图称为完全图(或全连接图) 完全图中有多少个不同的哈密尔顿回路?(m-1)!2 完全图中有多少个边不相交的哈密尔顿回路?(m-1)/2 最小哈密尔顿回路问题(NP- complete) 哈密尔顿路径:包含图中所有点的路径 为什么说找两点间的最长路是非常困难的问题?

6.6 哈密尔顿回路及旅行推销员问题 6.6.1 哈密尔顿回路( Hamiltonian circuit) • 连通图G(V,E)中的回路称为哈密尔顿回路，若该回路包括图中 所有的点。显然哈密尔顿回路有且只有 n 条边，若|V|=n • 连通图具有哈密尔顿回路的充分必要条件是什么？这个问题是 由爱尔兰数学家哈密尔顿1859年提出的，但至今仍未解决 • 欧拉回路是对边进行访问的问题，哈密尔顿回路是对点进行访 问的问题 • 搜索哈密尔顿回路的难度是 NP-complete • 任两点间都有边的图称为完全图(或全连接图) • 完全图中有多少个不同的哈密尔顿回路？ • 完全图中有多少个边不相交的哈密尔顿回路？ • 最小哈密尔顿回路问题 (NP-complete) • 哈密尔顿路径：包含图中所有点的路径 • 为什么说找两点间的最长路是非常困难的问题？ (n−1)!/2 (n−1)/2

662旅行推销员问题( Traveling salesman problen) 旅行推销员问题(TSP):设v,v2,…,Vn为n个已知城市,城市 之间的旅程也是已知的,要求推销员从v出发,走遍所有城 市一次且仅一次又回到出发点,并使总旅程最短 ·这种不允许点重复的旅行推销员问题就是最小哈密尔顿回路 问题 一般旅行推销员问题(GTSP):允许点重复的TSP ·当网路边权满足三角不等式时,一般旅行推销员问题就等价 于最小哈密尔顿回路问题 当网路边权不满足三角不等式时,只要用两点间最短路的距 离代替原来的边权,就可以满足三角不等式,在此基础上求 最小哈密尔顿回路 典型的应用: 乡邮员的投递路线 邮递员开邮箱取信的路线问题 ·邮车到各支局的转趟问题

6.6.2 旅行推销员问题(Traveling Salesman Problem) • 旅行推销员问题(TSP)：设v1 , v2 , ...,vn 为 n 个已知城市，城市 之间的旅程也是已知的，要求推销员从 v1出发，走遍所有城 市一次且仅一次又回到出发点，并使总旅程最短 • 这种不允许点重复的旅行推销员问题就是最小哈密尔顿回路 问题 • 一般旅行推销员问题(GTSP)：允许点重复的TSP • 当网路边权满足三角不等式时，一般旅行推销员问题就等价 于最小哈密尔顿回路问题 • 当网路边权不满足三角不等式时，只要用两点间最短路的距 离代替原来的边权，就可以满足三角不等式，在此基础上求 最小哈密尔顿回路 典型的应用： • 乡邮员的投递路线 • 邮递员开邮箱取信的路线问题 • 邮车到各支局的转趟问题

TSP的启发式算法( Heuristic algorithm) 穷举法:指数算法 分支定界法:隐枚举法 二交换法(mwo- option,Lin' algorithm) 哈密尔顿回路可以用点的序列表示 从任一个哈密尔顿回路(即任何一个序列出发 按照一定顺序试图交换相邻两个点的顺序,若路程减少则完 成交换,继续下一个交换;若没有改善,则不进行本次交换 尝试下一个交换;若所有的相临交换都试过而不能改善,则 算法结束,得到一个局部最优点 模拟退火( Simulated annealing) 随机地采用二交换法 当交换后没有使目标函数改善,也可能以瓌尔兹曼分布概率 被接受,但这种概率是随模拟的温度下降而减少的 发挥了计算机的优点,尽量减少陷入局部极值点 模拟物理机制

TSP 的启发式算法(Heuristic algorithm) • 穷举法：指数算法 • 分支定界法：隐枚举法 • 二交换法 (two-option, Lin’s algorithm) – 哈密尔顿回路可以用点的序列表示 – 从任一个哈密尔顿回路(即任何一个序列)出发 – 按照一定顺序试图交换相邻两个点的顺序，若路程减少则完 成交换，继续下一个交换；若没有改善，则不进行本次交换， 尝试下一个交换；若所有的相临交换都试过而不能改善，则 算法结束，得到一个局部最优点 • 模拟退火 (Simulated Annealing) – 随机地采用二交换法 – 当交换后没有使目标函数改善，也可能以玻尔兹曼分布概率 被接受，但这种概率是随模拟的温度下降而减少的 – 发挥了计算机的优点，尽量减少陷入局部极值点 – 模拟物理机制

二交换法举例 23 23 ① 3 3 10 6 6 初始解:1-2-3-4-5 →1-3-2-4-5 3 3 10 10 ⑤。④ 1-3-2-4-5→1-3-4-2-5 1-3-4-25→1-3-45-2 →5-3-4-2-1×→3-1-4-2-5×

二交换法举例 2 3 5 4 1 11 23 2 6 10 1 3 1 17 8 2 5 4 11 23 2 6 10 1 1 1 3 初始解：1-2-3-4-5 → 1-3-2-4-5 1 23 1 2 6 10 3 1 2 3 5 4 1-3-2-4-5 → 1-3-4-2-5 2 3 5 4 1 1 2 10 3 1 1-3-4-2-5 → 1-3-4-5-2  → 5-3-4-2-1  → 3-1-4-2-5 

算法复杂度 Prim算法 i=1n-1次比较,最多n-1次赋值 i=22(n-2)次比较,最多2n-2)次赋值 i=kk(n-k)次比较,最多k(n-k)次赋值 ∑h(n-b)=2zH(n-1) =1 6 (n-1)nm-123"(n-1 · Dijkstra算法 i=1n-1次临时标记,永久标记n-1次比较和赋值 i=2n-2次临时标记,永久标记n-2次比较和赋值 i=kn-k次临时标记,永久标记n-k次比较和赋值 ∑5(n-k)=25n(n-1)

算法复杂度 • Prim算法 – i=1 n − 1 次比较，最多 n − 1 次赋值 – i=2 2(n − 2) 次比较，最多 2(n − 2) 次赋值 – i=k k(n − k) 次比较，最多 k(n − k) 次赋值 ( 1) 3 1 ( 1) (2 1) 6 2 2 ( 1) 2 ( ) 2 2 1 1 − − − = − −  − = − = n n n n n n n k n k n n k • Dijkstra算法 – i=1 n − 1 次临时标记，永久标记 n − 1 次比较和赋值 – i=2 n − 2 次临时标记，永久标记 n − 2 次比较和赋值 – i=k n − k 次临时标记，永久标记 n − k 次比较和赋值 5( ) 2.5 ( 1) 1 1  − = − − = n k n n n k

Prim算法的改进 增加一个辅助记录型数组,用以记录当前中眢节点到V的最小边, minedgeli.cost记录该边的权值, minedgei vex记录该边v中的 顶点。若 minedgeli. cost0)and (minedgelj] cost<mi) then begin k:j; mi: =minedgeljl cost end minedge k. cost:=- minedge k. cost;我找到k,将k加入集合吟 forj: =2 to n do if (w(k,j <minedge[j]. cost) then begin minedgelj. cost: =wk,; minedgeljlvex: =k; end end;{该算法复杂度约为5n(-1)}

Prim算法的改进 增加一个辅助记录型数组，用以记录当前V 中各节点到 V 的最小边， minedge[i].cost 记录该边的权值，minedge[i].vex 记录该边 V 中的 顶点。若 minedge[i].cost0) 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) }