运筹学课件 第二节 树

运筹学教程1一、树的概念定义14（树）:一个无圈的连通无向图称为树。树中次为1的点为树叶；次大于1的点为分枝点。bfed复习第二节树运筹学教程2二、图的生成树求解方法：（1）深探法（2）广探法（3）破圈法图的生成树不唯一运筹学教程3三、最小生成树求解方法：（1）避圈法（2）破圈法运筹学教程4主要内容最短路问题的算法最短路问题的应用第三节最短路问题运筹学教程5最短路问题的研究问题的提法——寻求网络中两点间的最短路就是寻求连接这两个点的边的总权数为最小的道路。（注意：在有向图中，道路——开的初等链中所有的弧应是首尾相连的。）应用背景——管道铺设、线路安排、厂区布局、设备更新等。运筹学教程6一、D氏标号法（Dijkstra狄克斯拉）1.D氏标号法思路（1）求解思路——从始点出发，逐步顺序地向外探寻，每向外延伸一步都要求是最短的。（2）使用条件——网络中所有的弧权均非负，即。0ijl运筹学教程7（3）选用符号的意义：①标号P（永久性标号）——从始点到该标号点的最短路权。②标号T（试探性标号）——从始点到该标号点的最短路权上界。运筹学教程8（4）计算步骤第一步：始点标上永久标号P(vS)=0,其余各点标试探性标号T(vj)=+。第二步：如果vi为刚得到P标号的点,考虑满足条件(Vi,Vj)∈E,Vj具有T标号;修改Vj的T标号为ijijjlvpvTvT)(),(min)(运筹学教程9第三步：比较所有具有T标号的点,把最小者改为P标号,即当存在两个以上最小者时,可同时改为P标号;若网络图中已无T标号点，停止计算,否则,用代替vi转回第二步。)()(minjvvivTvPjiv运筹学教程102.例题1用D氏标号法求解图所示V1到V8最短路。v1v5v3v8v6v4v2v74416769557445P(v1)=0T(v2)=∞T(v4)=∞T(v6)=∞T(v8)=∞T(v7)=∞T(v5)=∞T(v3)=∞解:(1)首先给v1以P标号，P(v1)=0;给其余所有点T标号，T(vi)=+∞(i=2,3,4…8)(2)由于(v1,v2),(v1,v3)边属于E，且v2,v3为T标号，所以对v2,v3进行修改。T(v2)=min[T(v2),P(v1)+L12]=min[+∞,0+4]=4T(v3)=min[T(v3),P(v1)+L13]=min[+∞,0+6]=6(3)比较所有T标号T(v2)最小，令P(v2)=4,路径(v1,v2)T(v2)=4v1v5v3v8v6v4v2v74416769557445T(v3)=6P(v2)=4;V1(4)由于v2得到P标号，考察(v2,v4),(v2,v5)边，且v4,v5为T标号，所以对v4,v5进行修改。T(v4)=min[T(v4),P(v2)+L24]=min[+∞,4+5]=9T(v5)=min[T(v5),P(v2)+L25]=min[+∞,4+4]=8(5)比较所有T标号T(v3)最小，令P(v3)=6,路径(v1,v3)P(v3)=6;V1P(v1)=0T(v2)=∞T(v4)=∞T(v6)=∞T(v8)=∞T(v7)=∞T(v5)=∞T(v3)=∞T(v2)=4v1v5v3v8v6v4v2v74416769557445T(v3)=6P(v2)=4;V1T(v4)=9T(v5)=8(6)由于v3得到P标号，考察(v3,v4),(v3,v5)边，且v4,v5为T标号，所以对v4,v5进行修改。T(v4)=min[T(v4),P(v3)+L34]=min[+9,6+4]=9T(v5)=min[T(v5),P(v3)+L35]=min[+8,6+7]=8(7)比较所有T标号T(v5)最小，令P(v5)=8,路径(v2,v5)P(v3)=6;V1P(v1)=0T(v2)=∞T(v4)=∞T(v6)=∞T(v8)=∞T(v7)=∞T(v5)=∞T(v3)=∞T(v2)=4v1v5v3v8v6v4v2v74416769557445T(v3)=6P(v2)=4;V1T(v4)=9T(v5)=8P(V5)=8;V2(8)由于v5得到P标号，考察(v5,v6),(v5,v7)边，且v6,v7为T标号，所以对v6,v7进行修改。T(v6)=min[T(v6),P(v5)+L56]=min[+∞,8+5]=13T(v7)=min[T(v7),P(v5)+L57]=min[+∞,8+6]=14(9)比较所有T标号T(v4)最小，令P(v4)=9,路径(v2,v4)P(v3)=6;V1P(v1)=0T(v2)=∞T(v4)=∞T(v6)=∞T(v8)=∞T(v7)=∞T(v5)=∞T(v3)=∞T(v2)=4v1v5v3v8v6v4v2v74416769557445T(v3)=6P(v2)=4;V1T(v4)=9T(v5)=8P(V5)=8;V2T(V6)=13T(V7)=14P(V4)=9;V2(10)由于v4得到P标号，考察(v4,v6),(v4,v7)边，且v6,v7为T标号，所以对v6,v7进行修改。T(v6)=min[T(v6),P(v4)+L46]=min[+13,9+9]=13T(v7)=min[T(v7),P(v4)+L47]=min[+14,9+7]=14(11)比较所有T标号T(v6)最小，令P(v6)=13,路径(v5,v6)P(v3)=6;V1P(v1)=0T(v2)=∞T(v4)=∞T(v6)=∞T(v8)=∞T(v7)=∞T(v5)=∞T(v3)=∞T(v2)=4v1v5v3v8v6v4v2v74416769557445T(v3)=6P(v2)=4;V1T(v4)=9T(v5)=8P(V5)=8;V2T(V6)=13T(V7)=14P(V4)=9;V2P(V6)=13;V5(12)由于v6得到P标号，考察(v6,v7),(v6,v8)边，且v7,v8为T标号，所以对v7,v8进行修改。T(v7)=min[T(v7),P(v6)+L67]=min[+14,13+5]=14T(v8)=min[T(v8),P(v6)+L68]=min[+∞,13+4]=17(13)比较所有T标号T(v7)最小，令P(v7)=14,路径(v5,v7)P(v3)=6;V1P(v1)=0T(v2)=∞T(v4)=∞T(v6)=∞T(v8)=∞T(v7)=∞T(v5)=∞T(v3)=∞T(v2)=4v1v5v3v8v6v4v2v74416769557445T(v3)=6P(v2)=4;V1T(v4)=9T(v5)=8P(V5)=8;V2T(V6)=13T(V7)=14P(V4)=9;V2P(V6)=13;V5T(V7)=14T(V8)=17P(V7)=14;V5(14)由于v7得到P标号，考察(v7,v8)边，且v8为T标号，所以对v8进行修改。T(v8)=min[T(v8),P(v7)+L78]=min[+17,14+1]=15(15)只有一个T标号T(v8)，令P(v8)=15,路径(v7,v8)P(v3)=6;V1P(v1)=0T(v2)=∞T(v4)=∞T(v6)=∞T(v8)=∞T(v7)=∞T(v5)=∞T(v3)=∞T(v2)=4v1v5v3v8v6v4v2v74416769557445T(v3)=6P(v2)=4;V1T(v4)=9T(v5)=8P(V5)=8;V2T(V6)=13T(V7)=14P(V4)=9;V2P(V6)=13;V5T(V7)=14T(V8)=17P(V7)=14;V5T(V8)=15P(V8)=15;V7运筹学教程18结论:V1到V8的最短距离：15；最短路径：V1V2V5V7V8运筹学教程19（5）D氏标号法（Dijkstra）的特点（获得的附加信息）：能得到从始点到各点的最短路线和最短路长。v1v5v3v8v6v4v2v74416769557445T(v2)=4P(v2)=4;V1T(v3)=6P(v3)=6;V1T(v4)=9T(v4)=9P(v4)=9;V2T(v5)=8T(v5)=8P(v5)=8;V2T(v6)=13T(v6)=13P(v6)=13;V5P(v7)=14;V5T(v7)=14T(v7)=14T(v7)=14P(v1)=0T(v2)=∞T(v3)=∞T(v4)=∞T(v5)=∞T(v6)=∞T(v7)=∞T(v8)=∞T(v8)=17T(v8)=15P(v8)=15;V7T(vj)=min[T(vs),P(vs)+Lsj]运筹学教程21例2：设备更新问题某工厂使用一台设备，每年年初工厂需要作出决定，如果继续使用旧的，要付维修费用；如果购买一台新设备，要付购买费。要求制订一个5年的更新计划，目标使总支出最小。3.最短路问题的应用运筹学教程22项目第1年第2年第3年第4年第5年购买费1112131414服役年龄0-11-22-33-44-5维修费5681118残值：对应的是使用n年43210运筹学教程23边(vi，vj)上的数字表示第i年初购进设备一直使用到第j年年初（j-1年底）所需要支付的购买、维修的全部费用；问题化为最短路问题用点vi表示第i年初购进设备，虚设一个V6表示第5年年底；用边(vi，vj)表示第i年初购进设备一直使用到第j年年初（j-1年底）；运筹学教程24v1v6v5v4v3v2构造图v1v6v5v4v3v2121515141328405919213020294122(v1,v2)=12=11-4（1年的残值）+5(1年维修)(v2,v3)=13=12-4+5；(v3,v4)=14=13-4+5；(v4,v5)=15=14-4+5；(v5,v6)=15=14-4+5；(v1,v3)=19=11-3（2年的残值）+5+6(2年维修)(v1,v4)=28=11-2（3年的残值）+5+6+8(3年维修)(v1,v5)=40=11-1（4年的残值）+5+6+8+11(4年维修)(v1,v6)=59=11-0（5年的残值）+5+6+8+11+18(5年维修)(v2,v4)=20=12-3（2年的残值）+5+6(2年维修)(v2,v5)=29=12-2（3年的残值）+5+6+8(3年维修)(v2,v6)=41=12-1（4年的残值）+5+6+8+11(4年维修)(v3,v5)=21=13-3（2年的残值）+5+6(2年维修)(v3,v6)=30=13-2（3年的残值）+5+6+8(3年维修)(v4,v6)=22=14-3（2年的残值）+5+6(2年维修)项目第1年第2年第3年第4年第5年购买费1112131414服役年0-11-22-33-44-5维修费5681118残值43210构造赋权图运筹学教程26v1v6v5v4v3v2121515141328405919213020294122问题转化为求：从v1到v6的最短路问题。应用D氏标号法求最短路线：最短路19+30=49；表示:在第一年，第三年初各购买一台设备，总费用最小。v1v3v6运筹学教程27237184566134105275934682练习：用D氏标号算法求解从1到8的最短路运筹学教程28237184566134105275934682P1=0T2=∞T5=∞T4=∞T6=∞T7=∞T3=∞T8=∞运筹学教程29237184566134105275934682min{2,1,3,∞.}=1，4点变p标号P1=0T4=∞T7=∞T6=∞T5=∞T2=∞T3=∞T8=∞T2=2T4=1T6=3P4=1,v1运筹学教程30237184566134105275934682min{2,3,3,∞}=2，2点变P标号P1=0T2=∞T2=25T4=∞T4=1P4=1,V1T6=∞T6=3T7=∞T3=∞T5=∞T8=∞T7=3P2=2,v1运筹学教程31237184566134105275934682P1=0T2=∞T2=25T4=∞T4=1P4=1,v1T6=∞T6=3T7=∞T3=∞T5=∞T8=∞P2=2,v1T3=8T5=7min{3,8,7,3