《算法设计与分析》第04章概要课件.ppt
算法设计与分析,DeSign and Analysis of AlgorithmsIn C+,“十一五”国家级规划教材,陈慧南 编著,电子工业出版社,第4章 基本搜索和遍历方法,基本概念 人工智能,人工智能研究如何使计算机去做过去只有人才能做的智能工作人工智能是关于知识的学科怎样表示知识以及怎样获得知识并使用知识的科学计算机博弈模式识别美国火星探测车人工智能研究,资料来源：百度知道 与 http:/,基本概念 问题的表示,状态空间法问题的归约(与或图)状态空间法:状态:所求问题的各种可能情况初始状态目标状态状态空间表示：图、树,基本概念 问题的解决,搜索 遍历无知搜索：盲目、穷举深度优先搜索(DFS)广度优先搜索(BFS)D-搜索有知搜索：启发式,2 图的搜索与遍历,Struct Enode int adjVex;Enode*nextArc Enode*a;,有向图与其邻接表,未访问、未检测（活结点）、已检测（死结点）、扩展结点（E-结点）、活结点表,2 图的搜索与遍历,/图类enum ColorTypeWhite,Gray,Black;class Graph public:Graph(int mSize);void DFS_Traversal(int*parent);/一维数组parent保存DFS生成森林void BFS_Traversal(int*prarent);/一维数组parent保存BFS生成森林 protected:void DFS(int u,int*parent,ColorType*color);/递归DFS函数访问从u可达结点void BFS(int u,int*parent,ColorType*color);/BFS函数访问从u可达结点 ENode*a;/生成指向ENode类对象的指针数组int n;/图中结点数目;,2 图的搜索与遍历,BFS规则(记v为起始结点）访问v，v成为活结点选择下一个活结点为E-结点，依次访问其各邻接点（成为活结点），v成为死结点；选择下一个活结点为E-结点重复上一步，直到无活结点结束以FIFO队列作为活结点表BFS遍历在结果称为广度优先树(森林)双亲表示法 保存在一维数组parent中,2 图的搜索与遍历,BFS示例,1,2,3,4,5,6,0,Parent数组：,O(n+e),2 图的搜索与遍历,DFS递归过程(记v为起始结点）访问结点v，使之成为未检测结点依次以v的未访问邻接结点为起始结点，进行DFS递归过程此过程中活结点表隐含在系统堆栈中实现DFS遍历在结果为一课深度优先树双亲表示法：以一维数组parent记录,2 图的搜索与遍历,DFS示例,O(n+e),根据深度优先树对图边分类,树边（粗线）反向边（B）正向边（F）交叉边（C）,约定无向图只有反向边和树边,3 双连通图,双连通图图G是双连通图等价于图G的任意两个结点之间存在简单回路，等价于图G中不包含关节点,无向连通图及双连通图,双连通图检测,关键在于检查图中是否存在关节点逐个结点测试法 太费时深度优先搜索法双连通图的深度优先树有以下特征 根结点只有一个孩子非根结点u的每一颗子树上 均有反向边指向u的祖先,双连通图检测,性质4-3设S=(V,T)是图G=(V,E)的一颗深度优先树，图中结点a是一个关节点，当且仅当a是根，且a至少两个孩子或者a不是根，且a的某颗树上没有指向a的祖先的反向边,双连通图检测,相关定义深度优先数du是指结点u在深度优先搜索树中被遍历到的次序号。程序中通过全局变量dtime记录根据深度优先搜索树，定义lowu如下：Lowu=min du,min Loww,w为u的孩子,min Lowx,(u,x)是一条反向边,双连通图检测,最小深度优先数Low(u)是指从u出发经过某条路径可以达到的其它结点的最低深度优先数。这里某条路径是指以下情况：自结点u出发通过一条反向边到达结点x自结点u出发，经过u的孩子w，以及由w出发由树边组成的路径和一条反向边到达结点y。,双连通图检测,求图G的关节点的算法对于非根结点u，若存在u的一个孩子w使Lowwdu，则u是一个关节点。,【程序4-4】计算d和Lowvoid Graph:DFS_low(int u,int p)/u是起始结点，p是u的双亲结点 Lowu=du=time+;/Lowu=du for(ENode*w=au;w;w=w-nextArc)int v=w-adjVex;if(dv=-1)/表示v尚未访问DFS_low(v,u);if(LowuLowv)Lowu=Lowv;/是树边else if(v！=p/是反向边,是否考虑了根结点有两个孩子的情况呢？,【程序4-5】求双连通分量void Graph:BiCom(int u,int p)Lowu=du=time+;eNode e;for(ENode*w=au;w;w=w-nextArc)int v=w-adjVex;e.u=u;e.v=v;if(v！=p,构造双连通图,边添加算法For(图G的第个关节点a)设B1,B2,Bk为包含a的双连通分量;令vi(vi a)是Bi(1 i k)中的一个结点;将边(vi,vi+1),1 i k 添加到图G中;,3.问题归约,与或图与或树与或树是否可解？构建解树,
