西电人工智能10-确定性推理-part3课件

Artificial Intelligence (AI) 人工智能,主讲：戚玉涛,Email：qi_yutao163.com,第三章：确定性推理,内容提要,第三章：确定性推理,1.推理的基本概念,2.搜索策略,3.自然演绎推理,4.归结演绎推理,5.基于规则的演绎推理,搜索策略,搜索策略 搜索的基本概念 状态空间的搜索策略 与/或树的搜索策略 搜索的完备性与效率,状态空间的搜索策略,状态空间的搜索策略 状态空间搜索的基本思想 图搜索的一般过程 状态空间的盲目搜索 广度优先搜索 深度优先搜索 代价树搜索 状态空间的启发式搜索 启发性信息和估价函数 A算法和A*算法,状态空间的搜索策略,状态空间的搜索策略 状态空间搜索的基本思想 图搜索的一般过程 状态空间的盲目搜索 广度优先搜索 深度优先搜索 代价树搜索 状态空间的启发式搜索 启发性信息和估价函数 A算法和A*算法,A算法,A算法：在图搜索算法中，如果能在搜索的每一步都利用估价函数f(n)=g(n)+h(n)对OPEN表中的节点进行排序，则该搜索算法为A算法。 由于估价函数中带有问题自身的启发性信息，因此，A算法也被称为启发式搜索算法。 A算法的类型：可根据搜索过程中选择扩展节点的范围，将启发式搜索算法分为 全局择优搜索算法： 从OPEN表的所有节点中选择一个估价函数值最小的一个进行扩展。 局部择优搜索算法：仅从刚生成的子节点中选择一个估价函数值最小的一个进行扩展。,A算法,全局择优搜索算法流程 (1)把初始节点S0放入OPEN表，计算f(S0)。 (2)如果OPEN表为空，则问题无解，退出。 (3)把OPEN表的第一个节点（记为节点n）取出放入CLOSED表。 (4)考察节点n是否为目标节点。若是，则求得了问题的解，退出。 (5)若节点n不可扩展，则转第2步。 (6)扩展节点n，用估价函数f(x)计算每个子节点的估价值，并为每一个子节点都配置指向父节点的指针。把这些子节点都送入OPEN表中，然后对OPEN表中的全部节点按估价值从小至大的顺序进行排序，然后转第2步。,A算法,局部择优搜索算法流程 (1) 把初始节点S0放入OPEN表，计算f(S0)。 (2)如果OPEN表为空，则问题无解，退出。 (3)把OPEN表的第一个节点（记为节点n）取出放入CLOSED表。 (4)考察节点n是否为目标节点。若是，则求得了问题的解，退出。 (5)若节点n不可扩展，则转第2步。 (6) 扩展节点n，用估价函数f(x)计算每个子节点的估价值，并按估价值从小到大的顺序放到OPEN表中的首部，并为每一个子节点都配置指向父节点的指针，然后转第2步。,A*算法,A*算法：A*算法是对A算法的估价函数f(n)=g(n)+h(n)加上某些限制后得到的一种启发式搜索算法。 假设f*(n)是从初始节点出发经过节点n达到目标节点的最小代价，估价函数f(n)是对f*(n)的估计值。且 f*(n)=g*(n)+h*(n) g*(n)是从初始节点S0到节点n的最小代价。 h*(n)是从节点n到目标节点的最小代价，若有多个目标节点，则为其中最小的一个。,A*算法,A*算法：A*算法对A算法（全局择优的启发式搜索算法）中的g(n)和h(n)分别提出如下限制： 第一，g(n)是对最小代价g*(n)的估计，且g(n)0； 第二，h(n)是最小代价h*(n)的下界，即对任意节点n均有h(n)h*(n)。 即：满足上述两条限制的A算法称为A*算法。,A*算法,在A*算法中， g(n)比较容易得到，它实际上就是从初始节点S0到节点n的路径代价，恒有： g(n) g*(n) 在算法执行过程中，随着更多搜索信息的获得， g(n)呈下降的趋势。 如右图的例子： 对S0扩展后g(n1)=3， g(n2)=7 对n1扩展后g(n2)=6， g(n3)=5,A*算法,A*算法的可纳性： 可纳性的含义：对任一状态空间图，当从初始节点到目标节点有路经存在时，如果搜索算法总能在有限步骤内找到一条从初始节点到目标节点的最佳路径，并在此路径上结束，则称该搜索算法是可纳的。 A*算法是可纳的，即它能在有限步内终止，并找到问题的最优解。 证明：,A*算法,A*算法的可纳性证明： 第一步：对于有限图， A*算法一定会在有限步骤内终止。 第二步：对于无限图，如果从初始节点S0到目标节点Sg有路径存在，则A*算法也必然会终止。 第三步： A*算法一定终止在最优路径上。,A*算法,证明： A*算法一定终止在最优路径上。 假设最优路径存在，记为S0, x1, x2, ., xm, Sg* 由于A*算法中的h(n)满足 h(n)h*(n)，则： f (S0), f(x1), f (x2) , ., f(xm) 均不大于, f( Sg*)， f( Sg*)= f* ( S0) 在A*算法结束之前，OPEN表中必然存在最优路径S0, x1, x2, ., xm, Sg*中的一些节点，记x'为其中最前面一个，则f( x') f* ( S0)。 假设：A*算法不是终止在最优路径上，而是在某个目标节点t处终止，则有f(t)= g(t) f* ( S0)。 此时有f( x') f(t)，按照A*算法的规则，应该选择x'进行扩展，而不会选择t。与假设矛盾,A*算法,A*算法的最优性： h(n)的确定依赖于具体问题领域的启发性信息，其中h(n) h*(n)的限制是十分重要的，它可以保证A*算法能找到问题的最优解。 A*算法的搜索效率很大程度上取决于估价函数h(n)。一般来说，在满足h(n) h*(n)的前提下，h(n)的值越大越好。h(n)的值越大，说明它携带的启发性信息越多，A*算法搜索时扩展的节点就越少，搜索效率就越高。,A*算法,h(n)的单调限制 在A*算法中，每当扩展一个节点n时，都需要检查其子节点是否已在OPEN表或CLOSED表中。 对已在OPEN表中的子节点，需要决定是否调整指向其父节点的指针； 对已在CLOSED表中的子节点，除需要决定是否调整其指向父节点的指针外，还需要决定是否调整其子节点的后继节点的父指针。 如果能够保证，每当扩展一个节点时就已经找到了通往这个节点的最佳路径，就没有必要再去作上述检查。,A*算法,h(n)的单调限制 为能够保证，每当扩展一个节点时就已经找到了通往这个节点的最佳路径，我们需要对启发函数h(n)增加单调性限制。 如果启发函数满足以下两个条件: (1) h(Sg)=0; (2) 对任意节点ni及其任一子节点nj，都有 0h(ni)-h(nj)c(ni, nj) 其中c(ni, nj)是ni到其子节点nj的边代价，则称h(n)满足单调限制。,A*算法,如果h(n)满足单调条件，则当A*算法扩展节点n时，该节点就已经找到了通往它的最佳路径，即g(n)= g*( n)。 证明：设A*正要扩展节点n，而节点序列S0=n0, n1, ,nk=n是由初始节点S0到节点n的最佳路径。其中，ni是这个序列中最后一个位于CLOSED表中的节点，则上述节点序列中的ni+1节点必定在OPEN表中，由h(n)的单调条件可知： g*(ni)+h(ni)g*(ni) +c(ni, ni+1) +h(ni+1) 所以： g*(ni)+h(ni)g*( ni+1) +h(ni+1) 依此类推可得：g*( ni+1)+h(ni+1)g*( nk) +h(nk)=g*(n)+h(n) 由于节点ni+1在最佳路径上，故有 f(ni+1)g*(n)+h(n) 因为这时A*扩展节点n而不扩展节点ni+1，则有： f(n)=g(n)+h(n)f( ni+1)g*(n)+h(n) 即g(n)g*(n)。g*(n)是最小代价值，所以有g(n)=g*(n),最佳路径上的节点,A*算法,如果h(n)满足单调限制，则A*算法扩展的节点序列的f 值是非递减的，即f(ni)f(ni+1)。 证明：假设节点ni+1在节点ni之后立即扩展，由单调限制条件可知：h(ni)-h(ni+1)c(ni, ni+1) 即：(f(ni)-g(ni)-(f(ni+1)-g(ni+1)c(ni, ni+1) 亦即：f(ni)-g(ni)-f(ni+1)+g(ni)+c(ni, ni+1)c(ni, ni+1) 所以：f(ni)-f(ni+1)0 即：f(ni)f(ni+1) 以上两个定理都是在h(n)满足单调性限制的前提下才成立的。如果h(n)不满足单调性限制，则它们不一定成立。,A*算法,A*算法应用： 八数码难题 f(n)=g(n)+h(n) g(n) 深度 h(n)与目标距离 f*=g*+h*,f(n)=g(n)+h(n) g(n) 深度 h(n)与目标距离 f*=g*+h*,搜索策略,搜索策略 搜索的基本概念 状态空间的搜索策略 与/或树的搜索策略 搜索的完备性与效率,与/或树的搜索策略,与/或树的搜索策略 与/或树的一般搜索过程 与/或树的广度优先搜索 与/或树的深度优先搜索 与/或树的启发式搜索 博弈树的启发式搜索 -剪枝技术,与/或树的搜索策略,与/或树的搜索策略 与/或树的一般搜索过程 与/或树的广度优先搜索 与/或树的深度优先搜索 与/或树的启发式搜索 博弈树的启发式搜索 -剪枝技术,与/或树的一般搜索过程,与/或树的搜索策略： 用与/或树方法求解问题时，首先要定义问题的描述方法，及分解或变换问题的算符，然后就用它们通过搜索生成与/或树，从而求得原始问题的解。 在与/或树中，一个节点是否为可解节点是由它的子节点确定的。由可解/不可解子节点来确定父节点、祖父节点等为可解/不可解节点的过程成为可解/不可解标记过程。 与/或树的搜索过程是反复调用可解/不可解标记过程，直到初始节点（原始问题）被标记为可解/不可解节点为止。,与/或树的一般搜索过程,与/或树的一般搜索过程如下： (1) 把原始问题作为初始节点S0，并把它作为当前节点； (2) 应用分解或等价变换操作对当前节点进行扩展； (3) 为每个子节点设置指向父节点的指针； (4) 选择合适的子节点作为当前节点，反复执行第(2)步和第(3)步，在此期间需要多次调用可解标记过程或不可解标记过程，直到初始节点被标记为可解节点或不可解节点为止。 上述搜索过程将形成一棵与/或树，这种由搜索过程所形成的与/或树称为搜索树。,与/或树的搜索策略,与/或树的搜索策略 与/或树的一般搜索过程 与/或树的广度优先搜索 与/或树的深度优先搜索 与/或树的启发式搜索 博弈树的启发式搜索 -剪枝技术,与/或树的广度优先搜索,与/或树的广度优先搜索： 与/或树的广度优先搜索与状态空间的广度优先搜索的主要差别是，需要在搜索过程中需要多次调用可解标识过程或不可解标识过程。 与/或树的广度优先搜索算法如下： (1)把初始节点S0放入OPEN表中； (2)把OPEN表的第一个节点取出放入CLOSED表，并记该节点为n； (3)如果节点n可扩展，则做下列工作：,与/或树的广度优先搜索, 扩展节点n，将其子节点放入OPEN表的尾部，并为每一个子节点设置指向父节点的指针； 考察这些子节点中有否终止节点。若有，则标记这些终止节点为可解节点，并用可解标记过程对其父节点及先辈节点中的可解解节点进行标记。如果初始解节点S0能够被标记为可解节点，就得到了解树，搜索成功，退出搜索过程；如果不能确定S0为可解节点，则从OPEN表中删去具有可解先辈的节点。 转第(2)步。,与/或树的广度优先搜索,(4) 如果节点n不可扩展，则作下列工作： 标记节点n为不可解节点； 应用不可解标记过程对节点n的先辈中不可解解的节点进行标记。如果初始解节点S0也被标记为不可解节点，则搜索失败，表明原始问题无解，退出搜索过程；如果不能确定S0为不可解节点，则从Open表中删去具有不可解先辈的节点。 转第(2)步。,与/或树的广度优先搜索,与/或树的广度优先搜索的例子: 设有下图所示的与/或树，节点按标注顺