离散数学课件-第6章-2

1,离散数学DiscreteMathematics,汪荣贵教授合肥工业大学软件学院专用课件2011.06,Chapter6,GraphAlgorithms,3,2020/5/6,6.1最短路径问题及算法6.2图的遍历、划分与关键路径6.3网络流图问题及算法6.4匹配理论及算法,4,2020/5/6,6.2图的遍历、划分与关键路径,1.图的遍历,图的遍历：从图的某顶点出发，访问图中所有顶点，并且每个顶点仅访问一次。图的遍历算法：深度优先搜索（Depth-FirstSearch）DFS广度优先搜索（Breadth-FirstSearch）BFS,深度优先搜索（DFS）,DFS（Depth-FirstSearch）算法是图论中最重要的算法之一，它的思路可以用迷宫法则来表述。下图是1690年独裁者威廉王修筑的迷宫示意图，现遗址在奥地利。,x,b,d,e,f,c,l,g,h,i,j,a,k,一、迷宫法则,任务是从事先未知结构的迷宫入口出发，每个走廊都要搜索，再从入口退出。为了不兜圈子尽快退出，要记住哪些走廊已经走过，沿着未走过的走廊尽可能地走下去，走到已无未走过的走廊可走时，沿来路返回，到某一路口，发现可通往一条未走过的走廊时，沿此走廊搜索，依次类推，直至完成任务。,迷宫法则,一直往前走碰壁就回头换条路走沿途要记录走过的路线,老鼠走迷宫dfs,1973年，用上述迷宫思想，Hopcroft和Tarjan设计了下面有效的DFS算法。dfs(v0)从v0出发深度遍历1、访问v0visit(v0)；2、依次从v0未被访问的邻接点出发深度遍历。,容易看出，dfs遍历是一个递归搜索的过程,深度优先搜索过程：,例,v0,v1,v3,v5,v4,v2,v6,v7,搜索,回溯,dfs(v0),v0,v1,v3,v5,v4,v2,v7,v6,序列：v0-v1-v3-v5-v4-v2v6-v7,序列2：v0-v1-v4-v5-v3-v2-v7-v6,由于没有规定访问邻接点的顺序，深度优先序列不是唯一的,左图所示的是DFS执行的示意图，标了箭头的是父子边(以父为尾，子为头的搜索边)，它们导出的是生成树，称为DFS生成树。,v0,v1,v3,v5,v4,v2,v6,v7,v0,v1,v3,v5,v4,v2,v7,v6,v0,v1,v3,v5,v4,v2,v6,v7,v0,v1,v3,v5,v4,v2,v7,v6,DFS生成树,可以看出，用dfs对迷宫进行搜索，可以找出穿过迷宫的路，但是不一定是最短的。如果要找出最短的，则对迷宫进行bfs搜索。,二、对搜索树进行dfs搜索,N皇后问题：nn的棋盘上放置n个皇后，使之相互不能攻击。现以4皇后问题为例。,例,为求解n皇后问题，可采用穷举法，即把所有放置情况都列出来，然后搜索符合要求的解。,解,12,解,若不进行剪枝，则时间呈指数增长,DFS算法举例,背包问题：设有n个物品，其重量分别为：w1，w2，w3，wn，所有物品的重量之和大于等于背包所能放置的重量S。设计算法从中找出若干物品放入背包，使其重量之和正好等于S。在杂货店比赛中你获得了第一名，奖品是一车免费杂货。店中有n种不同的货物。规则规定从每种货物中最多只能拿一件，车子的容量为C，物品i需占用wi的空间，价值为pi。,试探法求解背包问题，可能会有下面三种情况：（1）放置后正好符合条件，则输出；（2）放置后，背包中重量S，则继续放置；（3）放置后，背包中重量S，则将包里的物品依次取出，换一种方案试探。,现有5个不同重量的物品，重量分别为1，2，3，4，5kg，把物品放入能装6kg的背包里，保证背包为最满，有几种放置方法？,广度优先搜索（BFS）,BFS（Breadth-FirstSearch）算法的描述bfs(v0)从v0出发广度遍历1、访问v0visit(v0)；2、依次访问v0未被访问的邻接点；3、假设这一层访问的结点次序为vk1，vk2，vkm，依次访问vk1，vk2，vkm未被访问的邻接点。,广度优先搜索过程：,v0,v1,v3,v5,v4,v2,v6,v7,bfs(v0),v0,v1,v3,v5,v4,v2,v7,v6,例,序列：v0-v1-v2-v3-v4-v6-v7-v5,由于没有规定访问邻接点的顺序，广度优先序列不是唯一的,搜索,序列2：v0-v2-v1-v4-v3-v7-v6-v5,BFS搜索过程记录的边构成BFS生成树：,注,BFS算法的一个显著特点是：层次性。所以可以用来求两点间最短路径。,1,2.图的划分,划分的定义：图G中，若顶点vG，将v及和v相关联的边去掉，图G的连通分量数增加，则v称为图G的切割点或者关节点。,3,定义：具有和切割点相同性质的边称为图G的桥（割边）。,切割点v的性质：先找出图G的DFS生成树（1）若v是根，则v的孩子数目2；（2）若v是非根，则v的后代结点不存在到v的祖先的后退边。,num(v)表示dfs生成树中v的访问序号；low(v)表示v的后退边回到的顶点序号；low(v)的计算步骤：(1)第一次访问v，low(v)=num(v)；(2)遇到后退边(v,w)时，low(v)=minlow(v),num(w)(3)从w回溯到v时，low(v)=minlow(v),low(w),这样，对图G的DFS生成树的所有顶点检查一次后，满足：low（w）num（v）的v是切割点（充要条件）。这里，w是v的“儿子”。（v非根）,求下图的切割点。,例,假设从v1出发，求得的DFS生成树如下：,解,num(v1)=1,num(v2)=2,num(v3)=3,num(v4)=4,num(v5)=5,num(v6)=6,假设从v1出发，检查所有顶点过程如下：,v2,v6,v5,v1,v3,v4,解,(1),low(v1)=num(v1),low(v1)=1,num(v1)=1,num(v2)=2,num(v3)=3,num(v4)=4,num(v5)=5,num(v6)=6,low(v3)=num(v3),low(v2)=2,low(v2)=num(v2),low(v3)=3,(2),DFS搜索,后退边,回溯,假设从v1出发，检查所有顶点过程如下：,v2,v6,v5,v1,v3,v4,解,(1),low(v1)=1,num(v1)=1,num(v2)=2,num(v3)=3,num(v4)=4,num(v5)=5,num(v6)=6,low(v3)=minnum(v1),low(v3),low(v2)=2,low(v3)=3,(2),(3),low(v3)=1,DFS搜索,后退边,回溯,假设从v1出发，检查所有顶点过程如下：,v2,v6,v5,v1,v3,v4,解,(1),low(v1)=1,num(v1)=1,num(v2)=2,num(v3)=3,num(v4)=4,num(v5)=5,num(v6)=6,low(v4)=num(v4),low(v2)=2,low(v3)=1,(2),(3),(4),low(v4)=4,low(v4)=minnum(v1),low(v4),low(v4)=1,(5),low(v4)=minnum(v2),low(v4),(6),DFS搜索,后退边,回溯,low(v2)=2,low(v3)=minlow(v3),low(v4),假设从v1出发，检查所有顶点过程如下：,v2,v6,v5,v1,v3,v4,解,(1),low(v1)=1,num(v1)=1,num(v2)=2,num(v3)=3,num(v4)=4,num(v5)=5,num(v6)=6,low(v3)=1,(2),(3),(4),low(v4)=1,(5),low(v2)=minlow(v2),low(v3),(6),DFS搜索,后退边,回溯,(7),(8),(9),low(v1)=minlow(v2),low(v1),low(v2)=1,假设从v1出发，检查所有顶点过程如下：,v2,v6,v5,v1,v3,v4,解,(1),low(v1)=1,num(v1)=1,num(v2)=2,num(v3)=3,num(v4)=4,num(v5)=5,num(v6)=6,low(v2)=1,low(v3)=1,(2),(3),(4),low(v4)=1,(5),(6),DFS搜索,后退边,回溯,(7),(8),(9),(10),(11),low(v5)=5,low(v6)=6,low(v5)=num(v5),low(v6)=num(v6),假设从v1出发，检查所有顶点过程如下：,v2,v6,v5,v1,v3,v4,解,(1),low(v1)=1,num(v1)=1,num(v2)=2,num(v3)=3,num(v4)=4,num(v5)=5,num(v6)=6,low(v2)=1,low(v3)=1,(2),(3),(4),low(v4)=1,(5),(6),DFS搜索,后退边,回溯,(7),(8),(9),(10),(11),low(v5)=5,low(v6)=6,low(v6)=minnum(v1),low(v6),(12),low(v6)=1,假设从v1出发，检查所有顶点过程如下：,v2,v6,v5,v1,v3,v4,解,(1),low(v1)=1,num(v1)=1,num(v2)=2,num(v3)=3,num(v4)=4,num(v5)=5,num(v6)=6,low(v2)=1,low(v3)=1,(2),(3),(4),low(v4)=1,(5),(6),DFS搜索,后退边,回溯,(7),(8),(9),(10),(11),low(v5)=5,low(v6)=1,low(v5)=minlow(v5),low(v6),(12),(13),(14),low(v1)=minlow(v1),low(v5),low(v5)=1,求得各顶点的low和num值如下：,v2,v6,v5,v1,v3,v4,解,low(v1)=1,num(v1)=1,num(v2)=2,num(v3)=3,num(v4)=4,num(v5)=5,num(v6)=6,low(v2)=1,low(v3)=1,low(v4)=1,low(v5)=5,low(v6)=1,low(v5)=1,low（w）num（v）,3.关键路径,按照软件生命周期，软件开发项目通常分为需求分析、总体设计、详细设计、实现、单元测试、集成测试、验收测试等各个阶段，而且当软件规模比较大的时候，又会分成几个子系统，每个子系统都有这些阶段，从而各个子系统的各阶段之间存在复杂的时间约束关系，软件项目经理通常需要找出其中的关键步骤，从而控制软件开发的进度。我们先引入一些概念来对这种与关键路径有关问题进行建模。,PERT图,定义：PERT图是一个有向连通图G=(V,E)，且：(1)每条边表示一个作业（工序），边的非负实数权表示完成该作业所需的时间；(2)每个顶点表示以该顶点为起点的作业的开始，也表示以该顶点为终点的作业结束；(3)作业开始条件：某条有向边e=所代表的作业可以开始当且仅当以v为终点的有向边所代表的作业全部完成；(4)G没有有向回路，也没有环；(5)G中有且仅有一个顶点的入度为0，称该顶点为源点；同时G中有且仅有一个顶点的出度为0，称该顶点为汇点。,实际上，对于PERT图，我们主要关心其关键路径，以及每个作业的最早启动时间和最晚启动时间。,关键路径,定义：给定PERT图G=(V,E)，关键路径：G中从源点到汇点最长带权路径称为关键路径。关键路径的长度T为完成整个任务（即包括所有作业）所必需的最少时间。关键作业：关键路径上的边所代表的作业称为关键作业。最早起动时间：对于某个作业e=，源点到该作业起点vk的最长路径长度k称为该作业的最早起动时间。最晚启动时间：设vk到汇点的最长路径长度为k，则该作业可最晚于k=Tk时间启动而不影响整个任务完成的预期时间T，k称为该作业的最晚启动时间。,很显然，作业e=是关键作业当且仅当k=k，因为这时e是处于从源点到汇点最长带权路径上。所以，我们可通过求每个作业的最早启动时间和最晚启动时间而得到PERT图的关键路径。,定理：设PERT图G=(V,E)的顶点编号v1,v2,vn，使得边e=E蕴涵ij。,令：1=0j=maxm+w(vm,vj)|1m的最早启动时间。这里w(vm,vj)定义为：,令：n=nk=mink,m-w(vk,vm)|k的最晚启动时间。,关键路径举例,例子：考虑下面的PERT图，求关键路径。,注意顶点可看作一种状态，在该状态，所有以它为终点的作业都已经完成，而所有以它为起点的作业准备启动。为计算每个作业（边）的最早启动时间和最晚启动时间，我们实际上计算每个顶点的最早启动时间和最晚启动时间，也即，某顶点的最早启动时间（最晚启动时间）就是所有以该顶点为起点的作业的最早启动时间（最晚启动时间）。,我们先计算每个顶点的最早启动时间。最早启动时间的计算是从源点开始计算，源点的最早启动时间为0，对于顶点vi，只有在所有以vi为终点的边的起点vj的最早启动时间都计算出来之后，才能计算vi的最早启动时间，而且vi的最早启动时间i是：i=maxj+w(vj,vi)|E,1=0;3=max1+w(v1,v3)=max0+5=5;2=max1+w(v1,v2),3+w(v3,v2)=max4,5+3=8;4=max1+w(v1,v4),3+w(v3,v4)=max2,5+1=6;5=max3+w(v3,v5),2+w(v2,v5)=max5+3,8+5=13;6=max2+w(v2,v6),5+w(v5,v6)=max8+4,13+4=17;7=max4+w(v4,v7),5+w(v5,v7)=max6+2,13+2=15;8=max5+w(v5,v8),6+w(v6,v8),7+w(v7,v8)=max13+4,17+5,15+3=22;,得到源点v1到汇点v8的最长带权路径长度为22，这也是完成整个任务的必需时间。,最晚启动时间的计算是从汇点开始计算，汇点的最晚启动时间等于其最早启动时间，对于顶点vi，只有在所有以vi为起点的边的终点vj的最晚启动时间都计算出来之后，才能计算vi的最晚启动时间，而且vi的最晚启动时间i是：i=minj-w(vi,vj)|E,8=8=22;6=min8-w(v6,v8)=min22-5=17;7=min8-w(v7,v8)=