算法学习 8.图论(下).pdf

《算法学习 8.图论(下).pdf》由会员分享，可在线阅读，更多相关《算法学习 8.图论(下).pdf（53页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图论(下)七月算法邹博2015年4月30日2/主要内容 继续关于深度优先搜索的讨论以某例题来观察DFS和动态规划的关系 最短路径单源点最短路径任意两点间的最短路径边存在负权 最小生成树Prim算法Kruskal算法 拓扑排序深化“拓扑”的概念3/深度优先搜索DFS 理念：不断深入，“走到头”回退。(回溯思想)一般所谓“暴力枚举”搜索都是指DFS 回忆数组章节中“N-Sum问题”的解法 实现 一般使用堆栈，或者递归 用途：DFS的过程中，能够获得的信息“时间戳”、“颜色”、父子关系、高度4/回文划分问题Palindrome Partitioning 给定一个字符串str，将str划分成若干子串，

2、使得每一个子串都是回文串。计算str的所有可能的划分。单个字符构成的字符串，显然是回文串；所以，这个的划分一定是存在的。如：s=“aab”，返回“aa”，“b”；“a”，“a”，“b”。5/回文划分问题Palindrome Partitioning 分析：在每一步都可以判断中间结果是否为合法结果：回溯法如果某一次发现划分不合法，立刻对该分支限界。事实上，一个长度为n的字符串，有n-1个位置可以截断，每个位置有两种选择，因此时间复杂度为O(2n-1)=O(2n)。6/Code7/Palindrome Partitioning思考 与之类似的：给定仅包含数字的字符串，返回所有可能的有效IP地址组合

3、。如：“25525511135”，返回“255.255.11.135”，“255.255.111.35”。该问题只插入3个分割位置。只有添加了第3个分割符后，才能判断当前划分是否合法。如：2.5.5.25511135，才能判断出是非法的。当然，它可以通过“25511135”大于“255.255”等其他限界条件“事先”判断。8/Palindrome Partitioning思考：动态规划如果已知：stri+1,i+2n-1的所有回文划分(i+1)，注：是个集合，存储了所有可能的回文划分，下同stri+2,i+3n-1的所有回文划分(i+2)，stri+3,i+4n-1的所有回文划分(i+3)，s

4、trn-1的所有回文划分(n-1)，如何求stri,i+1n-1的所有划分呢？分析：如果已知以stri为起点的子串中stri,i+1j是回文串，那么，该子串添加到(j)中，即为一种可能的划分方案。算法：将集合(i)置空；遍历j(ijn-1)，若stri,i+1j是回文串，则将stri,i+1j，(j)添加到(i)中；i从n-1到0，依次调用上面两步，最终返回(0)即为所求。9/动态规划解回文划分的Trick 在计算stri,i+1j是否是回文串这一子问题中，暴力也是无可厚非的。线性探索：j从i到n-1遍历即可。事实上，可以事先缓存所有的stri,i+1.j是回文串的那些记录：用二维布尔数组pn

5、n就够了：pij的true/false表示了stri,i+1.j是否是回文串；它本身是个小的动态规划：如果已知stri+1.j-1是回文串，那么，判断stri,i+1.j是否是回文串，只需要判断stri=strj就可以。10/Code11/回文子串问题的DFS与DP深刻认识 DFS的过程，是计算完成了str0i的切分，然后递归调用，继续计算stri+1,i+2n-1的过程；而DP中，故意使用了从后向前的方法：假定得到了stri+1,i+2n-1的所有可能切分方案，如何扩展得到stri,i+1n-1的切分；当然可以先计算str0i的所有可能切分，然后考察str0i+1的所有切分。从本质上说，二者

6、是等价的：最终都搜索了一颗隐式树。当然，如果题目要求“切分成最少数目的回文子串”，动态规划就有优势了事实上是快速删减了不可能的子树分支。12/附：Palindrome Partitioning II 给定一个字符串str，将str划分成若干子串，使得每一个子串都是回文串。在所有可能的划分中，子串数目最少是多少？如：s=“aab”，最少子串数目为2“aa”，“b”注：原leetcode题目是返回切分的数目“aab”返回1：切1刀。设di为字符0i划分的最小回文串的个数，则di=mindj+1|sj+1i是回文串。13/Palindrome Partitioning II 假设当前已经计算完成前缀

7、串str0i-1的最少划分数目d0i-1，其中dj表示前缀串str0j的最少划分数目；则：要划分前缀串str0i，假定划分方案的最后一个子串为strj+1i，显然，根据题意strj+1i为回文串，并且str0j一定是最少划分，即：di=mindj+1|sj+1i是回文串，i-1j0 注意：strji是否为回文串，本身是个小的动态规划 若已知strj+1i-1 是回文串，则只需判断strj=stri；上述整个过程从后向前分析仍然可以得到类似的结论；14/Code15/再谈LCA：Tarjan算法 Tarjan算法是由Robert Tarjan在1979年发现的一种高效的离线算法，也就是说，它要首

8、先读入所有的询问(求一次LCA叫做一次询问)，然后并不一定按照原来的顺序处理这些询问，该算法的时间复杂度O(N*(N)+Q)，其中，(x)不大于4，N表示问题规模，Q表示询问次数。16/Tarjan概览Tarjan算法基于深度优先搜索，对于新搜索到的一个结点u，首先创建由这个结点u构成的集合setU，再对当前结点u的每一个子树subTree进行搜索，每搜索完一棵子树sub，则可确定子树sub内的LCA询问都已解决。其他的LCA询问的结果必然在这个子树sub之外，这时把子树sub所形成的集合setSub与当前结点的集合setU合并成set，并将当前结点u设为这个集合set的祖先Ua。之后继续搜索

9、下一棵子树subNext，直到当前结点u的所有子树搜索完。这时把当前结点u设为checked，同时可以处理有关当前结点u的LCA询问，如果有一个从当前结点u到结点v的询问，且v已被检查过，则由于进行的是深度优先搜索，当前结点u与v的最近公共祖先LCA一定是未checked，而这个最近公共祖先LCA包含v的子树subV一定已经搜索过了，那么LCA一定是v所在集合的祖先Va。17/Tarjan算法：深度优先 关键：计算当前正要被回溯的节点10和其他结点的LCA(2,10)(10,7)(9,10)(10,8)18/Tarjan Code19/Tarjan算法的思考：如何存储候选查询 遍历P中的查询(

10、a,b)，将a插入到b的列表中，b插入到a的列表中隐式图；常见的空间检索方案 有点像链式Hash表：只是这里的“冲突”太多了凡是与该结点邻接的，都在冲突链中。20/Edsger Wybe Dijkstra 提出“goto有害论”;提出信号量和PV原语;解决了“哲学家聚餐”问题;最短路径算法(SPF)和银行家算法的创造者;第一个Algol 60编译器的设计者和实现者;THE操作系统的设计者和开发者;还有提过的“荷兰国旗问题”。21/最短路径SPF：Shortest Path First(Dijkstra)对于从v0至w，且经过最后一个中间结点为u的最短路径，有：DIST(w)=DIST(u)+c

11、(u,w)随着u的加入，DIST(w)调整为 DIST(w)=min(DIST(w),DIST(u)+c(u,w)22/最短路径示例23/最短路径示例 算法的执行在有n-1个结点加入到S中后终止，此时求出了v0至其它各结点的最短路径。问题：如何求出所有这些最短路径？记录前驱生成最短路径的贪心算法procedure SHORTEST-PATHS(v,COST,DIST,n)/G是一个n结点有向图，它由其成本邻接矩阵COST(n,n)表示。DIST(j)被置从结点v到结点j的最短路径长度，这里1jn。特殊的，DIST(v)被置成零/boolean S(1:n);real COST(1:n,1:n)

12、,DIST(1:n)integer u,v,n,num,i,wfor i1 to n do/将集合S初始化为空/S(i)0;DIST(i)COST(v,i)/若v到i没有边，DIST(i)=/repeatS(v)1;DIST(v)0 /结点v计入S/for num2 to n-1 do/确定由结点v出发的n-1条路/选取结点u,它使得DIST(u)=S(u)1/结点u计入S/for 所有S(w)0的结点w do /修改DIST(w)/DIST(w)=min(DIST(w),DIST(u)+COST(u,w)repeatrepeatend SHORTEST-PATHS)(min0)(wDISTw

13、S25/Floyd算法 Floyd算法又称为插点法，是一种用于寻找给定的加权图中多源点之间最短路径的算法。该算法名称以创始人之一、1978年图灵奖获得者罗伯特弗洛伊德命名。通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。26/算法分析 记录mapi,j为结点i到结点j的最短路径的距离；则：mapi,j=min mapi,k+mapk,j,mapi,j k取所有结点 同时，mapn,n=0 i,j,k各自从0到N-1，所以时间复杂度为O(n3)此外，如果图中存在负的权值，算法也是适用的。思考：Dijkstra算法允许边存在负权吗？27/Floyd算法28/带负权的最短路径 思考：计算图的最小

14、权值，若该权值大于0，按照Dijkstra算法正常计算；若小于0，则所有权值都加上该权值的绝对值+1，则修改后的图不再含有负权。使用Dijkstra算法计算最小路径。29/带负权的最短路径：Bellman-ford算法 本质：动态规划 适用：单源结点到其他所有结点的最短路径 若u-v是有向边，则dv=du+dis(u,v)这个操作被成为松弛操作。优点：对边权无要求，可以发现负环。30/Bellman-ford算法31/Bellman-ford算法分析图的任意一条最短路径既不能包含负权回路，也不会包含正权回路，因此它最多包含|v|-1条边。从源点s可达的所有顶点如果存在最短路径，则这些最短路径构

15、成一个以s为根的最短路径树。Bellman-Ford算法的迭代松弛操作，实际上就是按顶点距离s的层次，逐层生成这棵最短路径树的过程。在对每条边进行第1遍松弛的时候，生成了从s出发，层次至多为1的那些树枝。也就是说，找到了与s至多有1条边相联的那些顶点的最短路径；对每条边进行第2遍松弛的时候，生成了第2层次的树枝，就是说找到了经过2条边相连的那些顶点的最短路径。因为最短路径最多只包含|v|-1条边，所以，只需要循环|v|-1次。略做优化：如果第k次松弛操作后，最短路径没有得到更新，显然，后面仍然无法得到更新，可提前退出。并且，如果kn-1，一定不存在负环。32/最短路径例题 A traveler

16、s map gives the distances between cities along the highways,together with the cost of each highway.Now you are supposed to write a program to help a traveler to decide the shortest path between his/her starting city and the destination.If such a shortest path is not unique,you are supposed to output

17、 the one with the minimum cost,which is guaranteed to be unique.城市间由高速路连接，从城市A到城市B，有两个代价：高速距离、旅行价格。给定一张有向图和某个起点、终点，计算它们的最短路径：如果高速距离相同的路段，选择更小的旅行价格旅行价格保证是唯一的。33/输入输出Input Specification:Each input file contains one test case.Each case starts with a line containing 4 positive integers N,M,S,and D,where

18、 N(8-0-3-7-1-5-6-9-4-11-10-1245/拓扑排序的方法 从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它；从网中删去该顶点，并且删去从该顶点发出的全部有向边；重复上述两步，直到剩余的网中不再存在没有前趋的顶点为止。46/Code47/进一步思考拓扑排序算法可以发现圈；其本质是不断输出入度为0的点；可以用队列(或者栈)保存入度为0的点，避免每次遍历所有点查找入度；排序列表中的点需要更新与之连接的点的入度。入度减小1之后，如果为0，放入队列(或者栈)中。拓扑排序其实是给定了结点的一组偏序关系。“拓扑”一词的本意不限于此，在GIS中，它往往指点、线、面、体之间的相互邻接关系，即“橡皮泥集合”通过揉捏几何形体而不受影响的空间相互关系。存储这些关系，往往能够对某些算法带来好处。如：计算不自交的空间曲面是否能够围成三维体任意三维边都邻接两个三维曲面。48/扩展：拓扑的几何含义 一种关系：如三维数据间的拓扑关系49/三维拓扑重建50/视角再次放大面面、面线的拓扑51/参考文献 余祥宣等，计算机算法基础M，华中科技大学出版社，2001 戴方勤,LeetCode 题解,2014 http:/ 更多算法面试题在http:/ 直播课程 问答社区 contact us：微博研究者July七月问答邹博_机器学习53/感谢大家！欢迎大家提出宝贵的意见！