1、1 前面曾经讨论过与前面曾经讨论过与/ /或树的概念和问题的与或树的概念和问题的与/ /或树表示。用与或树表示。用与/ /或树法表示的问题求解过程与状或树法表示的问题求解过程与状态空间法类似，也是通过搜索来实现对问题求解态空间法类似，也是通过搜索来实现对问题求解的。与的。与/ /或树的搜索策略也分为或树的搜索策略也分为盲目搜索盲目搜索和和启发式启发式搜索搜索两大类。两大类。4.4 4.4 与与/ /或树的盲目搜索或树的盲目搜索2 与与/ /或树的搜索过程实际上是一个不断或树的搜索过程实际上是一个不断寻找解树寻找解树的过程。其一般搜索过的过程。其一般搜索过程如下：程如下： （1 1）把原始问题作
2、为初始节点把原始问题作为初始节点S0S0，并把它作为当前节点；并把它作为当前节点； （2 2）应用应用分解分解或或等价变换等价变换操作对当前节点进行扩展；操作对当前节点进行扩展； （3 3）为每个子节点设置指向父节点的指针；为每个子节点设置指向父节点的指针； （4 4）选择选择合适的合适的子节点作为当前节点，反复执行第（子节点作为当前节点，反复执行第（2 2）步和第（）步和第（3 3）步，在此期间需要多次调用步，在此期间需要多次调用可解标记过程可解标记过程或或不可解标记过程不可解标记过程，直到初始节点，直到初始节点被标记为被标记为可解节点或不可解节点可解节点或不可解节点为止。为止。 上述搜索过
3、程将形成一棵与上述搜索过程将形成一棵与/ /或树，这种由搜索过程形成的与或树，这种由搜索过程形成的与/ /或树称为或树称为搜索树搜索树。当搜索成功时，经可解标记过程标识的由初始节点及其下属的可解。当搜索成功时，经可解标记过程标识的由初始节点及其下属的可解节点构成的子树称为节点构成的子树称为解树解树。4.4 4.4 与与/ /或树的盲目搜索或树的盲目搜索一一. . 与与/ /或树的一般搜索或树的一般搜索 搜索过程中的搜索过程中的可解标记过程与不可解标记过程可解标记过程与不可解标记过程都是都是自下而上自下而上进行的，即由进行的，即由子节点的可解性确定父节点、祖父节点的可解性；由子节点的不可解性确定
4、父子节点的可解性确定父节点、祖父节点的可解性；由子节点的不可解性确定父节点、祖父节点的不可解性。节点、祖父节点的不可解性。 在与在与/ /或树中，除或树中，除端节点端节点和和终止节点终止节点外，外，一个节点的可解性完全是由其子一个节点的可解性完全是由其子节点来决定的节点来决定的。对与节点，只有其所有子节点都为可解时它才为可解，只要有。对与节点，只有其所有子节点都为可解时它才为可解，只要有一个子节点不可解它就是不可解的；对或节点，只要有一个子节点可解它就是一个子节点不可解它就是不可解的；对或节点，只要有一个子节点可解它就是可解的，仅当所有子节点都是不可解时它才为不可解。可解的，仅当所有子节点都是
5、不可解时它才为不可解。1.1.可解标记过程可解标记过程: :由可解子节点来确定其父节点、祖父节点为可解节点的过程。由可解子节点来确定其父节点、祖父节点为可解节点的过程。2.2.不可解标记过程不可解标记过程：由不可解子节点来确定其父节点、祖父节点为不可解节点由不可解子节点来确定其父节点、祖父节点为不可解节点的过程。的过程。 由于与由于与/ /或树搜索的目标是或树搜索的目标是寻找解树寻找解树，因此，如果搜索过程确定某个节点，因此，如果搜索过程确定某个节点为可解节点，则其为可解节点，则其不可解的后裔节点就可从搜索树中删去不可解的后裔节点就可从搜索树中删去；同样，如果搜索过；同样，如果搜索过程能确定某
6、个节点为不可解节点，则其后裔节点也可从搜索树中删去。程能确定某个节点为不可解节点，则其后裔节点也可从搜索树中删去。一一. . 与与/ /或树的一般搜索或树的一般搜索 与与/ /或树的广度优先搜索与状态空间的广度优先搜索类似，只是或树的广度优先搜索与状态空间的广度优先搜索类似，只是在搜索过程在搜索过程中需要多次调用可解标记过程或不可解标记过程中需要多次调用可解标记过程或不可解标记过程，其搜索算法如下：，其搜索算法如下：（1 1）把初始节点把初始节点S0 S0 放人放人OpenOpen表中；表中；（2 2）把把OpenOpen表的第一个节点取出放入表的第一个节点取出放入ClosedClosed表，
7、并记该节点为表，并记该节点为n n；（3 3）如果节点如果节点n n可扩展可扩展，则做下列工作：，则做下列工作： 扩展节点扩展节点n n，将将其子节点其子节点放入放入OpenOpen表的表的尾部尾部，并为每一个子节点设置指向父，并为每一个子节点设置指向父节点的指针；节点的指针； 考察这些子节点中考察这些子节点中是否有终止节点是否有终止节点。若有，则标记这些终止节点为可解节。若有，则标记这些终止节点为可解节点，并用可解标记过程对其父节点及先辈节点中的可解节点进行标记。如果初始点，并用可解标记过程对其父节点及先辈节点中的可解节点进行标记。如果初始解节点解节点S0S0能够被标记为可解节点，就得到了解
8、树，搜索成功，退出搜索过程；如能够被标记为可解节点，就得到了解树，搜索成功，退出搜索过程；如果不能确定果不能确定S0S0为可解节点，则从为可解节点，则从OpenOpen表中删去具有可解先辈的节点；表中删去具有可解先辈的节点； 转第（转第（2 2）步。）步。（4 4）如果节点如果节点n n不可扩展不可扩展，则做下列工作：，则做下列工作： 标记节点标记节点n n为不可解节点；为不可解节点； 应用不可解标记过程对节点应用不可解标记过程对节点n n的先辈中不可解的节点进行标记。如果初始解的先辈中不可解的节点进行标记。如果初始解节点节点S0S0也被标记为不可解节点，则搜索失败，表明原始问题无解，退出搜索
9、过程；也被标记为不可解节点，则搜索失败，表明原始问题无解，退出搜索过程；如果不能确定如果不能确定S0S0为不可解节点，则从为不可解节点，则从OpenOpen表中删去具有不可解先辈的节点；表中删去具有不可解先辈的节点； 转第（转第（2 2）步。）步。二二. . 与与/ /或树的广度优先搜索或树的广度优先搜索 例：例：设有如下图所示的与设有如下图所示的与/ /或树，节点按图中所标注的顺序号进行扩展，其中或树，节点按图中所标注的顺序号进行扩展，其中标有标有t1t1、t2t2、t3t3的节点是终止节点，的节点是终止节点，A A 、 B B 、 C C为不可解的端节点。为不可解的端节点。 与与/或树的广
10、度优先搜索或树的广度优先搜索123A4t1t3CBt25搜索过程为搜索过程为：（ 1 1）先先扩展扩展1 1号节点号节点，生成，生成2 2号节点和号节点和3 3号节号节点，由于这两个子节点都不是终止节点，因此点，由于这两个子节点都不是终止节点，因此接着扩展接着扩展2 2号节点，此时号节点，此时OpenOpen表中只剩下表中只剩下 3 3号号节点。节点。（2 2）扩展扩展2 2号节点号节点，生成，生成A A节点和节点和4 4号节点。由于号节点。由于这两个子节点均不是终止节点，因此接着扩展这两个子节点均不是终止节点，因此接着扩展3 3号节点，此时号节点，此时OpenOpen表中剩下表中剩下A A节
11、点和节点和4 4号节点。号节点。（3 3）扩展扩展3 3号节点号节点，生成，生成t1t1节点和节点和5 5号节点。由于号节点。由于t1t1为终止节点，则标记它为终止节点，则标记它为可解节点，并应用可解标记过程，对其先辈中的可解节点进行标记，由于为可解节点，并应用可解标记过程，对其先辈中的可解节点进行标记，由于t1t1的父节点是一个与节点，因此不能确定的父节点是一个与节点，因此不能确定3 3号节点是否可解。下一步扩展号节点是否可解。下一步扩展A A节节点，此时点，此时OpenOpen表中剩下表中剩下4 4号节点和号节点和 5 5号节点。号节点。（4 4）扩展节点扩展节点A A，由于由于A A是端
12、节点，因此不可扩展。调用不可解标记过程，是端节点，因此不可扩展。调用不可解标记过程，由于由于2 2号节点是或节点，因此不能确定号节点是或节点，因此不能确定2 2号节点是不可解节点。下一步扩展号节点是不可解节点。下一步扩展4 4号节点，此时号节点，此时OpenOpen表中仅剩下表中仅剩下5 5号节点。号节点。（5 5）扩展扩展4 4号节点号节点，生成，生成t2t2节点和节点和B B节点。节点。由于由于t2t2为终止节点，则标记它为可解节点，为终止节点，则标记它为可解节点，并应用可解标记过程，对其先辈中的可解并应用可解标记过程，对其先辈中的可解节点进行标记，由于节点进行标记，由于4 4号节点是一个
13、或节点，号节点是一个或节点，因此可标记它为可解节点。继续向上，可因此可标记它为可解节点。继续向上，可标记标记2 2号节点为可解节点，但不能标记号节点为可解节点，但不能标记1 1号号节点为可解节点。下一步扩展节点为可解节点。下一步扩展5 5号节点，此号节点，此时时OpenOpen表为空。表为空。（6 6）扩展扩展5 5号节点号节点，生成，生成t3t3节点和节点和C C节点。由于节点。由于t3t3为终止节点，标为终止节点，标记它为可解节点，并应用可解标记过程，对其先辈中的可解节点进记它为可解节点，并应用可解标记过程，对其先辈中的可解节点进行标记，由于行标记，由于5 5号节点是一个或节点，因此可标记
14、它为可解节点。号节点是一个或节点，因此可标记它为可解节点。继续向上，可标记继续向上，可标记3 3号节点为可解节点。由于号节点为可解节点。由于2 2号节点和号节点和3 3号节点都号节点都为可解节点，因此可标记为可解节点，因此可标记1 1号节点为可解节点。号节点为可解节点。（7 7）搜索成功搜索成功，得到由，得到由1 1、2 2、3 3、4 4、5 5号节点及号节点及t1t1、t2t2、t3t3节点构节点构成的解树。该解树如上图中的粗线所示。成的解树。该解树如上图中的粗线所示。 与与/或树的广度优先搜索或树的广度优先搜索123A4t1t3CBt25 与与/ /或树的深度优先搜索和与或树的深度优先搜
15、索和与/ /或树的广度优先搜索过程基本相同，其主要或树的广度优先搜索过程基本相同，其主要区别在于区别在于 OpenOpen表中节点的排列顺序不同。在扩展节点时，与表中节点的排列顺序不同。在扩展节点时，与/ /或树的深度优先或树的深度优先搜索过程总是把搜索过程总是把刚生成的节点刚生成的节点放在放在OpenOpen表的表的首部首部。同状态空间的深度优先搜索。同状态空间的深度优先搜索一样也一样也可以带有深度限制可以带有深度限制dmdm，其搜索算法如下：其搜索算法如下： （1 1）把初始节点）把初始节点S0S0放入放入OpenOpen表中；表中； （2 2）把）把OpenOpen表的第一个节点取出放入
16、表的第一个节点取出放入ClosedClosed表，并记该节点为表，并记该节点为n n； （3 3）如果节点如果节点n n的深度等于的深度等于dmdm，则转第（则转第（5 5）步的第点；）步的第点； （4 4）如果节点）如果节点n n可扩展可扩展，则做下列工作：，则做下列工作： 扩展节点扩展节点 n n，将其子节点放入将其子节点放入 OpenOpen表的首部，并为每一个子节点设表的首部，并为每一个子节点设置指向父节点的指针；置指向父节点的指针； 考察这些子节点中考察这些子节点中是否有终止节点是否有终止节点。若有，则标记这些终止节点为可。若有，则标记这些终止节点为可解节点，并用可解标记过程对其父节
17、点及先辈节点中的可解节点进行标记。如解节点，并用可解标记过程对其父节点及先辈节点中的可解节点进行标记。如果初始节点果初始节点S0S0能够被标记为可解节点，就得到了解树，搜索成功，退出搜索过能够被标记为可解节点，就得到了解树，搜索成功，退出搜索过程；如果不能确定程；如果不能确定S0S0为可解节点，则从为可解节点，则从OpenOpen表中删去具有可解先辈的节点；表中删去具有可解先辈的节点； 转第（转第（2 2）步。）步。三三. . 与与/ /或树的深度优先搜索或树的深度优先搜索（5 5）如果节点）如果节点n n不可扩展不可扩展，则做下列工作：，则做下列工作： 标记节点标记节点n n为不可解节点；为
18、不可解节点； 应用不可解标记过程对节点应用不可解标记过程对节点n n的先辈中不可解的节点进行标记。如果初的先辈中不可解的节点进行标记。如果初始节点始节点S0S0也被标记为不可解节点，则搜索失败，表明原始问题无解，退出搜也被标记为不可解节点，则搜索失败，表明原始问题无解，退出搜索过程；如果不能确定为不可解节点，则从索过程；如果不能确定为不可解节点，则从OpenOpen表中删去具有不可解先辈的表中删去具有不可解先辈的节点；节点； 转第（转第（2 2）步。）步。 与与/或树的深度优先搜索或树的深度优先搜索123A4t1t3CBt25例如，对上例所给出的与或树，例如，对上例所给出的与或树，若按有界深度
19、优先搜索，且给定若按有界深度优先搜索，且给定dm=4dm=4，则其扩展节点的顺序为：则其扩展节点的顺序为： 1 1，3 3，5 5，2 2，4 4其解树与上例相同。其解树与上例相同。4.4 4.4 与与/ /或树的盲目搜索或树的盲目搜索三三. . 与与/ /或树的深度优先搜索或树的深度优先搜索9 与与/ /或树的盲目搜索是或树的盲目搜索是按确定路线进行按确定路线进行的，当要选择一个节点进行扩展时，的，当要选择一个节点进行扩展时，只是只是根据节点在与根据节点在与/ /或树中或树中所处的位置所处的位置，而，而没有考虑要付出的没有考虑要付出的代价代价，因而求得，因而求得的解树不一定是代价最小的解树，
20、即不一定是最优解树。因此，我们需要考虑的解树不一定是代价最小的解树，即不一定是最优解树。因此，我们需要考虑与与/ /或树的启发式搜索。在讨论与或树的启发式搜索过程之前，需要先讨论或树的启发式搜索。在讨论与或树的启发式搜索过程之前，需要先讨论几个有关的概念。几个有关的概念。一一. . 解树的代价与希望树解树的代价与希望树 与或树的启发式搜索过程是一种利用搜索过程所得到的启发性信息寻找与或树的启发式搜索过程是一种利用搜索过程所得到的启发性信息寻找最优解树的过程。对搜索的每一步，算法都试图找到一个最有希望成为最优解最优解树的过程。对搜索的每一步，算法都试图找到一个最有希望成为最优解树的子树。树的子树
21、。最优解树是指最优解树是指代价最小代价最小的那棵解树的那棵解树。那么，如何计算解树的代价呢？。那么，如何计算解树的代价呢？4.5 4.5 与与/ /或树的启发式搜索或树的启发式搜索1 1解树的代价解树的代价 要寻找最优解树，首先需要计算要寻找最优解树，首先需要计算解树的代价解树的代价。在与在与/ /或树的启发式搜索过程或树的启发式搜索过程中，解树的代价可按如下规则计算：中，解树的代价可按如下规则计算： （1 1）若若n n为终止节点为终止节点，则其代价，则其代价h h（n n）=0=0。 （2 2）若若n n为或节点为或节点，且子节点为，且子节点为n1n1，n2n2，nknk，则则n n的代价
22、为的代价为 h h（n n）= min = min c c（n n，nini） h h（nini） (1ik) (1ik) 其中，其中，c c（n n，nini）是节点是节点n n到其子节点到其子节点nini的边代价。的边代价。 （3 3）若若n n为与节点为与节点，且子节点为，且子节点为n1n1，n2n2，nknk，则则n n的代价可用和代价法的代价可用和代价法或最大代价法。或最大代价法。 若用若用和代价法和代价法，则其计算公式为：，则其计算公式为： h h（n n）= (= (c(nc(n，nini) ) h(nih(ni) i=1,2,) i=1,2,k ,k 若用若用最大代价法最大代价
23、法，则其计算公式为：，则其计算公式为： h h（n n）= =maxmaxc c（n n，nini）h h（nini） (1ik) (1ik) （4 4）若若n n是端节点是端节点，但又不是终止节点，则，但又不是终止节点，则n n不可扩展，其代价定义为不可扩展，其代价定义为 h h（n n）= = （5 5）根节点的代价即为解树的代价根节点的代价即为解树的代价。一一. . 解树的代价与希望树解树的代价与希望树例例 ：设右图是一棵与设右图是一棵与/ /或树，其中包括两或树，其中包括两棵解树，左边的解树由棵解树，左边的解树由S0S0、A A 、 t1 t1、C C及及t3t3组成；右边的解树由组成
24、；右边的解树由S0S0、 B B、 t2 t2、D D及及t4 t4 组成。在此与组成。在此与/ /或树中，或树中，t1t1、t2t2、t3t3、t4t4为终止节点；为终止节点； E E、 F F是端节点；边上的是端节点；边上的数字是该边的代价。请计算解树的代价。数字是该边的代价。请计算解树的代价。S0ABt1Ct3Et2Dt4F 与或树的代价与或树的代价22463521解解：先计算：先计算左边的解树左边的解树 按和代价：按和代价：h h（S0S0）=2=24 46 62=142=14 按最大代价：按最大代价：h h（S0S0）=2+6+2=10=2+6+2=10 再计算再计算右边的解树右边的
25、解树 按和代价：按和代价： h h（S0S0）= 1= 15 53 32= 112= 11 按最大代价：按最大代价：h h（S0S0）=1+5+2=8=1+5+2=8 在本例中，无论按和代价还是最大代价，右边的解树都是最优解在本例中，无论按和代价还是最大代价，右边的解树都是最优解树。但在有些情况下，当采用的代价法不同时，找到的最优解树有可树。但在有些情况下，当采用的代价法不同时，找到的最优解树有可能不同。能不同。122 2希望树希望树 为了找到最优解树，搜索过程的任何时刻都应该选择那些最有为了找到最优解树，搜索过程的任何时刻都应该选择那些最有希望成为最优解树一部分的节点进行扩展。由于这些节点及
26、其父节点希望成为最优解树一部分的节点进行扩展。由于这些节点及其父节点所构成的与所构成的与/ /或树最有可能成为最优解树的一部分，因此称它为希望或树最有可能成为最优解树的一部分，因此称它为希望解树，也简称为解树，也简称为希望树希望树。需要注意，。需要注意，希望解树是会随搜索过程而不断希望解树是会随搜索过程而不断变化的变化的。下面给出希望树的定义。下面给出希望树的定义。4.5 4.5 与与/ /或树的启发式搜索或树的启发式搜索一一. . 解树的代价与希望树解树的代价与希望树定义：希望解树定义：希望解树T T （1 1）初始节点初始节点S0S0在希望树在希望树T T中；中； （2 2）如果）如果n
27、n是具有子节点是具有子节点n1n1，n2n2，nknk的的或节点或节点，则，则n n的某个子的某个子节点节点nini在希望树在希望树T T中的充分必要条件是中的充分必要条件是 h h（n n）= min = min c c（n n，nini） h h（nini） 1ik 1ik （3 3）如果如果n n是是与节点与节点，则，则n n的全部子节点都在希望树的全部子节点都在希望树T T中。中。13 与或树的启发式搜索需要与或树的启发式搜索需要不断地选择、修正希望树不断地选择、修正希望树，其搜索过程如下：，其搜索过程如下： （1 1）把初始节点）把初始节点S0S0放入放入OpenOpen表中，计算表
28、中，计算h h（S0S0）；）； （2 2）计算希望树计算希望树T T； （3 3）依次在依次在OpenOpen表中取出表中取出T T的端节点放入的端节点放入ClosedClosed表，并记该节点为表，并记该节点为n n； （4 4）如果节点如果节点n n为终止节点为终止节点，则做下列工作：，则做下列工作： 标记节点标记节点n n为可解节点；为可解节点； 在在T T上应用可解标记过程，对上应用可解标记过程，对n n的先辈节点中的所有可解节点进行标记；的先辈节点中的所有可解节点进行标记； 如果初始节点如果初始节点S0S0能够被标记为可解节点，则能够被标记为可解节点，则T T就是最优解树，成功退出
29、；就是最优解树，成功退出； 否则，从否则，从OpenOpen表中删去具有可解先辈的所有节点；表中删去具有可解先辈的所有节点； 转第（转第（2 2）步。）步。4.5 4.5 与与/ /或树的启发式搜索或树的启发式搜索二二. . 与与/ /或树的启发式搜索过程或树的启发式搜索过程（5 5）如果节点）如果节点n n不是终止节点，但可扩展不是终止节点，但可扩展，则做下列工作：，则做下列工作： 扩展节点扩展节点n n，生成生成n n的所有子节点；的所有子节点； 把这些子节点都放入把这些子节点都放入 OpenOpen表中，并为每一个子节点设置指向父节点表中，并为每一个子节点设置指向父节点 n n的指针；的
30、指针； 计算这些子节点及其先辈节点的计算这些子节点及其先辈节点的h h值；值； 转第（转第（2 2）步。）步。（6 6）如果节点）如果节点n n不是终止节点，且不可扩展不是终止节点，且不可扩展，则做下列工作：，则做下列工作： 标记节点标记节点n n为不可解节点；为不可解节点； 在在T T上应用不可解标记过程，对上应用不可解标记过程，对n n的先辈节点中的所有不可解节点进行标的先辈节点中的所有不可解节点进行标记；记； 如果初始节点如果初始节点S0S0能够被标记为不可解节点，则问题无解，失败退出；能够被标记为不可解节点，则问题无解，失败退出； 否则，从否则，从OpenOpen表中删去具有不可解先辈
31、的所有节点；表中删去具有不可解先辈的所有节点； 转第（转第（2 2）步。）步。4.5 4.5 与与/ /或树的启发式搜索或树的启发式搜索二二. . 与与/ /或树的启发式搜索过程或树的启发式搜索过程 为了说明上述搜索过程，下面给出一个具体例子。在这个例子中，为了说明上述搜索过程，下面给出一个具体例子。在这个例子中，搜索过程每次扩展节点时都搜索过程每次扩展节点时都同时扩展两层同时扩展两层，且按一层或节点、一层与，且按一层或节点、一层与节点的间隔方式进行扩展。实际上，下一节将要讨论的节点的间隔方式进行扩展。实际上，下一节将要讨论的博弈树博弈树就是这就是这种结构。种结构。 设初始节点为设初始节点为S
32、0S0，对对S0S0扩展后得到的与扩展后得到的与/ /或树如下图所示。其中，或树如下图所示。其中，端节点端节点B B、C C、E E、F F下面的数字是用启发函数估算出的下面的数字是用启发函数估算出的h h值，节点值，节点S0S0、A A、D D旁边的数字是按旁边的数字是按和代价法和代价法计算出来的节点代价。此时，计算出来的节点代价。此时，S0S0的的右子树右子树是当前的希望树是当前的希望树，下面对其端节点进行扩展。，下面对其端节点进行扩展。S0ADBCEF8873332扩展扩展S0后的与或树后的与或树16 先先扩展节点扩展节点E E ，得到如图得到如图1 1所示的与所示的与/ /或树。此时，
33、由右子树求出的或树。此时，由右子树求出的h h（S0S0）=12=12，而由左子树求出的而由左子树求出的h h（S0S0）=9=9。显然，左子树的代价小。因此，当前的希望显然，左子树的代价小。因此，当前的希望树应树应改为左子树改为左子树。 对节点对节点B B进行扩展进行扩展，扩展两层后得到的与，扩展两层后得到的与/ /或树如图或树如图2 2所示。由于节点所示。由于节点H H和和I I是是可解节点，故调用可解标记过程，得节点可解节点，故调用可解标记过程，得节点G G、B B也为可解节点，但不能标记也为可解节点，但不能标记S0S0为可为可解节点，须继续扩展。当前的解节点，须继续扩展。当前的希望树仍
34、然是左子树希望树仍然是左子树。 对节点对节点C C进行扩展进行扩展。扩展两层后得到的与或树如图。扩展两层后得到的与或树如图3 3所示。所示。 由于节点由于节点N N和和P P是可解节点，故调用可解标记过程，得节点是可解节点，故调用可解标记过程，得节点M M、C C、A A也为可解也为可解节点，进而可标记节点，进而可标记S0S0为可解节点。这样就求出了代价最小的解树，即最优解树，为可解节点。这样就求出了代价最小的解树，即最优解树，如图如图3 3中的粗线所示。中的粗线所示。按和代价法，该最优解树的代价为按和代价法，该最优解树的代价为9 9。S0ADBCEF8332 3222776119图图1 扩展
35、扩展E后的与或树后的与或树S0ADBCEF8332 3222776119GKHILJ002226图图2 扩展扩展B后的与或树后的与或树9S0DEFABC8332 3222776119IGKHLJ002226MNP005229图图3 扩展扩展C后的与或树后的与或树17 博弈博弈是一类富有智能行为的竞争活动，如下棋、打牌、是一类富有智能行为的竞争活动，如下棋、打牌、战争等。博弈可分为战争等。博弈可分为双人完备信息博弈双人完备信息博弈和和机遇性博弈机遇性博弈。所。所谓谓双人完备信息博弈双人完备信息博弈，就是两位选手对垒，轮流走步，每，就是两位选手对垒，轮流走步，每一方不仅知道对方已经走过的棋步，而且
36、还能估计出对方一方不仅知道对方已经走过的棋步，而且还能估计出对方未来的走步。对弈的结果是一方赢，另一方输；或者双方未来的走步。对弈的结果是一方赢，另一方输；或者双方和局。这类博弈的实例有象棋、围棋等。所谓和局。这类博弈的实例有象棋、围棋等。所谓机遇性博弈机遇性博弈，是指存在不可预测性的博弈，例如掷币等。对机遇性博弈，是指存在不可预测性的博弈，例如掷币等。对机遇性博弈，由于不具备完备信息，因此我们不作讨论。由于不具备完备信息，因此我们不作讨论。 4.6 4.6 博弈树的启发式搜索博弈树的启发式搜索一一. . 概述概述 这里我们主要讨论双人完备信息博弈问题。这里我们主要讨论双人完备信息博弈问题。
37、在双人完备在双人完备信息博弈过程中，双方都希望自己能够获胜。因此，当任何一信息博弈过程中，双方都希望自己能够获胜。因此，当任何一方走步时，都是选择对自己最为有利，而对另一方最为不利的方走步时，都是选择对自己最为有利，而对另一方最为不利的行动方案。行动方案。 假设博弈的一方为假设博弈的一方为MAXMAX，另一方为另一方为MINMIN。在博弈过程的每一在博弈过程的每一步，可供步，可供MAXMAX和和MINMIN选择的行动方案都可能有多种。从选择的行动方案都可能有多种。从MAXMAX方的方的观点看，观点看，可供自己选择的那些行动方案之间是可供自己选择的那些行动方案之间是“或或”的关系的关系，原因是主
38、动权掌握在原因是主动权掌握在MAXMAX手里，选择哪个方案完全是由自己决手里，选择哪个方案完全是由自己决定的；而对那些定的；而对那些可供可供MINMIN选择的行动方案之间则是选择的行动方案之间则是“与与”的关的关系系，原因是主动权掌握在，原因是主动权掌握在MINMIN的手里，任何一个方案都有可能的手里，任何一个方案都有可能被被MINMIN选中，选中，MAXMAX必须防止那种对自己最为不利的情况的发生。必须防止那种对自己最为不利的情况的发生。19 若把双人完备信息博弈过程用图表示出来，就可得到一棵与若把双人完备信息博弈过程用图表示出来，就可得到一棵与/ /或或树，这种与树，这种与/ /或树被称为
39、或树被称为博弈树博弈树。在博弈树中，那些下一步该。在博弈树中，那些下一步该MAXMAX走步走步的节点称为的节点称为MAXMAX节点节点，而下一步该，而下一步该MINMIN走步的节点称为走步的节点称为MINMIN节点节点。博弈。博弈树具有如下特点：树具有如下特点： （l l）博弈的初始状态是初始节点；博弈的初始状态是初始节点； （2 2）博弈树中的）博弈树中的“或或”节点和节点和“与与”节点是节点是逐层交替逐层交替出现的；出现的； （3 3）整个博弈过程）整个博弈过程始终站在某一方始终站在某一方的立场上，所有能使自己一的立场上，所有能使自己一方获胜的终局都是本原问题，相应的节点是可解节点；所有使
40、对方获方获胜的终局都是本原问题，相应的节点是可解节点；所有使对方获胜的终局都是不可解节点。例如，胜的终局都是不可解节点。例如，站在站在MAXMAX方方，所有能使，所有能使MAXMAX方获胜的方获胜的节点都是可解节点，所有能使节点都是可解节点，所有能使MINMIN方获胜的节点都是不可解节点。方获胜的节点都是不可解节点。4.6 4.6 博弈树的启发式搜索博弈树的启发式搜索一一. . 概述概述20 对简单的博弈问题，可以生成整个博弈树，找到必胜对简单的博弈问题，可以生成整个博弈树，找到必胜的策略。但对于复杂的博弈，如国际象棋，大约有的策略。但对于复杂的博弈，如国际象棋，大约有1010120120个个
41、节点，可见要生成整个搜索树是不可能的。一种可行的方节点，可见要生成整个搜索树是不可能的。一种可行的方法是用当前正在考察的节点生成一棵法是用当前正在考察的节点生成一棵部分博弈树部分博弈树，由于该，由于该博弈树的叶节点一般不是哪一方的获胜节点，因此，需利博弈树的叶节点一般不是哪一方的获胜节点，因此，需利用用估价函数估价函数f(n)f(n)对叶节点进行静态评估，对对叶节点进行静态评估，对MAXMAX有利的节有利的节点其估价函数取正值；那些对点其估价函数取正值；那些对MINMIN有利的节点，其估价函有利的节点，其估价函数取负值；那些使双方均等的节点，其估价函数取接近于数取负值；那些使双方均等的节点，其
42、估价函数取接近于0 0的值。的值。4.6 4.6 博弈树的启发式搜索博弈树的启发式搜索二二. . 极大极小过程极大极小过程21 为了计算非叶节点的值，必须从叶节点向上倒推。对为了计算非叶节点的值，必须从叶节点向上倒推。对于于MAXMAX节点，由于节点，由于 MAXMAX方总是选择估值最大的走步，因此，方总是选择估值最大的走步，因此，MAXMAX节点的倒推值应该取其后继节点估值的节点的倒推值应该取其后继节点估值的最大值最大值。对于。对于MINMIN节点，由于节点，由于MINMIN方总是选择使估值最小的走步，因此方总是选择使估值最小的走步，因此MINMIN节点的倒推值应取其后继节点估值的节点的倒推
43、值应取其后继节点估值的最小值最小值。这样一。这样一步一步的计算倒推值，直至求出初始节点的倒推值为止。步一步的计算倒推值，直至求出初始节点的倒推值为止。由于我们是站在由于我们是站在MAXMAX的立场上，因此应选择具有最大倒推的立场上，因此应选择具有最大倒推值的走步。这一过程称为值的走步。这一过程称为极大极小过程极大极小过程。 下面给出一个极大极小过程的例子下面给出一个极大极小过程的例子。例：例： 一字棋游戏。设有一个三行三列的棋盘，如下图所示，两个棋手轮流走一字棋游戏。设有一个三行三列的棋盘，如下图所示，两个棋手轮流走步，每个棋手走步时往空格上摆一个自己的棋子，谁先使自己的棋子成三子一步，每个棋
44、手走步时往空格上摆一个自己的棋子，谁先使自己的棋子成三子一线为赢。设线为赢。设MAXMAX方的棋子用方的棋子用标记，标记，MINMIN方的棋子用方的棋子用 标记，并规定标记，并规定MAXMAX方先走方先走步。步。 解解：为了对叶节点进行静态估值，规定估价函数为了对叶节点进行静态估值，规定估价函数e e（P P）如下：如下： 若若 P P是是 MAXMAX的必胜局，的必胜局， 则则 e e（P P）= + = + ； 若若 P P是是 MIN MIN 的必胜局，的必胜局， 则则 e e（P P）= - = - ； 一字棋棋盘一字棋棋盘 若若P P对对MAXMAX、MINMIN都是胜负未定局，则都
45、是胜负未定局，则 e e（P P）= e= e（+P+P）e e（-P-P）其中，其中，e e（+P+P）表示棋局表示棋局 P P上有可能使上有可能使 成三子一线的数目；成三子一线的数目；e e（-P-P）表示棋局表示棋局 P P上上有可能使有可能使 成三子一线的数目。成三子一线的数目。4.6 4.6 博弈树的启发式搜索博弈树的启发式搜索二二. . 极大极小过程极大极小过程例如，对图例如，对图1 1所示的棋局有估价函数值所示的棋局有估价函数值 e e（P P）6-46-42 2图图1 棋局棋局1 在搜索过程中，在搜索过程中，具有对称性的棋局认为是同一棋局具有对称性的棋局认为是同一棋局。例如，图
46、例如，图2 2所示的棋局可以认为是同一个棋局，这样可以大所示的棋局可以认为是同一个棋局，这样可以大大大减少搜索空间减少搜索空间。图。图3 3给出了第一着走棋以后生成的博弈树。给出了第一着走棋以后生成的博弈树。图中叶节点下面的数字是该节点的静态估值，非叶节点旁图中叶节点下面的数字是该节点的静态估值，非叶节点旁边的数字是计算出的倒推值。从图中可以看出，对边的数字是计算出的倒推值。从图中可以看出，对MAXMAX来说来说S2S2是一着最好的走棋，它具有较大的倒推值。是一着最好的走棋，它具有较大的倒推值。图图2 对称棋局的例子对称棋局的例子 图图3 一子棋的极大极小搜索一子棋的极大极小搜索S0S1S2S3S4S5-1-1 1 1 -2 -26-5=15-5=06-5=15-5=04-5=- -15-6=- -15-5=06-6=05-6=- -14-6=- -25-4=16-4=2
