运筹学：第六章 图与网路分析2

6.4.5

以最短路为基础汇总网路上的流在电路网中每两点之间都有中继电路群需求，但并不是任两点都有物理传输链路根据两点间最短传输路径将该两点间的电路需求量加载到这条传输路径上去：设a25=10是节点2和5之间的电路需求，节点2和5之间的最短传输路径为2135，则加载过程为:T21=T21+10,T13=T13+10,T35=T35+10；Tij

是传输链路ij

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

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

解中国邮递员问题的步骤6.6哈密尔顿回路及旅行推销员问题

6.6.1哈密尔顿回路(Hamiltoniancircuit)连通图G(V,E)中的回路称为哈密尔顿回路，若该回路包括图中所有的点。显然哈密尔顿回路有且只有n

条边，若|V|=n连通图具有哈密尔顿回路的充分必要条件是什么？这个问题是由爱尔兰数学家哈密尔顿1859年提出的，但至今仍未解决欧拉回路是对边进行访问的问题，哈密尔顿回路是对点进行访问的问题搜索哈密尔顿回路的难度是NP-complete任两点间都有边的图称为完全图(或全连接图)完全图中有多少个不同的哈密尔顿回路？完全图中有多少个边不相交的哈密尔顿回路？最小哈密尔顿回路问题

(NP-complete)哈密尔顿路径：包含图中所有点的路径为什么说找两点间的最长路是非常困难的问题？(n1)!/2(n1)/26.6.2旅行推销员问题(TravelingSalesman

Problem)旅行推销员问题(TSP)：设v1,v2,...,vn

为n

个已知城市，城市之间的旅程也是已知的，要求推销员从v1出发，走遍所有城市一次且仅一次又回到出发点，并使总旅程最短这种不允许点重复的旅行推销员问题就是最小哈密尔顿回路问题一般旅行推销员问题(GTSP)：允许点重复的TSP当网路边权满足三角不等式时，一般旅行推销员问题就等价于最小哈密尔顿回路问题当网路边权不满足三角不等式时，只要用两点间最短路的距离代替原来的边权，就可以满足三角不等式，在此基础上求最小哈密尔顿回路

典型的应用：乡邮员的投递路线邮递员开邮箱取信的路线问题邮车到各支局的转趟问题

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

二交换法举例初始解：1-2-3-4-51-3-2-4-51-3-2-4-51-3-4-2-51-3-4-2-51-3-4-5-25-3-4-2-13-1-4-2-5

算法复杂度(Complexityofalgorithm)算法：一步一步求解问题的步骤及其正规描述。问题：所谓“问题”就是需要给出确切答案的一个提问。这种提问通常包含一些自由变量和若干参数，但它们的值是没有给定的。问题的描述必须给出：(1)所有变量和参数的一般性描述；(2)陈述问题答案(解)必须满足的性质。给问题的所有变量和参数指定具体的值，就得到该问题的一个“实例”。问题的规模：问题的规模可以由问题变量及有关参数的输入长度表示，而这种输入长度又由它的编码方案所决定。编码方案不同会影响一个问题的输入长度，但它们的差异至多是多项式的。例如，在图论中常用节点的数目n作为问题规模的一般表达方式；如果用边的数目表示，最多是n2；如果边权是实数，则问题输入长度为32n2bits。在线性规划问题中，一般用m+n表示问题的规模，其中n为变量个数，m为约束行数，其技术矩阵A

为主要输入，其大小为m×(m+n)

。显然，算法的难度和复杂度与问题规模有关。

算法复杂度(Complexityofalgorithm)算法的特征算法必有开始，表现为初始化，初始解的给定；算法必有结束，表现为必有判定是否停止的步骤；算法一般表现为通用步骤的反复循环，称为迭代(iterative)。通用迭代的基本计算量往往是问题规模的一个函数；算法的迭代步数也是问题规模的函数。算法复杂度算法复杂度的两种根本性的差别关于问题规模的多项式算法：P(n)，如n4,n3,n2–n等；关于问题规模的指数算法：E(n),如2n,n!,nn等；

算法复杂度(Complexityofalgorithm)指数算法

(坏算法)采用穷举法搜索TSP的最优解，其运算时间的估计式为：城市数(n)1015202130解的数量1.81441054.358910106.082310161.216510184.42091030运算时间－69.7s4y84.86y4.351014y多项式算法

(好算法)Prim算法i=1n1次比较，最多n1次赋值i=22(n2)次比较，最多2(n2)次赋值i=k

k(n

k)次比较，最多k(n

k)次赋值Dijkstra算法i=1n1次临时标记，永久标记n1次比较和赋值i=2n2次临时标记，永久标记n2次比较和赋值i=k

n

k

次临时标记，永久标记n

k

次比较和赋值

算法复杂度(Complexityofalgorithm)指数算法

(坏算法)如果一类问题被证明只有指数算法，这类问题就被称为难解的。多项式算法

(好算法)如果一类问题被证明有多项式算法，这类问题就被称为非难解的。NP-完备问题一类问题目前找不到多项式算法，也没有被证明只有指数算法，但它可以由一个已知的NP-完备问题多项式转变过来，它就是NP-完备的。目前只有(隐)枚举法可以保证找到最优解；一般采用启发式的近似算法求次最优解。Prim算法的改进增加一个辅助记录型数组，用以记录当前V

中各节点到V

的最小边，minedge[i].cost记录该边的权值，minedge[i].vex记录该边V

中的顶点。若minedge[i].cost<0则表明i

点进入集合Vfori:=2tondobeginminedge[i].vex:=1;minedge[i].cost:=w[1,i]end;fori:=1ton1dobeginmi:=maxint;forj:=2tondoif(minedge[j].cost>0)and(minedge[j].cost<mi)thenbegink:=j;mi:=minedge[j].costend;minedge[k].cost:=minedge[k].cost;{找到k，将k

加入集合V}forj:=2tondoif(w[k,j]<minedge[j].cost)thenbeginminedge[j].cost:=w[k,j];minedge[j].vex:=k;end;end;{该算法复杂度约为5n(n-1)}

匹配问题(MatchingProblem)定义：图中一组边的集合，当图中的每个节点最多只与该集合中的一条边相关联，则该边集就成为匹配。1、两部图的匹配问题图中的节点可分为两个集合，X,Y，X与Y

之间有边相连，但X

内部和Y

内部无关联边，称为两部图运输问题实际上是两部图的最小费用最大流问题任务分配问题实际上是两部图的最小完全匹配问题2、非两部图的匹配问题(1)最大基数匹配(maximumcardinalitymatching)(2)最大权匹配(maximumweightmatching)(3)最小完全匹配(minimumweightperfectmatching)(4)最优分数匹配(optimalfractionalmatching)两部图的最小完全匹配匈牙利算法任务分配问题的抽象就是两部图的最小完全匹配问题匈亚利算法(Hungarianmethod)由Kuhn教授提出，它实际上是主对偶算法的先驱匈亚利算法借助于效率矩阵和两部图来完成运算任务分配问题的效率矩阵对应的是两部图的边权{cij}，对偶问题的解对应的是每条边的两个端点{ai,bj}；对偶约束为ai＋bjcij匈亚利算法的实质是通过构造对偶问题的可行解，得到一个等值边子图，即所有ai,＋bj＝cij

的边构成的图；然后在等值边子图上求最大基数匹配；当得到原问题的完全匹配，则算法结束对偶问题的可行解等值边子图满足互补松弛定理求原问题的解(部分可行解)检验扩充等值边子图最大基数匹配最大基数匹配是基于交错树(匈牙利树)的算法敞露点、根、交错链、外点、内点、增广链尚未匹配的节点称为敞露点以敞露点为根，由非匹配边和匹配边交替构成的链称为交错链交错链的根为外点，其后内点与外点交替；外点是交错链的生长点以内点结束的交错链称为增广链，因为反转该链上各边的匹配状态可使匹配的边数增加一条匈牙利算法步骤令所有ai＝0在效率矩阵中找每列最小值qj，令bj＝qj

，故i,j，满足ai＋bjcij在满足ai＋bj＝cij

的边构成的等值子图中求最大基数匹配；若达到完全匹配则结束，否则到下一步对敞露点求每列的最小松弛量sj＝mini*{ci*j－ai*－bj}求最大增广量S＝0.5minj{sj}增广等值子图，j，bj＝bj＋S

i*(敞露点)，ai*＝ai*＋S

；

i(非敞露点)，ai＝ai－S返回到第3

步匈牙利算法举例**匈牙利算法举例*匈牙利算法举例

任务分配问题、匹配问题和TSP的关系三个问题都有一个nn

正权值的边权矩阵三个问题的解都可以用代数置换(permutation)表示i1,i2,i3,i4,i5是1,2,3,4,5的任一排列，表示元素位置的交换轮换，全轮换，对换TSP的解必须是一个全轮换任务分配问题的解可以是任一个置换匹配的解必须是n/2个对换任务分配问题是匹配问题的松弛问题

6.7

选址问题使所选地址到最远的服务对象距离尽可能小——中心点使所选地址到各服务对象的总距离最小——中位点有时间限制的多用中心点，如乡邮局总资源约束的多用中位点，如电话交换局

6.7.1各点之间的距离节点到节点间的最短距离，称为节点—节点距离边上某点到节点的最短距离，称为点—节点距离节点到某边上最远一点的距离，称为节点—边距离边上一点到另一边上最远点的距离，称为点—边距离1、边上某点到节点的最短距离dij

代表vi

与vj

间的最短距离，ars

代表边(r