人工智能导论-第三章02-2014

1、第三章 确定性推理,3.1 推理概述 3.2 自然演绎推理 3.3 消解原理 3.4 图搜索概述 3.5 盲目搜索 3.6 启发式搜索,2020/9/15,人工智能导论 - 刘珊,1,搜索,定义 依靠经验，利用已有知识，根据问题的实际情况，不断寻找可利用知识，从而构造一条代价最小的推理路线，使问题得以解决的过程称为搜索。 类型 盲目搜索：按预定的控制策略进行搜索，在搜索过程中获得的中间信息并不改变控制策略。 启发式搜索：在搜索中加入了与问题有关的启发性信息，用于指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。,2020/9/15,人工智能导论 - 刘珊,2,3.4 图搜索概述,

2、图,一种限制最少的数据结构。 显式图 顶点或节点、边、环 有限图、简单图、带权图、连通图、网络 隐式图 子集树、排列树 图的存储 邻接矩阵：表示顶点之间相邻关系的矩阵 邻接表：由边表和顶点表两部分组成,2020/9/15,人工智能导论 - 刘珊,3,3.4 图搜索概述,图搜索,穷举搜索 启发式搜索 术语 问题状态、状态空间 解状态：一些问题状态 答案状态：一些解状态 状态空间树：解空间的树结构 活节点、E-节点、死节点 节点深度 路径、路径代价 节点扩展,2020/9/15,人工智能导论 - 刘珊,4,3.4 图搜索概述,开始,把S0放入OPEN表,OPEN表为空表？,把OPEN表中第一个节点

3、(n)移至CLOSED表,n为目标节点吗？,扩展n，把其后继节点放入OPEN表的末端，提供返回节点n的指针,修改指针方向,重排OPEN表,失败,成功,图搜索过程框图,是,是,否,否,2020/9/15,人工智能导论 - 刘珊,5,3.4 图搜索概述,图搜索,2020/9/15,人工智能导论 - 刘珊,6,OPEN表：存放刚生成的节点，也称为未扩展节点表。OPEN表的一般形式如右图：,CLOSED表：存放已经扩展或将要扩展的节点。 CLOSED表的一般形式如右图：,3.4 图搜索概述,第三章 确定性推理,3.1 推理概述 3.2 自然演绎推理 3.3 消解原理 3.4 图搜索概述 3.5 盲目搜

4、索 3.6 启发式搜索,2020/9/15,人工智能导论 - 刘珊,7,盲目搜索,特点：不需重排OPEN表 状态空间的盲目搜索 与或图的盲目搜索 类型 宽度优先搜索（广度优先搜索） 深度优先搜索 等代价搜索,2020/9/15,人工智能导论 - 刘珊,8,3.5 盲目搜索,状态空间的宽度优先搜索,定义 以接近起始节点的程度逐层扩展节点的搜索方法 基本思想 从初始节点S0开始逐层向下扩展，在第n层节点还没有全部搜索完之前，不进入第n+1层节点的搜索。 Open表中的节点总是按进入的先后排序。 特点 一种高代价搜索，但若有解存在，必能找到,2020/9/15,人工智能导论 - 刘珊,9,3.5 盲

5、目搜索,开始,把S0放入OPEN表,OPEN表为空表？,把第一个节点(n)从OPEN表移至CLOSED表,是否有后继节点 为目标节点？,扩展n，把n的后继节点放入OPEN表的末端，提供返回节点n的指针,失败,成功,宽度优先算法框图,是,否,是,否,2020/9/15,人工智能导论 - 刘珊,10,3.5 盲目搜索,八数码难题,2020/9/15,人工智能导论 - 刘珊,11,（初始状态）,可以使用的操作：空格左移，空格上移，空格右移，空格下移。 要求应用宽度优先搜索策略寻找从初始状态到目标状态的解路径。,3.5 盲目搜索,1,八数码难题的 宽度优先搜索树,2020/9/15,人工智能导论 -

6、刘珊,12,3.5 盲目搜索,状态空间的深度优先搜索,定义 首先扩展最新产生的(即最深的)节点。 基本思想 从初始节点S0开始，选择最新产生的节点考察扩展，直到找到目标节点为止。 OPEN表中总是将新产生的节点放在OPEN表的前端。,2020/9/15,人工智能导论 - 刘珊,13,3.5 盲目搜索,八数码难题,2020/9/15,人工智能导论 - 刘珊,14,（初始状态）,可以使用的操作：空格左移，空格上移，空格右移，空格下移。 要求应用深度优先搜索策略寻找从初始状态到目标状态的解路径。,3.5 盲目搜索,1,八数码难题的 深度优先搜索树,2020/9/15,人工智能导论 - 刘珊,15,3

7、.5 盲目搜索,状态空间的深度优先搜索,与宽度优先搜索算法比较 步骤基本相同 Open表中的节点排序不同 一种非完备策略 深度限制 防止搜索过程沿着无益的路径扩展下去，给出一个节点扩展的最大深度,2020/9/15,人工智能导论 - 刘珊,16,3.5 盲目搜索,状态空间的等代价搜索,代价树：带有代价边的状态空间图。 定义 宽度优先搜索的一种推广 用g(n1)表示从S0到节点n1的路径的代价，用C(n1, n2)表示从父节点n1到子节点n2的代价，则从S0到节点n2的代价可以表示为： g(n2)=g(n1)+ C(n1, n2),2020/9/15,人工智能导论 - 刘珊,17,3.5 盲目搜

8、索,开始,把S0放入OPEN表,OPEN表为空表？,把具有最小g(i)值的节点i从OPEN表移至CLOSED表,是否为目标节点？,失败,成功,等代价搜索算法框图,是,否,是,否,令g(s)=0,S0是否目标节点？,是,成功,扩展i，计算其后继节点j的g(j)，按由小到大排序，放入OPEN表,否,2020/9/15,人工智能导论 - 刘珊,18,3.5 盲目搜索,城市交通问题,设有5个城市，它们之间的交通线路如下图所示，图中的数字表示两个城市之间的交通费用，即代价。用等代价搜索，求从A市出发到E市，费用最小的交通路线。,2020/9/15,人工智能导论 - 刘珊,19,3.5 盲目搜索,城市交通

9、问题,解：将原网络图转化为代价树：,2020/9/15,人工智能导论 - 刘珊,20,3.5 盲目搜索,与或图搜索,2020/9/15,人工智能导论 - 刘珊,21,3.5 盲目搜索,与或图,概念回顾 终节点 可解节点 不可解节点 有关概念 K连接符 耗散值 解图 最佳解图,2020/9/15,人工智能导论 - 刘珊,22,3.5 盲目搜索,耗散值,Ck为k连接符的路径耗散值，N为目标节点集合，n1 ,n2 ,.ni 为由k连接符连接的i个节点， C(n, N)为节点n到N的耗散值，则： C(n, N) = Ck+C(n1, N)+C(ni, N) 若n属于N，C(n,N)=0 若n是局部图的

10、一个叶节点,则C(n,N)=h(n) 根节点的耗散值为解图的耗散值,2020/9/15,人工智能导论 - 刘珊,23,3.5 盲目搜索,耗散值,假设K连接符的耗散值为K， N=n7, n8 计算C(n0,N),2020/9/15,人工智能导论 - 刘珊,24,与或图的盲目搜索,常用的方法也是深度优先和宽度优先两种基本策略 与或图的一般搜索 从代表原始问题的根节点开始，按一定的规则(归约操作)对当前节点进行与或扩展，并为每个子节点设置指向父节点的指针； 选择适当的子节点进行扩展，多次调用可解标记过程和不可解标记过程，直到根节点被标记为可接或不可解节点为止。,2020/9/15,人工智能导论 -

11、刘珊,25,3.5 盲目搜索,与或图的宽度优先搜索,2020/9/15,人工智能导论 - 刘珊,26,3.5 盲目搜索,实例,下图所示的与或图中，节点按标注顺序进行扩展，其中t1、t2、t3是终止节点， A、B、C为不可解的端节点。,2020/9/15,人工智能导论 - 刘珊,27,3.5 盲目搜索,与或图的深度优先搜索,2020/9/15,人工智能导论 - 刘珊,28,3.5 盲目搜索,第三章 确定性推理,3.1 推理概述 3.2 自然演绎推理 3.3 消解原理 3.4 图搜索概述 3.5 盲目搜索 3.6 启发式搜索,2020/9/15,人工智能导论 - 刘珊,29,启发式搜索,特点 重排

12、OPEN表，选择最有希望的节点加以扩展 类型 A算法、A*算法等 启发式信息 用来加速搜索过程的有关问题领域的特征信息 估价函数 用于评定侯选扩展节点 一般形式：f(n)=g(n)+h(n) 应用估价函数值重排OPEN表,2020/9/15,人工智能导论 - 刘珊,30,g(n)是从初始节点S0到节点n的实际代价；h(n)是从节点n到目标节点Sg的最优路径的估计代价。,3.6 启发式搜索,A算法,搜索中，如果重排OPEN表是依据估计函数f(x)=g(x)+h(x)进行的，则称该过程为A算法。 全局择优搜索：扩展节点时，总是从OPEN表的所有节点中选择。 局部择优搜索：扩展节点时，从刚生成的节点

13、中选择。,2020/9/15,人工智能导论 - 刘珊,31,3.6 启发式搜索,A算法,实质：选择OPEN表上具有最小f值的节点作为下一个要扩展的节点。,2020/9/15,人工智能导论 - 刘珊,32,全局择优搜索A算法框图,3.6 启发式搜索,八数码难题,2020/9/15,人工智能导论 - 刘珊,33,（初始状态）,假设估计函数为f(n)=d(n)+W(n)，d(n)表示节点n在搜索树中的深度，W(n)表示节点n中“不在位”的数码个数。,3.6 启发式搜索,5,7,1,4,5,6,3,2,八数码难题的有序搜索树,2020/9/15,人工智能导论 - 刘珊,34,5,3.6 启发式搜索,估

14、价函数,定义 定义f*(n)=g*(n)+h*(n) ,表示从初始状态经由节点n到达目标节点的所有路径中最小路径代价值。 g*(n)是从初始节点到节点n的最小代价 h*(n)是从节点n到达目标节点的最优路径的代价值，有多个目标节点时取其代价最小者 f*(n)的估价值定义为：f(n)=g(n)+h(n) g是g*的估计 ，h是h*的估计,2020/9/15,人工智能导论 - 刘珊,35,3.6 启发式搜索,几个定义,定义1：如果对所有的x存在h(x)h*(x)，则称h(x)为h*(x)的下界，它表示某种偏于保守的估计。 定义2：采用h*(x)的下界h(x)为启发函数的A算法（全局择优），称为A*

15、算法。 可纳性：如果搜索算法能在有限步内找到一条从初始节点到目标节点的最佳路径，则称该搜索算法是可采纳的。 A*算法是可采纳的。,2020/9/15,人工智能导论 - 刘珊,36,3.6 启发式搜索,A*算法的最优性,设有两个A*算法A1*和A2*，它们有 A1*: f1(n)=g1(n)+h1(n) A2*: f2(n)=g2(n)+h2(n) 如果对所有非目标节点均有 h2(n)h1(n)，则被A2*扩展的节点一定被A1*扩展。,2020/9/15,人工智能导论 - 刘珊,37,3.6 启发式搜索,h(n)的单调限制,如果启发函数满足以下两个条件： h(目标节点)=0 对任意节点n和它的子

16、节点m，都有 0h(n)-h(m) C(n,m)，C(n,m)是节点到其子节点的边代价 则称h(n)满足单调限制。 如果h(n)满足单调限制，则当A*算法扩展节点n时，该节点就已经找到通往它的最佳路径。 如果h(n)满足单调限制，则A*算法扩展的节点序列的f 值是非递减的，即f(ni)f(ni+1),2020/9/15,人工智能导论 - 刘珊,38,3.6 启发式搜索,八数码难题,2020/9/15,人工智能导论 - 刘珊,39,（初始状态）,假设估计函数为f(n)=d(n)+p(n)，d(n)表示节点n在搜索树中的深度，p(n)表示节点n中每个数码与其目标位置之间距离的总和。,3.6 启发式

17、搜索,40,2,5,1,9/15/2020,人工智能导论,3,4,八数码难题h(n)=P(n)的A*算法搜索树,3.6 启发式搜索,2020/9/15,人工智能导论 - 刘珊,与或图的启发式搜索,与或图的启发式搜索同样依赖于评价函数，其形式一般定义为f(n)=g(n)+h(n) 与或图的启发式搜索同样可以用open表和closed表实现，但是open表根据K连接符的耗散值排序， closed表中多了一列“可解性”判别。,2020/9/15,人工智能导论 - 刘珊,41,3.6 启发式搜索,AO* 算法,1、 把初始节点S0放入OPEN表； 2、 移出OPEN表的耗散值最小的K连接符对应的节点N

18、放入CLOSED表，并冠以序号n； 3、 若节点n可扩展，则做下列工作： 扩展n:将其子节点配上指向父节点的指针后放入OPEN表； 可解性判别：考察这些子节点中是否有终止节点。若有，则标记它们为可解节点，并将它们放入CLOSED表，然后由它的可解返回推断其先辈节点的可解性，并对其中的可解节点进行标记。如果初始节点S0也被标记为可解节点，则搜索成功，结束。 删去OPEN表中具有可解先辈的节点，转2步；,2020/9/15,人工智能导论 - 刘珊,42,3.6 启发式搜索,AO* 算法,4 、若n不可扩展，则做下列工作： 不可解判别：标记n为不可解节点，然后由它的不可解返回推断其先辈节点的可解性，并对其中的不可解节点进行标记。如果初始节点S0也被标记为不可解节点，则搜索失败，退出。 删去OPEN表中那些具有不可解先辈的节点（因为其先辈节点已不可解，故已无再考察这些节点的必要），转2步；,2020/9/15,人工智能导论 - 刘珊,43,3.6 启发式搜索,示例,初始节点为n0，目标节点为n7,n8。 任意单步路径耗散恒定为1,2020/9/15,人工智能导论 - 刘珊,44,h(n0)=3 h(n1)=2 h(n2)=4 h(n3)=4 h(n4)=1 h(n5)=1 h(n6)=