以最短路为基础汇总网路上的流.ppt

《以最短路为基础汇总网路上的流.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、以最短路为基础汇总网路上的流在电路网中每两点之间都有中继电路群需求，但并不是任两点都有物理传输链路根据两点间最短传输路径将该两点间的电路需求量加载到这条传输路径上去：设a25=10是节点2和5之间的电路需求，节点2和5之间的最短传输路径为2135，则加载过程为:T21=T21+10,T13=T13+10,T35=T35+10；Tij是传输链路ij上加载的电路数；当所有点间电路都加载完则算法结束16.6欧拉回路和中国邮递员问题（了解）中国邮递员问题(ChinesePostmanProblem,CPP)是由我国管梅谷教授于1962年首先提出并发表的问题是从邮局出

2、发，走遍邮区的所有街道至少一次再回到邮局，走什么路由才能使总的路程最短？如果街区图是一个偶图，根据定理3，一定有欧拉回路，CPP问题也就迎刃而解了若街区图不是偶图，则必然有一些街道要被重复走过才能回到原出发点显然要在奇次点间加重复边如何使所加的边长度最少归结为求奇次点间的最小匹配(minimumweightedmatch)—由Edmons给出多项式算法(1965)2解中国邮递员问题的步骤0、将图中的所有悬挂点依次摘去1、求所有奇次点间的最短距离和最短路径2、根据奇次点间的最短距离求最小完全匹配3、根据最小完全匹配和最短路径添加重复边4、将悬挂点逐一恢复，并加重复边5

3、、根据得到的偶图，给出欧拉回路的若干种走法3解中国邮递员问题的步骤46.7哈密尔顿回路及旅行推销员问题6.7.1哈密尔顿回路(Hamiltoniancircuit)连通图G(V,E)中的回路称为哈密尔顿回路，若该回路包括图中所有的点。显然哈密尔顿回路有且只有n条边，若

4、V

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

6、完全图中有多少个边不相交的哈密尔顿回路？最小哈密尔顿回路问题(NP-complete)哈密尔顿路径：包含图中所有点的路径为什么说找两点间的最长路是非常困难的问题？(n1)!/2(n1)/256.7.2旅行推销员问题(TravelingSalesmanProblem)旅行推销员问题(TSP)：设v1,v2,...,vn为n个已知城市，城市之间的旅程也是已知的，要求推销员从v1出发，走遍所有城市一次且仅一次又回到出发点，并使总旅程最短这种不允许点重复的旅行推销员问题就是最小哈密尔顿回路问题一般旅行推销员问题(GTSP)：允许点重复的TSP当网路边权满足三角不等式时，

7、一般旅行推销员问题就等价于最小哈密尔顿回路问题当网路边权不满足三角不等式时，只要用两点间最短路的距离代替原来的边权，就可以满足三角不等式，在此基础上求最小哈密尔顿回路典型的应用：乡邮员的投递路线邮递员开邮箱取信的路线问题邮车到各支局的转趟问题6TSP的启发式算法(Heuristicalgorithm)穷举法：指数算法分支定界法：隐枚举法二交换法(two-option,Lin’salgorithm)哈密尔顿回路可以用点的序列表示从任一个哈密尔顿回路(即任何一个序列)出发按照一定顺序试图交换相邻两个点的顺序，若路程减少则完成交换，继续下一个交换；若没有改善，则不进行本次

8、交换，尝试下一个交换；若所有的相临交换都试过而不能改善，则算法结束，得到一个局部最优点模拟退火(SimulatedAnnealing)随机地采用二交换法当交换后没有使目标函数改善，也可能以玻尔兹曼分布概率被接受，但这种概率是随模拟的温度下降而减少的发挥了计算机的优点，尽量减少陷入局部极值点模拟物理机制7二交换法举例初始解：1-2-3-4-51-3-2-4-51-3-2-4-51-3-4-2-51-3-4-2-51-3-4-5-25-3-4-2-13-1-4-2-58算法复杂度Prim算法i=1n1次比较，最多n1次赋值i=22(n2)次比较，最

9、多2(n2)次赋值i=kk(nk)次比较，最多k(nk)次赋值Dijkstra算法i=1n1次临时标记，永久标记n1次比较和赋值i=2n2次临时标记，永久标记n2次比较和赋值i=knk次临时标记，永久标记nk次比较和赋值9Prim算法的改进增加一个辅助记录型数组，用以记录当前V中各节点到V的最小边，minedge[i].cost记录该边的权值，minedge[i].vex记录该边V中的顶点。若minedge[i].cost<0则表明i点进入集合Vfori:=2tondobeginminedge[i].vex:=1;minedge[i].cost