1、Artificial Intelligence (AI)人工智能人工智能第二章：知识第二章：知识表示与推理表示与推理内容提要1.1.推理的基本概念推理的基本概念2.2.搜索策略搜索策略3.3.自然演绎推理自然演绎推理4.4.消解演绎推理消解演绎推理5.5.基于规则的演绎推理基于规则的演绎推理搜索策略v搜索策略搜索策略搜索的基本概念搜索的基本概念状态空间的搜索策略状态空间的搜索策略与与/ /或树的搜索策略或树的搜索策略搜索的完备性与效率搜索的完备性与效率与/或树的搜索策略v与与/ /或树的搜索策略或树的搜索策略与与/或树的一般搜索过程或树的一般搜索过程与与/或树的广度优先搜索或树的广度优先搜索与
2、与/或树的深度优先搜索或树的深度优先搜索与与/或树的启发式搜索或树的启发式搜索博弈树的启发式搜索博弈树的启发式搜索-剪枝技术剪枝技术与/或树的启发式搜索v与与/ /或树的启发式搜索或树的启发式搜索与与/ /或树的启发式搜索过程实际上是一种利用搜或树的启发式搜索过程实际上是一种利用搜索过程所得到的启发性信息寻找最优解树的过索过程所得到的启发性信息寻找最优解树的过程。程。算法的每一步都试图找到一个算法的每一步都试图找到一个最有希望成为最最有希望成为最优解树的子树优解树的子树。最优解树最优解树是指代价最小的那棵解树。是指代价最小的那棵解树。它涉及到它涉及到解树的代价解树的代价与与希望树希望树。与/或
3、树的启发式搜索v解树的代价解树的代价: :解树的代价可按如下规则计算解树的代价可按如下规则计算(1)若若n为为终止节点终止节点，则其代价，则其代价h(n)=0；(2)若若n为为或节点或节点，且子节点为，且子节点为n1, n2, ,nk，则，则n的代价的代价为：为： 其中，其中，c(n, ni)是节点是节点n到其子节点到其子节点ni的边代价。的边代价。(3)若若n为为与节点与节点，且子节点为，且子节点为n1, n2, ,nk，则，则n的代价的代价可用可用和代价法和代价法或或最大代价法最大代价法。)(),(min)(1iikinhnncnh与/或树的启发式搜索v解树的代价解树的代价: :解树的代价
4、可按如下规则计算解树的代价可按如下规则计算p若用和代价法，则其计算公式为：若用和代价法，则其计算公式为： p若用最大代价法，则其计算公式为：若用最大代价法，则其计算公式为：(4)若若n是是端节点，但又不是终止节点端节点，但又不是终止节点，则，则n不可扩展，不可扩展，其代价定义为其代价定义为h(n)=。(5)根节点的代价即为解树的代价。根节点的代价即为解树的代价。1()m ax(,)()iiikh nc n nh n 1()(,)()kiiih nc n nh n与/或树的启发式搜索v解树的代价解树的代价: : 设下图是一棵与设下图是一棵与/或树，它包或树，它包括两棵解树括两棵解树 左边的解树由
5、左边的解树由S0、A、t1、C及及t2组成；组成； 右边的解树由右边的解树由S0、B、t2、D及及t4组成。组成。 在此与或树中，在此与或树中，t1、t2、t3、t4为终止节点；为终止节点；E、F是端节是端节点；边上的数字是该边的代点；边上的数字是该边的代价。价。 请计算解树的代价。请计算解树的代价。4 6 3 5S02 2A Bt1 C t2 D2 1t3 E t4 F与/或树的启发式搜索v解树的代价解树的代价: :解：先计算左边的解树解：先计算左边的解树p按和代价：按和代价： h(S0)=2+4+6+2=14p按最大代价：按最大代价： h(S0)=(2+6)+2=10再计算右边的解树再计算
6、右边的解树p按和代价：按和代价： h(S0)=1+5+3+2=11p按最大代价：按最大代价： h(S0)=(1+5)+2=84 6 3 5S02 2A Bt1 C t2 D2 1t3 E t4 F与/或树的启发式搜索v希望树：希望树：希望树是指搜索过程中最有可能成为最优解树希望树是指搜索过程中最有可能成为最优解树的那棵树。与的那棵树。与/ /或树的启发式搜索过程就是不断地或树的启发式搜索过程就是不断地选择、修选择、修正正希望树的过程，在该过程中，希望树的过程，在该过程中，希望树是不断变化的希望树是不断变化的。v希望树的定义：希望树的定义：(1) 初始节点初始节点S0在希望树在希望树T中中 (2
7、) 如果节点如果节点n在希望树中，则一定有：在希望树中，则一定有：p如果如果n是具有子节点是具有子节点n1, n2, , nk的的或节点或节点，则具有，则具有 值的那个子节点值的那个子节点ni也应在也应在T中。中。p如果如果n是是与节点与节点，则，则n的的全部子节点全部子节点都在希望树都在希望树T中。中。 1min( ,)( )iii nc n nh n 与/或树的启发式搜索v与与/ /或树的启发式搜索过程或树的启发式搜索过程(1) 把初始节点把初始节点S0放入放入OPEN表中；表中；(2) 求出希望树求出希望树T，即根据当前搜索树中节点的代价，即根据当前搜索树中节点的代价h求求出以出以S0为
8、根的希望树为根的希望树T； (3) 依次在依次在OPEN表中取出表中取出T的端节点的端节点放入放入CLOSED表，表，并记该节点为并记该节点为n；节点；节点n有三种不同情况：有三种不同情况：n为终止节为终止节点，点，n不是终止节点，但可扩展，不是终止节点，但可扩展，n不是终止节点，不是终止节点，且不可扩展，对三种情况分别进行步骤且不可扩展，对三种情况分别进行步骤(4) (5) (6)的操作的操作过程；过程； 与/或树的启发式搜索v与与/ /或树的启发式搜索过程或树的启发式搜索过程(4)如果节点如果节点n为为终止节点终止节点，则：，则： p标记节点标记节点n为可解节点；为可解节点；p在在T上应用
9、可解标记过程，对上应用可解标记过程，对n的先辈节点中的所的先辈节点中的所有可解解节点进行标记；有可解解节点进行标记；p如果初始解节点如果初始解节点S0能够被标记为可解节点，则能够被标记为可解节点，则T就就是最优解树，成功退出；是最优解树，成功退出；p否则，从否则，从OPEN表中删去具有可解先辈的所有节点。表中删去具有可解先辈的所有节点。 p转第转第(2)步。步。 与/或树的启发式搜索v与与/ /或树的启发式搜索过程或树的启发式搜索过程(5) 如果节点如果节点n不是终止节点，但可扩展，则：不是终止节点，但可扩展，则： p扩展节点扩展节点n，生成，生成n的所有子节点；的所有子节点；p把这些子节点都
10、放入把这些子节点都放入OPEN表中，并为每一个子表中，并为每一个子节点设置指向父节点节点设置指向父节点n的指针；的指针；p计算这些子节点计算这些子节点及其先辈节点及其先辈节点的的h值；值；p转第转第(2)步。步。与/或树的启发式搜索v与与/ /或树的启发式搜索过程或树的启发式搜索过程(6) 如果节点如果节点n不是终止节点，且不可扩展，则：不是终止节点，且不可扩展，则： p标记节点标记节点n为不可解节点；为不可解节点；p在在T上应用不可解标记过程，对上应用不可解标记过程，对n的先辈节点中的的先辈节点中的所有不可解解节点进行标记；所有不可解解节点进行标记；p如果初始解节点如果初始解节点S0能够被标
11、记为不可解节点，则能够被标记为不可解节点，则问题无解，失败退出；问题无解，失败退出；p 否则，从否则，从OPEN表中删去具有不可解先辈的所有表中删去具有不可解先辈的所有节点。节点。 p 转第转第(2)步。步。 与/或树的启发式搜索v与与/ /或树的启发式搜索：或树的启发式搜索： 设初始节点为设初始节点为S0，要求搜索过，要求搜索过程每次扩展节点时都同时扩展程每次扩展节点时都同时扩展两层，且按一层或节点、一层两层，且按一层或节点、一层与节点的间隔方式进行扩展。与节点的间隔方式进行扩展。 S0经过扩展后得到的与经过扩展后得到的与/或树如或树如右图所示。其中，端节点右图所示。其中，端节点B、C、E、
12、F，下面的数字是用启发函，下面的数字是用启发函数数估算估算出的出的h值；值；各个父节点各个父节点到其子节点的代价为到其子节点的代价为1。S0ADBCEF3332h(B)=3，h(C)=3h(E)=3，h(F)=2按照和代价计算得到：按照和代价计算得到：h(A)=8，h(D)=7h(S0)=8此时此时S0的右子树是希望树的右子树是希望树与/或树的启发式搜索v与与/ /或树的启发式搜索：或树的启发式搜索： 依次对依次对当前希望树的端节点当前希望树的端节点进行扩展。对节点进行扩展。对节点E扩展两扩展两层后得到的与层后得到的与/或树如右图所或树如右图所示。节点示。节点S0、A、D、E、G、H旁边的数字
13、是按旁边的数字是按和代价法和代价法计算出来的节点代价。计算出来的节点代价。 此时，由右子树求出的此时，由右子树求出的h(S0)=12，由左子树求出的，由左子树求出的h(S0)=9。显然，左子树的代。显然，左子树的代价小。因此，价小。因此，当前的希望树当前的希望树应改为左子树应改为左子树。S09A8D11BCEF3372322276GH由子节点算出的由子节点算出的值值7 7代替原来的代替原来的估计值估计值3 3与/或树的启发式搜索v与与/ /或树的启发式搜索：或树的启发式搜索： 对节点对节点B进行扩展，扩展两层后进行扩展，扩展两层后得到的与得到的与/或树如下图所示。或树如下图所示。2S09A8D
14、11BCEF337232276LMNOPQ002226GH由于节点由于节点N和和O是可解节点，故调用可解标记过程，得是可解节点，故调用可解标记过程，得节点节点L、B也为可解节点，但不能标记也为可解节点，但不能标记S0为可解节点，为可解节点，须继续扩展。须继续扩展。当前的希望树仍然是左子树当前的希望树仍然是左子树。与/或树的启发式搜索v与与/ /或树的启发式搜索：或树的启发式搜索： 对节点对节点C进行扩展，扩展两层后进行扩展，扩展两层后得到的与得到的与/或树如下图所示。或树如下图所示。S09A8D11BCEF3372322276LMNOPQ002226RST005229GH调用可解标记过程，可标
15、记调用可解标记过程，可标记S0为可解节点，这就得为可解节点，这就得到了代价最小的解树。按和代价法，到了代价最小的解树。按和代价法，该最优解的代该最优解的代价为价为9。 搜索策略v搜索策略搜索策略搜索的基本概念搜索的基本概念状态空间的搜索策略状态空间的搜索策略与与/ /或树的搜索策略或树的搜索策略搜索的完备性与效率搜索的完备性与效率搜索的完备性与效率v完备性完备性对于一类对于一类可解的问题可解的问题和一个搜索过程，如果运和一个搜索过程，如果运用该搜索过程一定能求得该类问题的解，则称用该搜索过程一定能求得该类问题的解，则称该搜索过程为该搜索过程为完备的完备的，否则为，否则为不完备的不完备的。完备的
16、搜索过程称为完备的搜索过程称为“搜索算法搜索算法”。不完备的。不完备的搜索过程不是算法，称为搜索过程不是算法，称为“过程过程”。广度优先搜索、代价树的广度优先搜索、改进广度优先搜索、代价树的广度优先搜索、改进后的有界深度优先搜索以及后的有界深度优先搜索以及A*算法都是完备的算法都是完备的搜索过程，其它搜索过程都是不完备的。搜索过程，其它搜索过程都是不完备的。搜索的完备性与效率v搜索效率搜索效率一个搜索过程的搜索效率不仅取决于过程自身一个搜索过程的搜索效率不仅取决于过程自身的启发能力，而且还与被解问题的有关属性等的启发能力，而且还与被解问题的有关属性等多种因素有关。多种因素有关。为了比较求解同一
17、问题的不同搜索方法的效率，为了比较求解同一问题的不同搜索方法的效率，常用以下两种指标来衡量：常用以下两种指标来衡量：p外显率外显率p有效分支因数有效分支因数搜索的完备性与效率v外显率：外显率：外显率定义为：外显率定义为：P=L/TpL为从初始节点到目标节点的路径长度；为从初始节点到目标节点的路径长度；pT为整个搜索过程中所生成的节点总数。为整个搜索过程中所生成的节点总数。外显率反映了搜索过程中从初始节点向目标节点前进外显率反映了搜索过程中从初始节点向目标节点前进时时搜索区域的宽度搜索区域的宽度。当。当T=L时，时，P=1，表示搜索过程中，表示搜索过程中每次只生成一个节点，它恰好是解路径上的节点
18、，搜每次只生成一个节点，它恰好是解路径上的节点，搜索效率最高。索效率最高。P越小表示搜索时产生的无用节点愈多，越小表示搜索时产生的无用节点愈多，搜索效率愈低。搜索效率愈低。搜索的完备性与效率v有效分枝因数：有效分枝因数：有效分枝因数有效分枝因数B定义为：定义为：B+B2+BL=TpB是有效分枝因数，它表示在整个搜索过程中是有效分枝因数，它表示在整个搜索过程中每个每个节点平均生成的子节点数目节点平均生成的子节点数目；pL为从初始节点到目标节点的路径长度；为从初始节点到目标节点的路径长度；pT为整个搜索过程中所生成的节点总数。为整个搜索过程中所生成的节点总数。当当B1时，时，L=T，此时所生成的节点数最少，搜索效，此时所生成的节点数最少，搜索效率最高。率最高。搜索的完备性与效率v衡量搜索策略性能的准则：衡量搜索策略性能的准则：完备性完备性尽量避免无用搜索。增强搜索的目的性，尽量尽量避免无用搜索。增强搜索的目的性，尽量避免产生及考察那些无用的节点。避免产生及考察那些无用的节点。控制开销小。要求搜索策略实现简单。控制开销小。要求搜索策略实现简单。v显然以上准则很难同时满足。所以，在这些准则显然以上准则很难同时满足。所以，在这些准则之间可以采取折衷的方法，从而使其综合效果比之间可以采取折衷的方法，从而使其综合效果比较好。较好。
