第4章 基本搜索和遍历方法.

Presentation on theme: "第4章 基本搜索和遍历方法."— Presentation transcript:

1 第4章 基本搜索和遍历方法

2 资料来源：百度知道 与 http://cai.csu.edu.cn/jpkc/rengongzhineng/
基本概念 人工智能 人工智能 研究如何使计算机去做过去只有人才能做的智能工作 人工智能是关于知识的学科――怎样表示知识以及怎样获得知识并使用知识的科学 计算机博弈 模式识别 美国火星探测车 人工智能研究 资料来源：百度知道 与

3 基本概念 问题的表示 状态空间法: 状态空间表示：图、树 状态空间法 问题的归约(与或图) 状态: 所求问题的各种可能情况 初始状态
基本概念 问题的表示 状态空间法 问题的归约(与或图) 状态空间法: 状态: 所求问题的各种可能情况 初始状态 目标状态 状态空间表示：图、树

4 基本概念 问题的解决 搜索 遍历 无知搜索：盲目、穷举 深度优先搜索(DFS) 广度优先搜索(BFS) D-搜索 有知搜索：启发式

5 2 图的搜索与遍历 有向图与其邻接表 1 2 ▲ 6 3 4 5 1 2 3 4 5 6 Struct Enode{ int adjVex; Enode* nextArc } Enode** a; 未访问、未检测（活结点）、已检测（死结点）、 扩展结点（E-结点）、活结点表

6 2 图的搜索与遍历 //图类 enum ColorType{White, Gray, Black}; class Graph {
2 图的搜索与遍历 //图类 enum ColorType{White, 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; //图中结点数目 };

7 2 图的搜索与遍历 BFS规则 (记v为起始结点） BFS遍历在结果称为广度优先树(森林) 访问v，v入列成为活结点
2 图的搜索与遍历 BFS规则 (记v为起始结点） 访问v，v入列成为活结点 从队列中取下一个活结点为E-结点，依次访问其各邻接点（并入列成为活结点），v成为死结点； 重复上一步，直到队列中无活结点时结束 以FIFO队列作为活结点表 BFS遍历在结果称为广度优先树(森林) 双亲表示法 保存在一维数组parent中

8 O(n+e) 2 图的搜索与遍历 BFS示例 Parent数组： 1 2 3 4 5 6 1 2 3 4 5 6 -1 1 2 3 4 6
2 图的搜索与遍历 BFS示例 1 2 3 4 5 6 1 2 3 4 5 6 -1 1 2 3 4 6 5 Parent数组： O(n+e)

9 2 图的搜索与遍历 DFS递归过程 (记v为起始结点） DFS遍历结果为一课深度优先树 访问结点v，使之成为未检测结点
2 图的搜索与遍历 DFS递归过程 (记v为起始结点） 访问结点v，使之成为未检测结点 依次以v的未访问邻接结点为起始结点，进行DFS递归过程 此过程中活结点表隐含在系统堆栈中实现 DFS遍历结果为一课深度优先树 双亲表示法： 以一维数组parent记录

10 2 图的搜索与遍历 DFS示例 1 2 3 4 5 6 O(n+e)

11 根据深度优先树对图边分类 树边（粗线） 反向边 （B） 正向边（F） 交叉边（C） 约定无向图只有反向边和树边

12 D-搜索 (记v为起始结点） 访问v，v入栈成为活结点 从栈中取一个活结点为E-结点，依次访问其各邻接点（并入列成为活结点），v成为死结点；
重复上一步，直到栈中无活结点时结束 以堆栈作为活结点表

13 O(n+e) D-搜索示例 Parent数组： 1 2 3 4 5 6 1 2 ▲ 6 3 4 5 1 2 3 4 5 6 -1 1 2 3
D-搜索示例 1 2 ▲ 6 3 4 5 1 2 3 4 5 6 -1 1 2 3 4 6 5 Parent数组： O(n+e)

14 3 双连通图 双连通图 图G是双连通图等价于 图G的任意两个结点之间存在简单回路，等价于 图G中不包含关节点/边

15 无向连通图及双连通图

16 双连通图检测 关键在于检查图中是否存在关节点 逐个结点测试法 太费时 深度优先搜索法 双连通图的深度优先树有以下特征 根结点只有一个孩子
逐个结点测试法 太费时 深度优先搜索法 双连通图的深度优先树有以下特征 根结点只有一个孩子 非根结点u的每一颗子树上 均有反向边指向u的祖先

17 双连通图检测 性质4-3 设S=(V,T)是图G=(V,E)的一颗深度优先树，图中结点a是一个关节点，当且仅当 a是根，且a至少两个孩子

18 双连通图检测 相关定义 深度优先数d[u]是指结点u在深度优先搜索树中被遍历到的次序号。 程序中通过全局变量dtime记录
根据深度优先搜索树，定义low[u]如下： Low[u]=min{ d[u] , min{ Low[w], w为u的孩子 }, min{ Low[x], (u,x)是一条反向边} }

19 双连通图检测 最小深度优先数Low(u) 是指从u出发经过某条路径可以达到的其它结点的最低深度优先数。 这里某条路径是指以下情况：
自结点u出发通过一条反向边到达结点x 自结点u出发，经过u的孩子w，以及由w出发由树边组成的路径和一条反向边到达结点y。

20 双连通图检测 求图G的关节点的算法 对于非根结点u，若存在u的一个孩子w使Low[w]≥d[u]，则u是一个关节点。

21 void Graph::DFS_low(int u, int p) { //u是起始结点，p是u的双亲结点
【程序4-4】 计算d和Low void Graph::DFS_low(int u, int p) { //u是起始结点，p是u的双亲结点 Low[u]=d[u]=time++; //Low[u]=d[u] for (ENode* w=a[u]; w; w=w->nextArc){ int v=w->adjVex; if (d[v]==-1) { //表示v尚未访问 DFS_low(v, u); if (Low[u]>Low[v]) Low[u]=Low[v];//<u, v>是树边 } else if (v！=p && Low[u]>d[v]) Low[u]=d[v]; //<u, v>是反向边 是否考虑了根结点有两个孩子的情况呢？

22 【程序4-5】 求双连通分量 void Graph::BiCom(int u, int p) { Low[u]=d[u]=time++; eNode e; for (ENode* w=a[u]; w; w=w->nextArc){ int v=w->adjVex; e.u=u; e.v=v; if(v！=p && d[v]<d[u]) s.Push(e); //边进栈 if (d[v]==-1) { BiCom(v, u); if(Low[v]>=d[u]){ cout<<endl<<"New bicommponent\n"; do { e=s.Top(); s.Pop(); if(u<v && e.u>e.v) Swap(e.u, e.v); else if(u>v && e.u<e.v) Swap(e.u,e.v); cout<<"("<<e.u<<","<<e.v<<")"; } while(e.u！=u || e.v！=v); } if (Low[u]>Low[v]) Low[u]=Low[v]; else if (v！=p && Low[u]>d[v]) Low[u]=d[v];

23 构造双连通图 边添加算法 For (图G的第个关节点a) { 设B1, B2,…,Bk为包含a的双连通分量;
令vi(vi ≠a)是Bi(1≤ i ≤ k)中的一个结点; 将边(vi,vi+1), 1 ≤ i ≤ k 添加到图G中; }

24 3. 问题归约（略） 与或图 与或树 与或树是否可解？ 构建解树