人工智能幻灯片4.3

《人工智能幻灯片4.3》由会员分享，可在线阅读，更多相关《人工智能幻灯片4.3（24页珍藏版）》请在金锄头文库上搜索。

1、1,前面曾经讨论过与/或树的概念和问题的与/或树表示。用与/或树法表示的问题求解过程与状态空间法类似，也是通过搜索来实现对问题求解的。与/或树的搜索策略也分为盲目搜索和启发式搜索两大类。,4.4 与/或树的盲目搜索,2,与/或树的搜索过程实际上是一个不断寻找解树的过程。其一般搜索过程如下： （1）把原始问题作为初始节点S0，并把它作为当前节点； （2）应用分解或等价变换操作对当前节点进行扩展； （3）为每个子节点设置指向父节点的指针； （4）选择合适的子节点作为当前节点，反复执行第（2）步和第（3）步，在此期间需要多次调用可解标记过程或不可解标记过程，直到初始节点被标记为可解节点或不可解节点为

2、止。 上述搜索过程将形成一棵与/或树，这种由搜索过程形成的与/或树称为搜索树。当搜索成功时，经可解标记过程标识的由初始节点及其下属的可解节点构成的子树称为解树。,4.4 与/或树的盲目搜索,一. 与/或树的一般搜索,搜索过程中的可解标记过程与不可解标记过程都是自下而上进行的，即由子节点的可解性确定父节点、祖父节点的可解性；由子节点的不可解性确定父节点、祖父节点的不可解性。 在与/或树中，除端节点和终止节点外，一个节点的可解性完全是由其子节点来决定的。对与节点，只有其所有子节点都为可解时它才为可解，只要有一个子节点不可解它就是不可解的；对或节点，只要有一个子节点可解它就是可解的，仅当所有子节点都

3、是不可解时它才为不可解。 1.可解标记过程:由可解子节点来确定其父节点、祖父节点为可解节点的过程。2.不可解标记过程：由不可解子节点来确定其父节点、祖父节点为不可解节点的过程。 由于与/或树搜索的目标是寻找解树，因此，如果搜索过程确定某个节点为可解节点，则其不可解的后裔节点就可从搜索树中删去；同样，如果搜索过程能确定某个节点为不可解节点，则其后裔节点也可从搜索树中删去。,一. 与/或树的一般搜索,与/或树的广度优先搜索与状态空间的广度优先搜索类似，只是在搜索过程中需要多次调用可解标记过程或不可解标记过程，其搜索算法如下： （1）把初始节点S0 放人Open表中； （2）把Open表的第一个节点

4、取出放入Closed表，并记该节点为n； （3）如果节点n可扩展，则做下列工作： 扩展节点n，将其子节点放入Open表的尾部，并为每一个子节点设置指向父节点的指针； 考察这些子节点中是否有终止节点。若有，则标记这些终止节点为可解节点，并用可解标记过程对其父节点及先辈节点中的可解节点进行标记。如果初始解节点S0能够被标记为可解节点，就得到了解树，搜索成功，退出搜索过程；如果不能确定S0为可解节点，则从Open表中删去具有可解先辈的节点； 转第（2）步。 （4）如果节点n不可扩展，则做下列工作： 标记节点n为不可解节点； 应用不可解标记过程对节点n的先辈中不可解的节点进行标记。如果初始解节点S0也

5、被标记为不可解节点，则搜索失败，表明原始问题无解，退出搜索过程；如果不能确定S0为不可解节点，则从Open表中删去具有不可解先辈的节点； 转第（2）步。,二. 与/或树的广度优先搜索,例：设有如下图所示的与/或树，节点按图中所标注的顺序号进行扩展，其中标有t1、t2、t3的节点是终止节点，A 、 B 、 C为不可解的端节点。,搜索过程为： （ 1）先扩展1号节点，生成2号节点和3号节点，由于这两个子节点都不是终止节点，因此接着扩展2号节点，此时Open表中只剩下 3号节点。,（2）扩展2号节点，生成A节点和4号节点。由于这两个子节点均不是终止节点，因此接着扩展3号节点，此时Open表中剩下A节

6、点和4号节点。,（3）扩展3号节点，生成t1节点和5号节点。由于t1为终止节点，则标记它为可解节点，并应用可解标记过程，对其先辈中的可解节点进行标记，由于t1的父节点是一个与节点，因此不能确定3号节点是否可解。下一步扩展A节点，此时Open表中剩下4号节点和 5号节点。,（4）扩展节点A，由于A是端节点，因此不可扩展。调用不可解标记过程，由于2号节点是或节点，因此不能确定2号节点是不可解节点。下一步扩展4号节点，此时Open表中仅剩下5号节点。,（5）扩展4号节点，生成t2节点和B节点。由于t2为终止节点，则标记它为可解节点，并应用可解标记过程，对其先辈中的可解节点进行标记，由于4号节点是一个

7、或节点，因此可标记它为可解节点。继续向上，可标记2号节点为可解节点，但不能标记1号节点为可解节点。下一步扩展5号节点，此时Open表为空。,（6）扩展5号节点，生成t3节点和C节点。由于t3为终止节点，标记它为可解节点，并应用可解标记过程，对其先辈中的可解节点进行标记，由于5号节点是一个或节点，因此可标记它为可解节点。继续向上，可标记3号节点为可解节点。由于2号节点和3号节点都为可解节点，因此可标记1号节点为可解节点。,（7）搜索成功，得到由1、2、3、4、5号节点及t1、t2、t3节点构成的解树。该解树如上图中的粗线所示。,与/或树的深度优先搜索和与/或树的广度优先搜索过程基本相同，其主要区

8、别在于 Open表中节点的排列顺序不同。在扩展节点时，与/或树的深度优先搜索过程总是把刚生成的节点放在Open表的首部。同状态空间的深度优先搜索一样也可以带有深度限制dm，其搜索算法如下： （1）把初始节点S0放入Open表中； （2）把Open表的第一个节点取出放入Closed表，并记该节点为n； （3）如果节点n的深度等于dm，则转第（5）步的第点； （4）如果节点n可扩展，则做下列工作： 扩展节点 n，将其子节点放入 Open表的首部，并为每一个子节点设置指向父节点的指针； 考察这些子节点中是否有终止节点。若有，则标记这些终止节点为可解节点，并用可解标记过程对其父节点及先辈节点中的可解节

9、点进行标记。如果初始节点S0能够被标记为可解节点，就得到了解树，搜索成功，退出搜索过程；如果不能确定S0为可解节点，则从Open表中删去具有可解先辈的节点； 转第（2）步。,三. 与/或树的深度优先搜索,（5）如果节点n不可扩展，则做下列工作： 标记节点n为不可解节点； 应用不可解标记过程对节点n的先辈中不可解的节点进行标记。如果初始节点S0也被标记为不可解节点，则搜索失败，表明原始问题无解，退出搜索过程；如果不能确定为不可解节点，则从Open表中删去具有不可解先辈的节点； 转第（2）步。,例如，对上例所给出的与或树，若按有界深度优先搜索，且给定dm=4，则其扩展节点的顺序为： 1，3，5，2

10、，4 其解树与上例相同。,4.4 与/或树的盲目搜索,三. 与/或树的深度优先搜索,9,与/或树的盲目搜索是按确定路线进行的，当要选择一个节点进行扩展时，只是根据节点在与/或树中所处的位置，而没有考虑要付出的代价，因而求得的解树不一定是代价最小的解树，即不一定是最优解树。因此，我们需要考虑与/或树的启发式搜索。在讨论与或树的启发式搜索过程之前，需要先讨论几个有关的概念。 一. 解树的代价与希望树 与或树的启发式搜索过程是一种利用搜索过程所得到的启发性信息寻找最优解树的过程。对搜索的每一步，算法都试图找到一个最有希望成为最优解树的子树。最优解树是指代价最小的那棵解树。那么，如何计算解树的代价呢？

11、,4.5 与/或树的启发式搜索,1解树的代价 要寻找最优解树，首先需要计算解树的代价。在与/或树的启发式搜索过程中，解树的代价可按如下规则计算： （1）若n为终止节点，则其代价h（n）=0。 （2）若n为或节点，且子节点为n1，n2，nk，则n的代价为 h（n）= min c（n，ni） h（ni） (1ik) 其中，c（n，ni）是节点n到其子节点ni的边代价。,（3）若n为与节点，且子节点为n1，n2，nk，则n的代价可用和代价法或最大代价法。 若用和代价法，则其计算公式为： h（n）= (c(n，ni) h(ni) i=1,2,k 若用最大代价法，则其计算公式为： h（n）=maxc（n

12、，ni）h（ni） (1ik) （4）若n是端节点，但又不是终止节点，则n不可扩展，其代价定义为 h（n）= （5）根节点的代价即为解树的代价。,一. 解树的代价与希望树,例 ：设右图是一棵与/或树，其中包括两棵解树，左边的解树由S0、A 、 t1、C及t3组成；右边的解树由S0、 B、 t2、D及t4 组成。在此与/或树中，t1、t2、t3、t4为终止节点； E、 F是端节点；边上的数字是该边的代价。请计算解树的代价。,解：先计算左边的解树 按和代价：h（S0）=2462=14 按最大代价：h（S0）=2+6+2=10 再计算右边的解树 按和代价： h（S0）= 1532= 11 按最大代价

13、：h（S0）=1+5+2=8 在本例中，无论按和代价还是最大代价，右边的解树都是最优解树。但在有些情况下，当采用的代价法不同时，找到的最优解树有可能不同。,12,2希望树 为了找到最优解树，搜索过程的任何时刻都应该选择那些最有希望成为最优解树一部分的节点进行扩展。由于这些节点及其父节点所构成的与/或树最有可能成为最优解树的一部分，因此称它为希望解树，也简称为希望树。需要注意，希望解树是会随搜索过程而不断变化的。下面给出希望树的定义。,4.5 与/或树的启发式搜索,一. 解树的代价与希望树,定义：希望解树T （1）初始节点S0在希望树T中； （2）如果n是具有子节点n1，n2，nk的或节点，则n

14、的某个子节点ni在希望树T中的充分必要条件是 h（n）= min c（n，ni） h（ni） 1ik （3）如果n是与节点，则n的全部子节点都在希望树T中。,13,与或树的启发式搜索需要不断地选择、修正希望树，其搜索过程如下： （1）把初始节点S0放入Open表中，计算h（S0）； （2）计算希望树T； （3）依次在Open表中取出T的端节点放入Closed表，并记该节点为n； （4）如果节点n为终止节点，则做下列工作： 标记节点n为可解节点； 在T上应用可解标记过程，对n的先辈节点中的所有可解节点进行标记； 如果初始节点S0能够被标记为可解节点，则T就是最优解树，成功退出； 否则，从Open

15、表中删去具有可解先辈的所有节点； 转第（2）步。,4.5 与/或树的启发式搜索,二. 与/或树的启发式搜索过程,（5）如果节点n不是终止节点，但可扩展，则做下列工作： 扩展节点n，生成n的所有子节点； 把这些子节点都放入 Open表中，并为每一个子节点设置指向父节点 n的指针； 计算这些子节点及其先辈节点的h值； 转第（2）步。 （6）如果节点n不是终止节点，且不可扩展，则做下列工作： 标记节点n为不可解节点； 在T上应用不可解标记过程，对n的先辈节点中的所有不可解节点进行标记； 如果初始节点S0能够被标记为不可解节点，则问题无解，失败退出； 否则，从Open表中删去具有不可解先辈的所有节点； 转第（2）步。,4.5 与/或树的启发式搜索,二. 与/或树的启发式搜索过程,为了说明上述搜索过程，下面给出一个具体例子。在这个例子中，搜索过程每次扩展节点时都同时扩展两层，且按一层或节点、一层与节点的间隔方式进行扩展。实际上，下一节将要讨论的博弈树就是这种结构。 设初始节点为S0，对S0扩展后得到的与/或树如下图所示。其中，端节点B、C、E、F下面的数字是用启发函数估算出的h值，节点S0、A、D旁边的数字是按和代价法计算出来的节点代价。此时，S0的右子树是当前的希望树，