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

西安电子科技大学ArtificialIntelligence(AI)人工智能主讲：戚玉涛Email：[e-mail]第三章：确定性推理西安电子科技大学内容提要第三章：确定性推理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的代价可用和代价法或最大代价法。)(),(min)(1iikinhnncnh西安电子科技大学与/或树的启发式搜索解树的代价:解树的代价可按如下规则计算若用和代价法，则其计算公式为：若用最大代价法，则其计算公式为：(4)若n是端节点，但又不是终止节点，则n不可扩展，其代价定义为h(n)=∝。(5)根节点的代价即为解树的代价。1()max(,)()iiikhncnnhn1()(,)()kiiihncnnhn西安电子科技大学与/或树的启发式搜索解树的代价:设下图是一棵与/或树，它包括两棵解树左边的解树由S0、A、t1、C及t2组成；右边的解树由S0、B、t2、D及t4组成。在此与或树中，t1、t2、t3、t4为终止节点；E、F是端节点；边上的数字是该边的代价。请计算解树的代价。4635S022ABt1Ct2D21t3Et4F西安电子科技大学与/或树的启发式搜索解树的代价:解：先计算左边的解树按和代价：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=84635S022ABt1Ct2D21t3Et4F西安电子科技大学与/或树的启发式搜索希望树：希望树是指搜索过程中最有可能成为最优解树的那棵树。与/或树的启发式搜索过程就是不断地选择、修正希望树的过程，在该过程中，希望树是不断变化的。希望树的定义：(1)初始节点S0在希望树T中(2)如果节点n在希望树中，则一定有：如果n是具有子节点n1,n2,…,nk的或节点，则具有值的那个子节点ni也应在T中。如果n是与节点，则n的全部子节点都在希望树T中。1min(,)()iiincnnhn西安电子科技大学与/或树的启发式搜索与/或树的启发式搜索过程(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。S0ADBCEF3332h(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。显然，左子树的代价小。因此，当前的希望树应改为左子树。S09A8D11BCEF3372322276GH西安电子科技大学与/或树的启发式搜索与/或树的启发式搜索：对节点B进行扩展，扩展两层后得到的与/或树如下图所示。2S09A8D11BCEF337232276LMNOPQ002226GH由于节点N和O是可解节点，故调用可解标记过程，得节点L、B也为可解节点，但不能标记S0为可解节点，须继续扩展。当前的希望树仍然是左子树。西安电子科技大学与/或树的启发式搜索与/或树的启发式搜索：对节点C进行扩展，扩展两层后得到的与/或树如下图所示。S09A8D11BCEF3372322276LMNOPQ002226RST005229GH调用可解标记过程，可标记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西安电子科技大学博弈树的启发式搜索一子棋的极大极小搜索S01S1S2S3-16-5=15-5=06-5=15-5=04-5=-15-4=16-4=25-6=-15-5=05-6=-16-6=04-6=-2S4S5-21MAX节点MAX节点MIN节点西安电子科技大学与/或树的搜索策略与/或树的搜索策略与/或树的一般搜索过程与/或树的广度优先搜索与/或树的深度优先搜索与/或树的启发式搜索博弈树的启发式搜索α-β剪枝技术西安电子科技大学α-β剪枝技术剪枝的概念：极大极小过程是先生成与/或树，然后再计算各节点的估值，这种生成节点和计算估值相分离的搜索方式，需要生成规定深度内的所有节点，因此搜索效率较低。鉴于博弈树具有“与”节点和“或”节点逐层交替出现的特点，如果能边生成节点边对节点估值，就有可能删去一些不必要的节点，从而减少搜索及计算的工作量。例如：S0S452S1S2S33S5S63西安电子科技大学α-β剪枝技术α-β剪枝方法(1)MAX节点的α值为当前子节点的最大到推值；(2)MIN节点的β值为当前子节点的最小倒推值；(3)α-β剪枝的规则如下：任何MAX节点n的α值如果不能降低其父节点的β值，则n以下的分枝可停止搜索，并令节点n的倒推值为α。这种剪枝称为β剪枝。任何MIN节点n的β值如果不能升高其父节点的α值，则n以下的分枝可停止搜索，并令节点n的倒推值为β。这种剪枝称为α剪枝。西安电子科技大学α-β剪枝技术α-β剪枝的例子：≥4S0≤4A≦0≥4≥5≥0CDE0-6×IJ4≦1KLN461×FG5P58H×M8β值α值β值α值QR×≤0≦-6S××在α-β剪枝技术中：对于一个MAX节点，如果估值最高的子节点最先生成，或者对于一个MIN节点，如果估值最低的子节点最先生成，则被剪除的节点数最多，搜索效率最高。这称为最优α-β剪枝西安电子科技大学搜索策略搜索策略搜索的基本概念状态空间的搜索策略与/或树的搜索策略搜索的完备性与效率西安电子科技大学搜索的完备性与效率完备性对于一类可解的问题和一个搜索过程，如果运用该搜索过程一定能求得该类问题的解，则称该搜索过程为完备的，否则为不完备的。完备的搜索过程称为“搜索算法”。不完备的搜索过程不是算法，称为“过程”。广度优先搜索、代价树的广度