西电人工智能11确定性推理part4

ArtificialIntelligence(AI)人工智能,主讲：戚玉涛,Email：qi_yutao,第三章：确定性推理,内容提要,第三章：确定性推理,1.推理的基本概念,2.搜索策略,3.自然演绎推理,4.归结演绎推理,5.基于规则的演绎推理,搜索策略,搜索策略搜索的基本概念状态空间的搜索策略与/或树的搜索策略搜索的完备性与效率,与/或树的搜索策略,与/或树的搜索策略与/或树的一般搜索过程与/或树的广度优先搜索与/或树的深度优先搜索与/或树的启发式搜索博弈树的启发式搜索-剪枝技术,与/或树的启发式搜索,与/或树的启发式搜索与/或树的启发式搜索过程实际上是一种利用搜索过程所得到的启发性信息寻找最优解树的过程。算法的每一步都试图找到一个最有希望成为最优解树的子树。最优解树是指代价最小的那棵解树。它涉及到解树的代价与希望树。,与/或树的启发式搜索,解树的代价:解树的代价可按如下规则计算(1)若n为终止节点，则其代价h(n)=0；(2)若n为或节点，且子节点为n1,n2,nk，则n的代价为：其中，c(n,ni)是节点n到其子节点ni的边代价。(3)若n为与节点，且子节点为n1,n2,nk，则n的代价可用和代价法或最大代价法。,与/或树的启发式搜索,解树的代价:解树的代价可按如下规则计算若用和代价法，则其计算公式为：若用最大代价法，则其计算公式为：(4)若n是端节点，但又不是终止节点，则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按最大代价：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为根的希望树T；(3)依次在OPEN表中取出T的端节点放入CLOSED表，并记该节点为n；节点n有三种不同情况：n为终止节点，n不是终止节点，但可扩展，n不是终止节点，且不可扩展，对三种情况分别进行步骤(4)(5)(6)的操作过程；,与/或树的启发式搜索,与/或树的启发式搜索过程(4)如果节点n为终止节点，则：标记节点n为可解节点；在T上应用可解标记过程，对n的先辈节点中的所有可解解节点进行标记；如果初始解节点S0能够被标记为可解节点，则T就是最优解树，成功退出；否则，从OPEN表中删去具有可解先辈的所有节点。转第(2)步。,与/或树的启发式搜索,与/或树的启发式搜索过程(5)如果节点n不是终止节点，但可扩展，则：扩展节点n，生成n的所有子节点；把这些子节点都放入OPEN表中，并为每一个子节点设置指向父节点n的指针；计算这些子节点及其先辈节点的h值；转第(2)步。,与/或树的启发式搜索,与/或树的启发式搜索过程(6)如果节点n不是终止节点，且不可扩展，则：标记节点n为不可解节点；在T上应用不可解标记过程，对n的先辈节点中的所有不可解解节点进行标记；如果初始解节点S0能够被标记为不可解节点，则问题无解，失败退出；否则，从OPEN表中删去具有不可解先辈的所有节点。转第(2)步。,与/或树的启发式搜索,与/或树的启发式搜索：设初始节点为S0，要求搜索过程每次扩展节点时都同时扩展两层，且按一层或节点、一层与节点的间隔方式进行扩展。它实际上就是下一节将要讨论的博弈树的结构。S0经过扩展后得到的与/或树如右图所示。其中，端节点B、C、E、F，下面的数字是用启发函数估算出的h值；各个父节点到其子节点的代价为1。,h(B)=3，h(C)=3h(E)=3，h(F)=2按照和代价计算得到：h(A)=8，h(D)=7h(S0)=8此时S0的右子树是希望树,与/或树的启发式搜索,与/或树的启发式搜索：依次对当前希望树的端节点进行扩展。对节点E扩展两层后得到的与/或树如右图所示。节点S0、A、D、E、G、H旁边的数字是按和代价法计算出来的节点代价。此时，由右子树求出的h(S0)=12，由左子树求出的h(S0)=9。显然，左子树的代价小。因此，当前的希望树应改为左子树。,与/或树的启发式搜索,与/或树的启发式搜索：对节点B进行扩展，扩展两层后得到的与/或树如下图所示。,2,由于节点N和O是可解节点，故调用可解标记过程，得节点L、B也为可解节点，但不能标记S0为可解节点，须继续扩展。当前的希望树仍然是左子树。,与/或树的启发式搜索,与/或树的启发式搜索：对节点C进行扩展，扩展两层后得到的与/或树如下图所示。,调用可解标记过程，可标记S0为可解节点，这就的到了代价最小的解树。按和代价法，该最优解的代价为9。,与/或树的搜索策略,与/或树的搜索策略与/或树的一般搜索过程与/或树的广度优先搜索与/或树的深度优先搜索与/或树的启发式搜索博弈树的启发式搜索-剪枝技术,博弈树的启发式搜索,博弈的概念：博弈是一类具有智能行为的竞争活动，如下棋、战争等。博弈的类型：双人完备信息博弈：两位选手对垒，轮流走步，每一方不仅知道对方已经走过的棋步，而且还能估计出对方未来的走步。机遇性博弈：存在不可预测性的博弈，例如掷币等。博弈树若把双人完备信息博弈过程用图表示出来，就得到一棵与/或树，这种与/或树被称为博弈树。,博弈树的启发式搜索,博弈树在双人完备信息博弈中，若将两位对垒选手分别记为MAX和MIN，则博弈树中，下一步该MAX走步的节点称为MAX节点，该MIN走步的节点称为MIN节点。博弈树的特点：(1)博弈的初始状态是初始节点；(2)博弈树中的“或”节点和“与”节点逐层交替出现；(3)整个博弈过程始终站在某一方的立场上。所有能使自己一方获胜的终局都是本原问题，相应的节点是可解节点；所有使对方获胜的终局都是不可解节点。,博弈树的启发式搜索,极大极小分析法对简单的博弈问题，可生成整个博弈树，找到必胜的策略。对于复杂的博弈问题，不可能生成整个搜索树，如国际象棋，大约有10120个节点。一种可行的方法是用当前正在考察的节点生成一棵部分博弈树，并利用估价函数f(n)对叶节点进行静态估值。对叶节点的估值方法：那些对MAX有利的节点，其估价函数取正值那些对MIN有利的节点，其估价函数取负值那些使双方均等的节点，其估价函数取接近于0的值,博弈树的启发式搜索,极大极小分析法对非叶节点的估值方法：必须从叶节点开始向上倒推对于MAX节点，由于MAX方总是选择估值最大的走步，因此，MAX节点的倒推值应该取其后继节点估值的最大值。对于MIN节点，由于MIN方总是选择使估值最小的走步，因此MIN节点的倒推值应取其后继节点估值的最小值。这样一步一步的计算倒推值，直至求出初始节点的倒推值为止。这一过程称为极大极小过程。,博弈树的启发式搜索,博弈树的例子：一子棋游戏设有一个三行三列的棋盘，如下图所示，两个棋手轮流走步，每个棋手走步时往空格上摆一个自己的棋子，谁先使自己的棋子成三子一线为赢。设MAX方的棋子用标记，MIN方的棋子用标记，并规定MAX方先走步。,一子棋棋盘棋局1,博弈树的启发式搜索,博弈树的例子：一子棋游戏解：定义估价函数：e(P)=e(+P)-e(-P)e(+P)：P上有可能使成三子为一线的数目；e(-P)：P上有可能使成三子为一线的数目；当MAX必胜时，e(P)为正无穷大当MIN必胜时，e(P)为负无穷大具有对称性的棋盘可认为是同一棋盘，例如：,e(P)=e(+P)-e(-P)=5-4=1,博弈树的启发式搜索,一子棋的极大极小搜索,MAX节点,MAX节点,MIN节点,与/或树的搜索策略,与/或树的搜索策略与/或树的一般搜索过程与/或树的广度优先搜索与/或树的深度优先搜索与/或树的启发式搜索博弈树的启发式搜索-剪枝技术,-剪枝技术,剪枝的概念：极大极小过程是先生成与/或树，然后再计算各节点的估值，这种生成节点和计算估值相分离的搜索方式，需要生成规定深度内的所有节点，因此搜索效率较低。鉴于博弈树具有“与”节点和“或”节点逐层交替出现的特点，如果能边生成节点边对节点估值，就有可能删去一些不必要的节点，从而减少搜索及计算的工作量。例如：,-剪枝技术,-剪枝方法(1)MAX节点的值为当前子节点的最大到推值；(2)MIN节点的值为当前子节点的最小倒推值；(3)-剪枝的规则如下：任何MAX节点n的值如果不能降低其父节点的值，则n以下的分枝可停止搜索，并令节点n的倒推值为。这种剪枝称为剪枝。任何MIN节点n的值如果不能升高其父节点的值，则n以下的分枝可停止搜索，并令节点n的倒推值为。这种剪枝称为剪枝。,-剪枝技术,-剪枝的例子：,在-剪枝技术中：对于一个MAX节点，如果估值最高的子节点最先生成，或者对于一个MIN节点，如果估值最低的子节点最先生成，则被剪除的节点数最多，搜索效率最高。这称为最优-剪枝,搜索策略,搜索策略搜索的基本概念状态空间的搜索策略与/或树的搜索策略搜索的完备性与效率,搜索的完备性与效率,完备性对于一类可解的问题和一个搜索过程，如果运用该搜索过程一定能求得该类问题的解，则称该搜索过程为完备的，否则为不完备的。完备的搜索过程称为“搜索算法”。不完备的搜索过程不是算法，称为“过程”。广度优先搜索、代价树的广度优先搜索、改进后的有界深度优先搜索以及A*算法都是完备的搜索过程，其它搜索过程都是不完备的。,搜索的完备性与效率,搜索效率一个搜索过程的搜索效率不仅取决于过程自身的启发能力，而且还与被解问题的有关属性等多种因素有关。为了比较求解同一问题的不同搜索方法的效率，常用以下两种指标来衡量：外显率有效分支因数,搜索的完备性与效率,外显率：外显率定义为：P=L/TL为从初始节点到目标节点的路径长度；T为整个搜索过程中所生成的节点总数。外显率反映了搜索过程中从初始节点向目标节点前进时搜索区域的宽度。当T=L时，P=1，表示搜索过程中每次只生成一个节点，它恰好是解路径上的节点，搜索效率最高。P越小表示搜索时产生的无用节点愈多，搜索效率愈低。,搜索的完备性与效率,有效分枝因数：有效分枝因数B定义为