7 基本检索及周游.ppt

各结点的最低深度优先数是L(1:10)＝(1,1,1,1,6,8,6,6,5,4) 关节点： 结点3：它的儿子结点10有L(10)＝4而DFN(3)=3。 结点2：儿子结点5有L(5)=6而DFN(2)＝6 结点5：儿子结点6有L(6)＝8而DFN(5)＝7 1 4 3 10 9 2 5 6 7 8 1 2 3 4 5 6 7 8 9 10 计算L(u)的方法：按后根次序访问深度优先生成树的结点 确定G的关节点的工作： 1.完成对G的深度优先有哪些信誉好的足球投注网站，产生G的深度优先生成树T 2.按后根次序访问树T的结点 算法5.11计算DFN和L的算法 Procedure ART(u,v) //u是开始结点。在深度优先生成树中，u若有父亲，则v是其父亲。Num=1// Global DFN(n),L(n),num,n DFN(u) ← num; L(u) ← num; num← num+1 For 每个邻接于u的结点w do if DFN(w)=0 then call ART(w,u) //还没访问w// L(u) ← min(L(u),L(w)) else if w ≠ v then L(u) ← min(L(u)，DFN(w)) endif endif Repeat End ART 算法分析： 设图G有n个结点e条边，G由邻接表表示，那么ART的计算时间为O(n+e)。因此L(1:n)可在时间O(n+e)内算出。一旦算出L(1:n)，G的关节点就能在O(n)时间内识别出来。因此识别关节点的总时间不超过O(n+e) 判断G的双连通分图方法： 在第三行调用ART之后有L(w) ≥L(u)，就可断定u或者是根，或者是关节点。不管u是否是根，也不管u有一个或是多个儿子，将边(u,w)和对ART的这次调用期间遇到的所有树边和逆边加在一起，构成一个双连通分图。 对ART作一些修改即可生成该算法，算法略 ` 注意：上述算法要在相对于生成树，所给定的图没有交叉边。而相对于宽度优先生成树，一些图可能有交叉边，此时算法ART对BFS不适用。 7.4与/或图 很多复杂问题很难或没法直接求解，但可以分解成一系列（类型不同）的子问题，而这些子问题又可反复细分成一些更小的子问题，一直到分成一些可普通求解的，相当基本的问题为止。然后让这些分解成的子问题的全部或部分解在导出原问题的解。 例：洗衣服问题 某人一星期洗一次衣服，要做的事可以分为收集脏衣服、洗衣服、干燥、熨衣服、叠好衣服并放入衣柜。其中，某些事可采用不同的方法，如洗衣服可以是手洗或者是机器洗。干燥可以是晾干或者机器烘干。 对于上述问题，可以用与/或图来表示。 与/或图是一个有向图：结点表示问题，一个结点的子孙代表与其相关联的子问题。用一条弧将那些可以联合导出其解的子结点连结在一起。如下图(a)中表示问题A可以通过求解子问题B和C来解出，或者可由单个求解子问题D或E来解出。 为使结点含义单一化，即它的解或者需要求解它所有的子孙得到，或者求解它的一个子孙便可得到，通过引入图(b)中虚结点可达到此目的。前一类结点称为与结点，后一类结点称为或结点。 A B C D E (a) A A’ A’’ B C D E (b) 下图为洗衣服问题的与/或图。图中，没有子孙的结点是终结点，它代表基本问题并标记上可解或不可解。可解的终结点用方框表示。 洗衣服问题 收集 脏衣服 洗 干燥 熨 叠好并 归堆 手洗 机器洗 适当的更换 装入并 开始 晾干 机器烘干 适当的更换 装入并 开始 图7.17洗衣服问题对应的与/或图 概念： 解图是由与/或图中一些可解结点组成的子图，它表示对问题求解。 根据问题的与/或树判断该问题是否可解方法： 对与/或树作后根次序周游就可得出答案。 在算法执行过程中，一旦发现某与结点的一个儿子结点不可解，或者发现某或结点的一个儿子结点可解，就立即终止该算法，这可减少算法的工作量且对结果无任何影响。 判断与/或树是否可解的算法 Procedure SOLVE(T) //T是一棵其根为T的与/或树，T ≠0。如果问题可解则返回1，否则返回0// CASE :T是终结点： if T可解 then return(1) else return(0)