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

1、西安电子科技大学西安电子科技大学Artificial Intelligence (AI)人工智能人工智能主讲：戚玉涛Email：qi_第三章：确定性推理西安电子科技大学西安电子科技大学内容提要1.1.推理的基本概念推理的基本概念2.2.搜索策略搜索策略3.3.自然演绎推理自然演绎推理4.4.归结演绎推理归结演绎推理5.5.基于规则的演绎推理基于规则的演绎推理西安电子科技大学西安电子科技大学搜索策略v搜索策略搜索策略搜索的基本概念搜索的基本概念状态空间的搜索策略状态空间的搜索策略与与/ /或树的搜索策略或树的搜索策略搜索的完备性与效率搜索的完备性与效率西安电子科技大学西安电子科技大学与/或树的搜

2、索策略v与与/ /或树的搜索策略或树的搜索策略与与/或树的一般搜索过程或树的一般搜索过程与与/或树的广度优先搜索或树的广度优先搜索与与/或树的深度优先搜索或树的深度优先搜索与与/或树的启发式搜索或树的启发式搜索博弈树的启发式搜索博弈树的启发式搜索-剪枝技术剪枝技术西安电子科技大学西安电子科技大学与/或树的启发式搜索v与与/ /或树的启发式搜索或树的启发式搜索与与/ /或树的启发式搜索过程实际上是一种利用搜或树的启发式搜索过程实际上是一种利用搜索过程所得到的启发性信息寻找最优解树的过索过程所得到的启发性信息寻找最优解树的过程。程。算法的每一步都试图找到一个算法的每一步都试图找到一个最有希望成为最

3、最有希望成为最优解树的子树优解树的子树。最优解树最优解树是指代价最小的那棵解树。是指代价最小的那棵解树。它涉及到它涉及到解树的代价解树的代价与与希望树希望树。西安电子科技大学西安电子科技大学与/或树的启发式搜索v解树的代价解树的代价: :解树的代价可按如下规则计算解树的代价可按如下规则计算(1)若若n为为终止节点终止节点，则其代价，则其代价h(n)=0；(2)若若n为为或节点或节点，且子节点为，且子节点为n1, n2, ,nk，则，则n的代价的代价为：为： 其中，其中，c(n, ni)是节点是节点n到其子节点到其子节点ni的边代价。的边代价。(3)若若n为为与节点与节点，且子节点为，且子节点为

4、n1, n2, ,nk，则，则n的代价的代价可用可用和代价法和代价法或或最大代价法最大代价法。)(),(min)(1iikinhnncnh西安电子科技大学西安电子科技大学与/或树的启发式搜索v解树的代价解树的代价: :解树的代价可按如下规则计算解树的代价可按如下规则计算p若用和代价法，则其计算公式为：若用和代价法，则其计算公式为： p若用最大代价法，则其计算公式为：若用最大代价法，则其计算公式为：(4)若若n是是端节点，但又不是终止节点端节点，但又不是终止节点，则，则n不可扩展，不可扩展，其代价定义为其代价定义为h(n)=。(5)根节点的代价即为解树的代价。根节点的代价即为解树的代价。1()m

5、 ax(,)()iiikh nc n nh n 1()(,)()kiiih nc n nh n西安电子科技大学西安电子科技大学与/或树的启发式搜索v解树的代价解树的代价: : 设下图是一棵与设下图是一棵与/或树，它包或树，它包括两棵解树括两棵解树 左边的解树由左边的解树由S0、A、t1、C及及t2组成；组成； 右边的解树由右边的解树由S0、B、t2、D及及t4组成。组成。 在此与或树中，在此与或树中，t1、t2、t3、t4为终止节点；为终止节点；E、F是端节是端节点；边上的数字是该边的代点；边上的数字是该边的代价。价。 请计算解树的代价。请计算解树的代价。4 6 3 5S02 2A Bt1 C

6、 t2 D2 1t3 E t4 F西安电子科技大学西安电子科技大学与/或树的启发式搜索v解树的代价解树的代价: :解：先计算左边的解树解：先计算左边的解树p按和代价：按和代价： h(S0)=2+4+6+2=14p按最大代价：按最大代价： h(S0)=(2+6)+2=10再计算右边的解树再计算右边的解树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希望树：希望树：希望树是指搜索过程中最有可能成为最优解树希

7、望树是指搜索过程中最有可能成为最优解树的那棵树。与的那棵树。与/ /或树的启发式搜索过程就是不断地或树的启发式搜索过程就是不断地选择、修选择、修正正希望树的过程，在该过程中，希望树的过程，在该过程中，希望树是不断变化的希望树是不断变化的。v希望树的定义：希望树的定义：(1) 初始节点初始节点S0在希望树在希望树T中中 (2) 如果节点如果节点n在希望树中，则一定有：在希望树中，则一定有：p如果如果n是具有子节点是具有子节点n1, n2, , nk的的或节点或节点，则具有，则具有 值的那个子节点值的那个子节点ni也应在也应在T中。中。p如果如果n是是与节点与节点，则，则n的的全部子节点全部子节点

8、都在希望树都在希望树T中。中。 1min( ,)( )iii nc n nh n 西安电子科技大学西安电子科技大学与/或树的启发式搜索v与与/ /或树的启发式搜索过程或树的启发式搜索过程(1) 把初始节点把初始节点S0放入放入OPEN表中；表中；(2) 求出希望树求出希望树T，即根据当前搜索树中节点的代价，即根据当前搜索树中节点的代价h求求出以出以S0为根的希望树为根的希望树T； (3) 依次在依次在OPEN表中取出表中取出T的端节点的端节点放入放入CLOSED表，表，并记该节点为并记该节点为n；节点；节点n有三种不同情况：有三种不同情况：n为终止节为终止节点，点，n不是终止节点，但可扩展，不

9、是终止节点，但可扩展，n不是终止节点，不是终止节点，且不可扩展，对三种情况分别进行步骤且不可扩展，对三种情况分别进行步骤(4) (5) (6)的操作的操作过程；过程； 西安电子科技大学西安电子科技大学与/或树的启发式搜索v与与/ /或树的启发式搜索过程或树的启发式搜索过程(4)如果节点如果节点n为为终止节点终止节点，则：，则： p标记节点标记节点n为可解节点；为可解节点；p在在T上应用可解标记过程，对上应用可解标记过程，对n的先辈节点中的所的先辈节点中的所有可解解节点进行标记；有可解解节点进行标记；p如果初始解节点如果初始解节点S0能够被标记为可解节点，则能够被标记为可解节点，则T就就是最优解

10、树，成功退出；是最优解树，成功退出；p否则，从否则，从OPEN表中删去具有可解先辈的所有节点。表中删去具有可解先辈的所有节点。 p转第转第(2)步。步。 西安电子科技大学西安电子科技大学与/或树的启发式搜索v与与/ /或树的启发式搜索过程或树的启发式搜索过程(5) 如果节点如果节点n不是终止节点，但可扩展，则：不是终止节点，但可扩展，则： p扩展节点扩展节点n，生成，生成n的所有子节点；的所有子节点；p把这些子节点都放入把这些子节点都放入OPEN表中，并为每一个子表中，并为每一个子节点设置指向父节点节点设置指向父节点n的指针；的指针；p计算这些子节点及其先辈节点的计算这些子节点及其先辈节点的h

11、值；值；p转第转第(2)步。步。西安电子科技大学西安电子科技大学与/或树的启发式搜索v与与/ /或树的启发式搜索过程或树的启发式搜索过程(6) 如果节点如果节点n不是终止节点，且不可扩展，则：不是终止节点，且不可扩展，则： p标记节点标记节点n为不可解节点；为不可解节点；p在在T上应用不可解标记过程，对上应用不可解标记过程，对n的先辈节点中的的先辈节点中的所有不可解解节点进行标记；所有不可解解节点进行标记；p如果初始解节点如果初始解节点S0能够被标记为不可解节点，则能够被标记为不可解节点，则问题无解，失败退出；问题无解，失败退出；p 否则，从否则，从OPEN表中删去具有不可解先辈的所有表中删去

12、具有不可解先辈的所有节点。节点。 p 转第转第(2)步。步。 西安电子科技大学西安电子科技大学与/或树的启发式搜索v与与/ /或树的启发式搜索：或树的启发式搜索： 设初始节点为设初始节点为S0，要求搜索过，要求搜索过程每次扩展节点时都同时扩展程每次扩展节点时都同时扩展两层，且按一层或节点、一层两层，且按一层或节点、一层与节点的间隔方式进行扩展。与节点的间隔方式进行扩展。它实际上就是下一节将要讨论它实际上就是下一节将要讨论的博弈树的结构的博弈树的结构。 S0经过扩展后得到的与经过扩展后得到的与/或树如或树如右图所示。其中，端节点右图所示。其中，端节点B、C、E、F，下面的数字是用启发函，下面的数

13、字是用启发函数估算出的数估算出的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旁边的数字是

14、按和代价法旁边的数字是按和代价法计算出来的节点代价。计算出来的节点代价。 此时，由右子树求出的此时，由右子树求出的h(S0)=12，由左子树求出的，由左子树求出的h(S0)=9。显然，左子树的代。显然，左子树的代价小。因此，价小。因此，当前的希望树当前的希望树应改为左子树应改为左子树。S09A8D11BCEF3372322276GH西安电子科技大学西安电子科技大学与/或树的启发式搜索v与与/ /或树的启发式搜索：或树的启发式搜索： 对节点对节点B进行扩展，扩展两层后进行扩展，扩展两层后得到的与得到的与/或树如下图所示。或树如下图所示。2S09A8D11BCEF337232276LMNOPQ00

15、2226GH由于节点由于节点N和和O是可解节点，故调用可解标记过程，得是可解节点，故调用可解标记过程，得节点节点L、B也为可解节点，但不能标记也为可解节点，但不能标记S0为可解节点，为可解节点，须继续扩展。须继续扩展。当前的希望树仍然是左子树当前的希望树仍然是左子树。西安电子科技大学西安电子科技大学与/或树的启发式搜索v与与/ /或树的启发式搜索：或树的启发式搜索： 对节点对节点C进行扩展，扩展两层后进行扩展，扩展两层后得到的与得到的与/或树如下图所示。或树如下图所示。S09A8D11BCEF3372322276LMNOPQ002226RST005229GH调用可解标记过程，可标记调用可解标记

16、过程，可标记S0为可解节点，这就的为可解节点，这就的到了代价最小的解树。按和代价法，到了代价最小的解树。按和代价法，该最优解的代该最优解的代价为价为9。 西安电子科技大学西安电子科技大学与/或树的搜索策略v与与/ /或树的搜索策略或树的搜索策略与与/或树的一般搜索过程或树的一般搜索过程与与/或树的广度优先搜索或树的广度优先搜索与与/或树的深度优先搜索或树的深度优先搜索与与/或树的启发式搜索或树的启发式搜索博弈树的启发式搜索博弈树的启发式搜索-剪枝技术剪枝技术西安电子科技大学西安电子科技大学博弈树的启发式搜索v博弈的概念：博弈的概念：博弈是一类具有智能行为的竞争活动，如博弈是一类具有智能行为的竞

17、争活动，如下棋、战争等。下棋、战争等。v博弈的类型：博弈的类型：双人完备信息博弈：双人完备信息博弈：两位选手对垒，轮流走步，每一两位选手对垒，轮流走步，每一方不仅知道对方已经走过的棋步，而且还能估计出对方不仅知道对方已经走过的棋步，而且还能估计出对方未来的走步。方未来的走步。机遇性博弈：机遇性博弈：存在不可预测性的博弈，例如掷币等。存在不可预测性的博弈，例如掷币等。v博弈树博弈树若把双人完备信息博弈过程用图表示出来，就得到一若把双人完备信息博弈过程用图表示出来，就得到一棵与棵与/或树，这种与或树，这种与/或树被称为或树被称为博弈树博弈树。西安电子科技大学西安电子科技大学博弈树的启发式搜索v博弈

18、树博弈树 在双人完备信息博弈中，若将两位对垒选手分别记为在双人完备信息博弈中，若将两位对垒选手分别记为MAX和和MIN ，则博弈树中，下一步该，则博弈树中，下一步该MAX走步的节点走步的节点称为称为MAX节点，该节点，该MIN走步的节点称为走步的节点称为MIN节点。节点。v博弈树的特点：博弈树的特点：(1) 博弈的初始状态是初始节点；博弈的初始状态是初始节点； (2) 博弈树中的博弈树中的“或或”节点和节点和“与与”节点逐层交替出现；节点逐层交替出现；(3) 整个博弈过程始终站在某一方的立场上。所有能使整个博弈过程始终站在某一方的立场上。所有能使自己一方获胜的终局都是本原问题，相应的节点是自己

19、一方获胜的终局都是本原问题，相应的节点是可可解节点解节点；所有使对方获胜的终局都是；所有使对方获胜的终局都是不可解节点不可解节点。西安电子科技大学西安电子科技大学博弈树的启发式搜索v极大极小分析法极大极小分析法对简单的博弈问题，可生成整个博弈树，找到必胜的对简单的博弈问题，可生成整个博弈树，找到必胜的策略。策略。对于复杂的博弈问题，不可能生成整个搜索树，如国对于复杂的博弈问题，不可能生成整个搜索树，如国际象棋，大约有际象棋，大约有10120个节点。个节点。 一种可行的方法是用当一种可行的方法是用当前正在考察的节点生成一棵前正在考察的节点生成一棵部分博弈树部分博弈树，并利用，并利用估价估价函数函

20、数f(n)对叶节点进行静态估值对叶节点进行静态估值。对叶节点的估值方法：对叶节点的估值方法：p那些对那些对MAX有利的节点，其估价函数取有利的节点，其估价函数取正值正值p那些对那些对MIN有利的节点，其估价函数取有利的节点，其估价函数取负值负值p那些使双方均等的节点，其估价函数取接近于那些使双方均等的节点，其估价函数取接近于0的值的值西安电子科技大学西安电子科技大学博弈树的启发式搜索v极大极小分析法极大极小分析法对非叶节点的估值方法：对非叶节点的估值方法：必须从叶节点开始向上倒推必须从叶节点开始向上倒推p对于对于MAX节点，由于节点，由于MAX 方总是方总是选择估值最大的走步选择估值最大的走步

21、，因此，因此，MAX节点的倒推值应该取其后继节点估值的最大节点的倒推值应该取其后继节点估值的最大值。值。p对于对于MIN节点，由于节点，由于MIN方总是方总是选择使估值最小的走步选择使估值最小的走步，因此因此MIN节点的倒推值应取其后继节点估值的最小值。节点的倒推值应取其后继节点估值的最小值。这样一步一步的计算倒推值，直至求出初始节点的倒这样一步一步的计算倒推值，直至求出初始节点的倒推值为止。这一过程称为推值为止。这一过程称为极大极小过程极大极小过程。西安电子科技大学西安电子科技大学博弈树的启发式搜索v博弈树的例子：博弈树的例子：一子棋游戏一子棋游戏 设有一个三行三列的棋盘，如下图所示，两个棋

22、手轮设有一个三行三列的棋盘，如下图所示，两个棋手轮流走步，每个棋手走步时往空格上摆一个自己的棋子，流走步，每个棋手走步时往空格上摆一个自己的棋子，谁先使自己的棋子成三子一线为赢。设谁先使自己的棋子成三子一线为赢。设MAX方的棋子方的棋子用用标记，标记，MIN方的棋子用标记，并规定方的棋子用标记，并规定MAX方先方先走步。走步。一一子棋棋盘子棋棋盘 棋局棋局1西安电子科技大学西安电子科技大学博弈树的启发式搜索v博弈树的例子：博弈树的例子：一子棋游戏一子棋游戏解：解：定义估价函数：定义估价函数：e(P)=e(+P)-e(-P)p e(+P)：P上有可能使上有可能使成三子为一线的数目；成三子为一线的

23、数目；p e(-P) ：P上有可能使成三子为一线的数目；上有可能使成三子为一线的数目； p 当当MAX必胜时，必胜时， e(P)为正无穷大为正无穷大p 当当MIN 必胜时，必胜时， e(P)为负无穷大为负无穷大p具有对称性的棋盘可认为是同一棋盘，例如：具有对称性的棋盘可认为是同一棋盘，例如：e(P)=e(+P)-e(-P)=5-4=1西安电子科技大学西安电子科技大学博弈树的启发式搜索v 一子棋的极大极小搜索一子棋的极大极小搜索S01S1 S2 S3-1 6-5=1 5-5=0 6-5=1 5-5=0 4-5=-1 5-4=1 6-4=25-6=-1 5-5=0 5-6=-1 6-6=0 4-6

24、=-2S4 S5-2 1 MAX节点节点MAX节点节点MIN节点节点西安电子科技大学西安电子科技大学与/或树的搜索策略v与与/ /或树的搜索策略或树的搜索策略与与/或树的一般搜索过程或树的一般搜索过程与与/或树的广度优先搜索或树的广度优先搜索与与/或树的深度优先搜索或树的深度优先搜索与与/或树的启发式搜索或树的启发式搜索博弈树的启发式搜索博弈树的启发式搜索-剪枝技术剪枝技术西安电子科技大学西安电子科技大学-剪枝技术v剪枝的概念：剪枝的概念：极大极小过程是先生成与极大极小过程是先生成与/或树，然后再计算各节点的估或树，然后再计算各节点的估值，这种生成节点和计算估值相分离的搜索方式，需要值，这种生

25、成节点和计算估值相分离的搜索方式，需要生成规定深度内的所有节点，因此搜索效率较低。生成规定深度内的所有节点，因此搜索效率较低。鉴于博弈树具有鉴于博弈树具有“与与”节点和节点和“或或”节点逐层交替出现节点逐层交替出现的特点，如果能的特点，如果能边生成节点边对节点估值，就有可能删边生成节点边对节点估值，就有可能删去一些不必要的节点，从而减少搜索及计算的工作量。去一些不必要的节点，从而减少搜索及计算的工作量。例如：例如：S0S452S1S2S33S5S63西安电子科技大学西安电子科技大学-剪枝技术v-剪枝方法剪枝方法(1) MAX节点的节点的值为当前子节点的最大到推值；值为当前子节点的最大到推值；(

26、2) MIN节点的节点的值为当前子节点的最小倒推值；值为当前子节点的最小倒推值；(3) -剪枝的规则如下：剪枝的规则如下：p任何任何MAX节点节点n的的值如果不能降低其父节点的值如果不能降低其父节点的值，值，则则n 以下的分枝可停止搜索，并令节点以下的分枝可停止搜索，并令节点n的倒推值为的倒推值为。这种剪枝称为。这种剪枝称为剪枝。剪枝。p任何任何MIN节点节点n的的值如果不能升高其父节点的值如果不能升高其父节点的值，值，则则n 以下的分枝可停止搜索，并令节点以下的分枝可停止搜索，并令节点n的倒推值为的倒推值为。这种剪枝称为。这种剪枝称为剪枝。剪枝。西安电子科技大学西安电子科技大学-剪枝技术v-

27、剪枝的例子：剪枝的例子：4 4S04 4A0 04 450 0CDE0-6IJ41 1KLN461FG5P58HM8值值值值值值值值QR0 0-6-6Sv 在在-剪枝技术中：对于一个剪枝技术中：对于一个MAX节点，如果估值最高的子节点，如果估值最高的子节点最先生成，或者对于一个节点最先生成，或者对于一个MIN节点，如果估值最低的节点，如果估值最低的子节点最先生成，则被剪除的节点数最多，搜索效率最高。子节点最先生成，则被剪除的节点数最多，搜索效率最高。这称为这称为最优最优-剪枝剪枝西安电子科技大学西安电子科技大学搜索策略v搜索策略搜索策略搜索的基本概念搜索的基本概念状态空间的搜索策略状态空间的搜

28、索策略与与/ /或树的搜索策略或树的搜索策略搜索的完备性与效率搜索的完备性与效率西安电子科技大学西安电子科技大学搜索的完备性与效率v完备性完备性对于一类对于一类可解的问题可解的问题和一个搜索过程，如果运和一个搜索过程，如果运用该搜索过程一定能求得该类问题的解，则称用该搜索过程一定能求得该类问题的解，则称该搜索过程为该搜索过程为完备的完备的，否则为，否则为不完备的不完备的。完备的搜索过程称为完备的搜索过程称为“搜索算法搜索算法”。不完备的。不完备的搜索过程不是算法，称为搜索过程不是算法，称为“过程过程”。广度优先搜索、代价树的广度优先搜索、改进广度优先搜索、代价树的广度优先搜索、改进后的有界深度优先搜索以及后的有界深度优先搜索以及A*算法都是完备的算法都是完备的搜索过程，其它搜索过程都是不完备的。搜索过程，其它搜索过程都是不完备的。西安电子科技大学西安电子科技大学搜索的完备性与效率v搜索效率搜索效率一个搜索过程的搜索效率不仅取决于过程自身一个搜索过程的搜索效率不仅取决于过程自身的启发能力，而且还与被解问题的有关属性等的启发能力，而且还与被解问题的有关属性等