人工智能课件43

前面曾经讨论过与/或树的概念和问题的与/或树表示。用与/或树法表示的问题求解过程与状态空间法类似，也是通过搜索来实现对问题求解的。与/或树的搜索策略也分为盲目搜索和启发式搜索两大类。4.4与/或树的盲目搜索1前面曾经讨论过与/或树的概念和问题的与/或树表示。用与/或树的搜索过程实际上是一个不断寻找解树的过程。其一般搜索过程如下：

（1）把原始问题作为初始节点S0，并把它作为当前节点；

（2）应用分解或等价变换操作对当前节点进行扩展；

（3）为每个子节点设置指向父节点的指针；

（4）选择合适的子节点作为当前节点，反复执行第（2）步和第（3）步，在此期间需要多次调用可解标记过程或不可解标记过程，直到初始节点被标记为可解节点或不可解节点为止。

上述搜索过程将形成一棵与/或树，这种由搜索过程形成的与/或树称为搜索树。当搜索成功时，经可解标记过程标识的由初始节点及其下属的可解节点构成的子树称为解树。4.4与/或树的盲目搜索一.与/或树的一般搜索2与/或树的搜索过程实际上是一个不断寻找解树的过程。其

搜索过程中的可解标记过程与不可解标记过程都是自下而上进行的，即由子节点的可解性确定父节点、祖父节点的可解性；由子节点的不可解性确定父节点、祖父节点的不可解性。

在与/或树中，除端节点和终止节点外，一个节点的可解性完全是由其子节点来决定的。对与节点，只有其所有子节点都为可解时它才为可解，只要有一个子节点不可解它就是不可解的；对或节点，只要有一个子节点可解它就是可解的，仅当所有子节点都是不可解时它才为不可解。

1.可解标记过程:由可解子节点来确定其父节点、祖父节点为可解节点的过程。2.不可解标记过程：由不可解子节点来确定其父节点、祖父节点为不可解节点的过程。

由于与/或树搜索的目标是寻找解树，因此，如果搜索过程确定某个节点为可解节点，则其不可解的后裔节点就可从搜索树中删去；同样，如果搜索过程能确定某个节点为不可解节点，则其后裔节点也可从搜索树中删去。一.与/或树的一般搜索3搜索过程中的可解标记过程与不可解标记过程都是自下而上与/或树的广度优先搜索与状态空间的广度优先搜索类似，只是在搜索过程中需要多次调用可解标记过程或不可解标记过程，其搜索算法如下：

（1）把初始节点S0放人Open表中；

（2）把Open表的第一个节点取出放入Closed表，并记该节点为n；

（3）如果节点n可扩展，则做下列工作：

①扩展节点n，将其子节点放入Open表的尾部，并为每一个子节点设置指向父节点的指针；

②考察这些子节点中是否有终止节点。若有，则标记这些终止节点为可解节点，并用可解标记过程对其父节点及先辈节点中的可解节点进行标记。如果初始解节点S0能够被标记为可解节点，就得到了解树，搜索成功，退出搜索过程；如果不能确定S0为可解节点，则从Open表中删去具有可解先辈的节点；

③

转第（2）步。

（4）如果节点n不可扩展，则做下列工作：

①标记节点n为不可解节点；

②应用不可解标记过程对节点n的先辈中不可解的节点进行标记。如果初始解节点S0也被标记为不可解节点，则搜索失败，表明原始问题无解，退出搜索过程；如果不能确定S0为不可解节点，则从Open表中删去具有不可解先辈的节点；

③转第（2）步。二.与/或树的广度优先搜索4与/或树的广度优先搜索与状态空间的广度优先搜索类似，例：设有如下图所示的与/或树，节点按图中所标注的顺序号进行扩展，其中标有t1、t2、t3的节点是终止节点，A、B、C为不可解的端节点。

与/或树的广度优先搜索123A4t1t3CBt25搜索过程为：

（1）先扩展1号节点，生成2号节点和3号节点，由于这两个子节点都不是终止节点，因此接着扩展2号节点，此时Open表中只剩下3号节点。（2）扩展2号节点，生成A节点和4号节点。由于这两个子节点均不是终止节点，因此接着扩展3号节点，此时Open表中剩下A节点和4号节点。（3）扩展3号节点，生成t1节点和5号节点。由于t1为终止节点，则标记它为可解节点，并应用可解标记过程，对其先辈中的可解节点进行标记，由于t1的父节点是一个与节点，因此不能确定3号节点是否可解。下一步扩展A节点，此时Open表中剩下4号节点和5号节点。（4）扩展节点A，由于A是端节点，因此不可扩展。调用不可解标记过程，由于2号节点是或节点，因此不能确定2号节点是不可解节点。下一步扩展4号节点，此时Open表中仅剩下5号节点。5例：设有如下图所示的与/或树，节点按图中所标注的顺序号进行（5）扩展4号节点，生成t2节点和B节点。由于t2为终止节点，则标记它为可解节点，并应用可解标记过程，对其先辈中的可解节点进行标记，由于4号节点是一个或节点，因此可标记它为可解节点。继续向上，可标记2号节点为可解节点，但不能标记1号节点为可解节点。下一步扩展5号节点，此时Open表为空。（6）扩展5号节点，生成t3节点和C节点。由于t3为终止节点，标记它为可解节点，并应用可解标记过程，对其先辈中的可解节点进行标记，由于5号节点是一个或节点，因此可标记它为可解节点。继续向上，可标记3号节点为可解节点。由于2号节点和3号节点都为可解节点，因此可标记1号节点为可解节点。（7）搜索成功，得到由1、2、3、4、5号节点及t1、t2、t3节点构成的解树。该解树如上图中的粗线所示。

与/或树的广度优先搜索123A4t1t3CBt256（5）扩展4号节点，生成t2节点和B节点。由于t2为终止节点与/或树的深度优先搜索和与/或树的广度优先搜索过程基本相同，其主要区别在于Open表中节点的排列顺序不同。在扩展节点时，与/或树的深度优先搜索过程总是把刚生成的节点放在Open表的首部。同状态空间的深度优先搜索一样也可以带有深度限制dm，其搜索算法如下：

（1）把初始节点S0放入Open表中；

（2）把Open表的第一个节点取出放入Closed表，并记该节点为n；

（3）如果节点n的深度等于dm，则转第（5）步的第①点；

（4）如果节点n可扩展，则做下列工作：

①扩展节点n，将其子节点放入Open表的首部，并为每一个子节点设置指向父节点的指针；

②考察这些子节点中是否有终止节点。若有，则标记这些终止节点为可解节点，并用可解标记过程对其父节点及先辈节点中的可解节点进行标记。如果初始节点S0能够被标记为可解节点，就得到了解树，搜索成功，退出搜索过程；如果不能确定S0为可解节点，则从Open表中删去具有可解先辈的节点；

③转第（2）步。

三.与/或树的深度优先搜索7与/或树的深度优先搜索和与/或树的广度优先搜索过程基（5）如果节点n不可扩展，则做下列工作：

①标记节点n为不可解节点；

②应用不可解标记过程对节点n的先辈中不可解的节点进行标记。如果初始节点S0也被标记为不可解节点，则搜索失败，表明原始问题无解，退出搜索过程；如果不能确定为不可解节点，则从Open表中删去具有不可解先辈的节点；

③转第（2）步。

与/或树的深度优先搜索123A4t1t3CBt25例如，对上例所给出的与／或树，若按有界深度优先搜索，且给定dm=4，则其扩展节点的顺序为：

1，3，5，2，4

其解树与上例相同。4.4与/或树的盲目搜索三.与/或树的深度优先搜索8（5）如果节点n不可扩展，则做下列工作：

①标记节点n与/或树的盲目搜索是按确定路线进行的，当要选择一个节点进行扩展时，只是根据节点在与/或树中所处的位置，而没有考虑要付出的代价，因而求得的解树不一定是代价最小的解树，即不一定是最优解树。因此，我们需要考虑与/或树的启发式搜索。在讨论与／或树的启发式搜索过程之前，需要先讨论几个有关的概念。

一.解树的代价与希望树

与／或树的启发式搜索过程是一种利用搜索过程所得到的启发性信息寻找最优解树的过程。对搜索的每一步，算法都试图找到一个最有希望成为最优解树的子树。最优解树是指代价最小的那棵解树。那么，如何计算解树的代价呢？4.5与/或树的启发式搜索9与/或树的盲目搜索是按确定路线进行的，当要选择一个节1．解树的代价

要寻找最优解树，首先需要计算解树的代价。在与/或树的启发式搜索过程中，解树的代价可按如下规则计算：

（1）若n为终止节点，则其代价h（n）=0。

（2）若n为或节点，且子节点为n1，n2，…，nk，则n的代价为

h（n）=min{c（n，ni）＋h（ni）}(1≤i≤k)其中，c（n，ni）是节点n到其子节点ni的边代价。

（3）若n为与节点，且子节点为n1，n2，…，nk，则n的代价可用和代价法或最大代价法。

若用和代价法，则其计算公式为：

h（n）=Σ((c(n，ni)＋h(ni))i=1,2,……,k

若用最大代价法，则其计算公式为：

h（n）=max｛c（n，ni）＋h（ni）｝(1≤i≤k)

（4）若n是端节点，但又不是终止节点，则n不可扩展，其代价定义为

h（n）=∞

（5）根节点的代价即为解树的代价。一.解树的代价与希望树101．解树的代价

要寻找最优解树，首先需要计算解树的代例：设右图是一棵与/或树，其中包括两棵解树，左边的解树由S0、A、t1、C及t3组成；右边的解树由S0、B、t2、D及t4组成。在此与/或树中，t1、t2、t3、t4为终止节点；E、F是端节点；边上的数字是该边的代价。请计算解树的代价。S0ABt1Ct3Et2Dt4F与／或树的代价22463521解：先计算左边的解树

按和代价：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

在本例中，无论按和代价还是最大代价，右边的解树都是最优解树。但在有些情况下，当采用的代价法不同时，找到的最优解树有可能不同。11例：设右图是一棵与/或树，其中包括两棵解树，左边的解树由S2．希望树

为了找到最优解树，搜索过程的任何时刻都应该选择那些最有希望成为最优解树一部分的节点进行扩展。由于这些节点及其父节点所构成的与/或树最有可能成为最优解树的一部分，因此称它为希望解树，也简称为希望树。需要注意，希望解树是会随搜索过程而不断变化的。下面给出希望树的定义。4.5与/或树的启发式搜索一.解树的代价与希望树定义：希望解树T

（1）初始节点S0在希望树T中；

（2）如果n是具有子节点n1，n2，…，nk的或节点，则n的某个子节点ni在希望树T中的充分必要条件是

h（n）=min{c（n，ni）＋h（ni）}1≤i≤k

（3）如果n是与节点，则n的全部子节点都在希望树T中。122．希望树

为了找到最优解树，搜索过程的任何时刻都应与／或树的启发式搜索需要不断地选择、修正希望树，其搜索过程如下：

（1）把初始节点S0放入Open表中，计算h（S0）；

（2）计算希望树T；

（3）依次在Open表中取出T的端节点放入Closed表，并记该节点为n；

（4）如果节点n为终止节点，则做下列工作：

①标记节点n为可解节点；

②在T上应用可解标记过程，对n的先辈节点中的所有可解节点进行标记；

③如果初始节点S0能够被标记为可解节点，则T就是最优解树，成功退出；

④否则，从Open表中删去具有可解先辈的所有节点；

⑤转第（2）步。4.5与/或树的启发式搜索二.与/或树的启发式搜索过程13与／或树的启发式搜索需要不断地选择、修正希望树，其搜（5）如果节点n不是终止节点，但可扩展，则做下列工作：

①扩展节点n，生成n的所有子节点；

②把这些子节点都放入Open表中，并为每一个子节点设置指向父节点n的指针；

③计算这些子节点及其先辈节点的h值；

④转第（2）步。

（6）如果节点n不是终止节点，且不可扩展，则做下列工作：

①标记节点n为不可解节点；

②在T上应用不可解标记过程，对n的先辈节点中的所有不可解节点进行标记；

③如果初始节点S0能够被标记为不可解节点，则问题无解，失败退出；

④否则，从Open表中删去具有不可解先辈的所有节点；

⑤转第（2）步。4.5与/或树的启发式搜索二.与/或树的启发式搜索过程14（5）如果节点n不是终止节点，但可扩展，则做下列工作：

为了说明上述搜索过程，下面给出一个具体例子。在这个例子中，搜索过程每次扩展节点时都同时扩展两层，且按一层或节点、一层与节点的间隔方式进行扩展。实际上，下一节将要讨论的博弈树就是这种结构。

设初始节点为S0，对S0扩展后得到的与/或树如下图所示。其中，端节点B、C、E、F下面的数字是用启发函数估算出的h值，节点S0、A、D旁边的数字是按和代价法计算出来的节点代价。此时，S0的右子树是当前的希望树，下面对其端节点进行扩展。S0ADBCEF8873332扩展S0后的与／或树15为了说明上述搜索过程，下面给出一个具体例子。在这个例

先扩展节点E，得到如图1所示的与/或树。此时，由右子树求出的h（S0）=12，而由左子树求出的h（S0）=9。显然，左子树的代价小。因此，当前的希望树应改为左子树。对节点B进行扩展，扩展两层后得到的与/或树如图2所示。由于节点H和I是可解节点，故调用可解标记过程，得节点G、B也为可解节点，但不能标记S0为可解节点，须继续扩展。当前的希望树仍然是左子树。对节点C进行扩展。扩展两层后得到的与／或树如图3所示。由于节点N和P是可解节点，故调用可解标记过程，得节点M、C、A也为可解节点，进而可标记S0为可解节点。这样就求出了代价最小的解树，即最优解树，如图3中的粗线所示。按和代价法，该最优解树的代价为9。S0ADBCEF8332

3222776119图1扩展E后的与／或树S0ADBCEF8332

3222776119GKHILJ002226图2扩展B后的与／或树9S0DEFABC8332

3222776119IGKHLJ002226MNP005229图3扩展C后的与／或树16

先扩展节点E，得到如图1所示的与/或树。此时，

博弈是一类富有智能行为的竞争活动，如下棋、打牌、战争等。博弈可分为双人完备信息博弈和机遇性博弈。所谓双人完备信息博弈，就是两位选手对垒，轮流走步，每一方不仅知道对方已经走过的棋步，而且还能估计出对方未来的走步。对弈的结果是一方赢，另一方输；或者双方和局。这类博弈的实例有象棋、围棋等。所谓机遇性博弈，是指存在不可预测性的博弈，例如掷币等。对机遇性博弈，由于不具备完备信息，因此我们不作讨论。

4.6博弈树的启发式搜索一.概述17博弈是一类富有智能行为的竞争活动，如下棋、打牌、战争这里我们主要讨论双人完备信息博弈问题。在双人完备信息博弈过程中，双方都希望自己能够获胜。因此，当任何一方走步时，都是选择对自己最为有利，而对另一方最为不利的行动方案。假设博弈的一方为MAX，另一方为MIN。在博弈过程的每一步，可供MAX和MIN选择的行动方案都可能有多种。从MAX方的观点看，可供自己选择的那些行动方案之间是“或”的关系，原因是主动权掌握在MAX手里，选择哪个方案完全是由自己决定的；而对那些可供MIN选择的行动方案之间则是“与”的关系，原因是主动权掌握在MIN的手里，任何一个方案都有可能被MIN选中，MAX必须防止那种对自己最为不利的情况的发生。18这里我们主要讨论双人完备信息博弈问题。在双人完备信

若把双人完备信息博弈过程用图表示出来，就可得到一棵与/或树，这种与/或树被称为博弈树。在博弈树中，那些下一步该MAX走步的节点称为MAX节点，而下一步该MIN走步的节点称为MIN节点。博弈树具有如下特点：（l）博弈的初始状态是初始节点；（2）博弈树中的“或”节点和“与”节点是逐层交替出现的；（3）整个博弈过程始终站在某一方的立场上，所有能使自己一方获胜的终局都是本原问题，相应的节点是可解节点；所有使对方获胜的终局都是不可解节点。例如，站在MAX方，所有能使MAX方获胜的节点都是可解节点，所有能使MIN方获胜的节点都是不可解节点。4.6博弈树的启发式搜索一.概述19若把双人完备信息博弈过程用图表示出来，就可得到一棵与/对简单的博弈问题，可以生成整个博弈树，找到必胜的策略。但对于复杂的博弈，如国际象棋，大约有10120个节点，可见要生成整个搜索树是不可能的。一种可行的方法是用当前正在考察的节点生成一棵部分博弈树，由于该博弈树的叶节点一般不是哪一方的获胜节点，因此，需利用估价函数f(n)对叶节点进行静态评估，对MAX有利的节点其估价函数取正值；那些对MIN有利的节点，其估价函数取负值；那些使双方均等的节点，其估价函数取接近于0的值。4.6博弈树的启发式搜索二.极大极小过程20对简单的博弈问题，可以生成整个博弈树，找到必胜的策略为了计算非叶节点的值，必须从叶节点向上倒推。对于MAX节点，由于MAX方总是选择估值最大的走步，因此，MAX节点的倒推值应该取其后继节点估值的最大值。对于MIN节点，由于MIN方总是选择使估值最小的走步，因此MIN节点的倒推值应取其后继节点估值的最小值。这样一步一步的计算倒推值，直至求出初始节点的倒推值为止。由于我们是站在MAX的立场上，因此应选择具有最大倒推值的走步。这一