湘潭大学 人工智能课件 确定性推理 part4.ppt

1、Artificial Intelligence (AI)人工智能,第二章：知识表示与推理,内容提要,第二章：知识表示与推理,1.推理的基本概念,2.搜索策略,3.自然演绎推理,4.消解演绎推理,5.基于规则的演绎推理,搜索策略,搜索策略 搜索的基本概念 状态空间的搜索策略 与/或树的搜索策略 搜索的完备性与效率,与/或树的搜索策略,与/或树的搜索策略 与/或树的一般搜索过程 与/或树的广度优先搜索 与/或树的深度优先搜索 与/或树的启发式搜索 博弈树的启发式搜索 -剪枝技术,与/或树的启发式搜索,与/或树的启发式搜索 与/或树的启发式搜索过程实际上是一种利用搜索过程所得到的启发性信息寻找最优解

2、树的过程。 算法的每一步都试图找到一个最有希望成为最优解树的子树。 最优解树是指代价最小的那棵解树。 它涉及到解树的代价与希望树。,与/或树的启发式搜索,解树的代价:解树的代价可按如下规则计算 (1)若n为终止节点，则其代价h(n)=0； (2)若n为或节点，且子节点为n1, n2, ,nk，则n的代价为： 其中，c(n, ni)是节点n到其子节点ni的边代价。 (3)若n为与节点，且子节点为n1, n2, ,nk，则n的代价可用和代价法或最大代价法。,与/或树的启发式搜索,解树的代价:解树的代价可按如下规则计算 若用和代价法，则其计算公式为： 若用最大代价法，则其计算公式为： (4)若n是端

3、节点，但又不是终止节点，则n不可扩展，其代价定义为h(n)=。 (5)根节点的代价即为解树的代价。,与/或树的启发式搜索,解树的代价: 设下图是一棵与/或树，它包括两棵解树 左边的解树由S0、A、t1、C及t2组成； 右边的解树由S0、B、t2、D及t4组成。 在此与或树中，t1、t2、t3、t4为终止节点；E、F是端节点；边上的数字是该边的代价。 请计算解树的代价。,与/或树的启发式搜索,解树的代价: 解：先计算左边的解树 按和代价： h(S0)=2+4+6+2=14 按最大代价： h(S0)=(2+6)+2=10 再计算右边的解树 按和代价： h(S0)=1+5+3+2=11 按最大代价：

4、 h(S0)=(1+5)+2=8,与/或树的启发式搜索,希望树：希望树是指搜索过程中最有可能成为最优解树的那棵树。与/或树的启发式搜索过程就是不断地选择、修正希望树的过程，在该过程中，希望树是不断变化的。 希望树的定义： (1) 初始节点S0在希望树T中 (2) 如果节点n在希望树中，则一定有： 如果n是具有子节点n1, n2, , nk的或节点，则具有 值的那个子节点ni也应在T中。 如果n是与节点，则n的全部子节点都在希望树T中。,与/或树的启发式搜索,与/或树的启发式搜索过程 (1) 把初始节点S0放入OPEN表中； (2) 求出希望树T，即根据当前搜索树中节点的代价h求出以S0为根的希

5、望树T； (3) 依次在OPEN表中取出T的端节点放入CLOSED表，并记该节点为n；节点n有三种不同情况：n为终止节点，n不是终止节点，但可扩展，n不是终止节点，且不可扩展，对三种情况分别进行步骤(4) (5) (6)的操作过程；,与/或树的启发式搜索,与/或树的启发式搜索过程 (4)如果节点n为终止节点，则： 标记节点n为可解节点； 在T上应用可解标记过程，对n的先辈节点中的所有可解解节点进行标记； 如果初始解节点S0能够被标记为可解节点，则T就是最优解树，成功退出； 否则，从OPEN表中删去具有可解先辈的所有节点。 转第(2)步。,与/或树的启发式搜索,与/或树的启发式搜索过程 (5)

6、如果节点n不是终止节点，但可扩展，则： 扩展节点n，生成n的所有子节点； 把这些子节点都放入OPEN表中，并为每一个子节点设置指向父节点n的指针； 计算这些子节点及其先辈节点的h值； 转第(2)步。,与/或树的启发式搜索,与/或树的启发式搜索过程 (6) 如果节点n不是终止节点，且不可扩展，则： 标记节点n为不可解节点； 在T上应用不可解标记过程，对n的先辈节点中的所有不可解解节点进行标记； 如果初始解节点S0能够被标记为不可解节点，则问题无解，失败退出； 否则，从OPEN表中删去具有不可解先辈的所有节点。 转第(2)步。,与/或树的启发式搜索,与/或树的启发式搜索： 设初始节点为S0，要求搜

7、索过程每次扩展节点时都同时扩展两层，且按一层或节点、一层与节点的间隔方式进行扩展。 S0经过扩展后得到的与/或树如右图所示。其中，端节点B、C、E、F，下面的数字是用启发函数估算出的h值；各个父节点到其子节点的代价为1。,h(B)=3，h(C)=3 h(E)=3，h(F)=2 按照和代价计算得到： h(A)=8，h(D)=7 h(S0)=8 此时S0的右子树是希望树,与/或树的启发式搜索,与/或树的启发式搜索： 依次对当前希望树的端节点进行扩展。对节点E扩展两层后得到的与/或树如右图所示。节点S0、A、D、E、G、H旁边的数字是按和代价法计算出来的节点代价。 此时，由右子树求出的h(S0)=1

8、2，由左子树求出的h(S0)=9。显然，左子树的代价小。因此，当前的希望树应改为左子树。,由子节点算出的值7代替原来的估计值3,与/或树的启发式搜索,与/或树的启发式搜索： 对节点B进行扩展，扩展两层后得到的与/或树如下图所示。,2,由于节点N和O是可解节点，故调用可解标记过程，得节点L、B也为可解节点，但不能标记S0为可解节点，须继续扩展。当前的希望树仍然是左子树。,与/或树的启发式搜索,与/或树的启发式搜索： 对节点C进行扩展，扩展两层后得到的与/或树如下图所示。,调用可解标记过程，可标记S0为可解节点，这就得到了代价最小的解树。按和代价法，该最优解的代价为9。,搜索策略,搜索策略 搜索的

9、基本概念 状态空间的搜索策略 与/或树的搜索策略 搜索的完备性与效率,搜索的完备性与效率,完备性 对于一类可解的问题和一个搜索过程，如果运用该搜索过程一定能求得该类问题的解，则称该搜索过程为完备的，否则为不完备的。 完备的搜索过程称为“搜索算法”。不完备的搜索过程不是算法，称为“过程”。 广度优先搜索、代价树的广度优先搜索、改进后的有界深度优先搜索以及A*算法都是完备的搜索过程，其它搜索过程都是不完备的。,搜索的完备性与效率,搜索效率 一个搜索过程的搜索效率不仅取决于过程自身的启发能力，而且还与被解问题的有关属性等多种因素有关。 为了比较求解同一问题的不同搜索方法的效率，常用以下两种指标来衡量

10、： 外显率 有效分支因数,搜索的完备性与效率,外显率： 外显率定义为： P=L/T L为从初始节点到目标节点的路径长度； T为整个搜索过程中所生成的节点总数。 外显率反映了搜索过程中从初始节点向目标节点前进时搜索区域的宽度。当T=L时，P=1，表示搜索过程中每次只生成一个节点，它恰好是解路径上的节点，搜索效率最高。P越小表示搜索时产生的无用节点愈多，搜索效率愈低。,搜索的完备性与效率,有效分枝因数： 有效分枝因数B定义为： B+B2+BL=T B是有效分枝因数，它表示在整个搜索过程中每个节点平均生成的子节点数目； L为从初始节点到目标节点的路径长度； T为整个搜索过程中所生成的节点总数。 当B1