与或树的搜索策略_搜索的完备性与效率

1、6.3 与与/或树的搜索策略或树的搜索策略一般搜索过程一般搜索过程宽度优先搜索宽度优先搜索深度优先搜索深度优先搜索有序搜索有序搜索博弈树搜索博弈树搜索 - 剪枝技术剪枝技术可解节点与不可解节点可解节点与不可解节点可解节点的递归定义为：可解节点的递归定义为：l终叶节点是可解节点，直终叶节点是可解节点，直接和本原问题相关连；接和本原问题相关连；l非终叶节点含有非终叶节点含有“或或”子子节点时，只要子节点中有节点时，只要子节点中有一个是可解节点，该非终一个是可解节点，该非终叶节点便为可解节点；叶节点便为可解节点；l非终叶节点含有非终叶节点含有“与与”子子节点时，只有子节点全为节点时，只有子节点全为可

2、解节点时，该非终叶节可解节点时，该非终叶节点才是可解节点。点才是可解节点。注意：注意：终叶节点一定是端节点，终叶节点一定是端节点，但端节点不一定是终叶节点。但端节点不一定是终叶节点。由可解子节点来确定先辈节点是由可解子节点来确定先辈节点是否为可解节点的过程称为否为可解节点的过程称为可解标可解标示过程示过程。由不可解子节点来确定先辈节点由不可解子节点来确定先辈节点是否为可解节点的过程称为是否为可解节点的过程称为不可不可解标示过程解标示过程。不可解节点的定义为：不可解节点的定义为：关于可解节点的三个条件全关于可解节点的三个条件全部不满足的节点，称为不可解部不满足的节点，称为不可解节点；节点；一般搜

3、索过程流程一般搜索过程流程宽度优先搜索算法流程宽度优先搜索算法流程宽度优先搜索算法流程宽度优先搜索算法流程宽度优先搜索算法流程宽度优先搜索算法流程宽度优先搜索算法流程宽度优先搜索算法流程例：与例：与/或树的宽度优先搜索或树的宽度优先搜索例：设有如图所示的与例：设有如图所示的与/或树，其中或树，其中t1，t2，t3，t4均为终叶节均为终叶节点，点，A和和B是不可解的端节点。是不可解的端节点。 试采用与试采用与/或树的宽度优先搜索法对该图进行搜索。或树的宽度优先搜索法对该图进行搜索。例：与例：与/或树的宽度优先搜索或树的宽度优先搜索例：与例：与/或树的宽度优先搜索或树的宽度优先搜索例：与例：与/或

4、树的宽度优先搜索或树的宽度优先搜索例：与例：与/或树的宽度优先搜索或树的宽度优先搜索深度优先搜索的几点说明深度优先搜索的几点说明/或或有界深度优先搜索算法流程有界深度优先搜索算法流程有界深度优先搜索算法流程有界深度优先搜索算法流程例：与例：与/或树的深度优先搜索或树的深度优先搜索与与/或树的深度、宽度优先搜索特点或树的深度、宽度优先搜索特点有序搜索的基本思想有序搜索的基本思想解树的代价计算方法解树的代价计算方法 1,niiih xc x yh y 1min,iii nh xc x yh y 1max,iii nh xc x yh y 例：与例：与/或树的有序搜索或树的有序搜索例：设有如图所示与

5、例：设有如图所示与/或树，包括两棵解树，一棵由或树，包括两棵解树，一棵由S, A, t1, t2组成，另一棵组成，另一棵由由S, B, D, G, t4, t5组成。在与组成。在与/或树中，边上的数字是该边的代价，或树中，边上的数字是该边的代价，t1, t2 , t3, t4, t5为终叶节点，代价为为终叶节点，代价为0，E, F是端节点，代价为是端节点，代价为 。试计算解树代价。试计算解树代价。代价计算中存在的问题代价计算中存在的问题计算计算h(x)的的条件：条件：已知已知x所有子节点的代价。所有子节点的代价。x的所有子节点都不可扩展，否的所有子节点都不可扩展，否则则x的代价无法计算得到。的

6、代价无法计算得到。解决方案：解决方案：根据问题本身提供的启发性信息定义一个根据问题本身提供的启发性信息定义一个启发函启发函数数，由启发函数估算子节点的代价，然后反推计算父节点和，由启发函数估算子节点的代价，然后反推计算父节点和先辈节点的代价。每当有新一代的节点生成时，都要自下而先辈节点的代价。每当有新一代的节点生成时，都要自下而上地重新计算先辈节点的代价。上地重新计算先辈节点的代价。希望树希望树希望树的定义希望树的定义希望树的构成希望树的构成x在希望树中，则一定有：在希望树中，则一定有：1min,iii nc x yh y 有序搜索算法流程有序搜索算法流程3.2.4 与与/或树的有序搜索或树的

7、有序搜索例：与例：与/或树的有序搜索或树的有序搜索例：例： 设与设与/或树初始节点为或树初始节点为S0，每次扩，每次扩展两层，一层是展两层，一层是“与与”节点，一层节点，一层是是“或或”节点。希望树生成时，采节点。希望树生成时，采用和代价法，用和代价法，c(x, yi)=1。S0扩展后扩展后得到如图所示与得到如图所示与/或树，或树，B，C，E，F用启发函数估算出的用启发函数估算出的h值分别是：值分别是：h(B)=3，h(C)=3，h(E)=3，h(F)=2h(A)=c(A, B)+h(B)+c(A, C)+h(C) =(1+3)+(1+3)=8hA(S0)=8+1=9h(D)=7，hD(S0)

8、=8S0的右子树的右子树是希望树是希望树对希望树的端节点对希望树的端节点E扩展扩展两层后得到的与两层后得到的与/或树或树例：与例：与/或树的有序搜索或树的有序搜索h(G)=7h(H)=6h(E)=7h(D)=11hD(S0)=12S0的左子树是希望树的左子树是希望树hA(S0)=9例：与例：与/或树的有序搜索或树的有序搜索h(L)=2，h(M)=6，h(B)=3，h(A)=8，hA(S0)=9终叶节点终叶节点L和和B都是可解节点都是可解节点C无法判断是否可无法判断是否可解节点解节点A和和S0也无法判断也无法判断例：与例：与/或树的有序搜索或树的有序搜索Ch(N)=2，h(P)=7，h(C)=3

9、，h(A)=8，hA(S0)=9终叶节点终叶节点N、C、B可解可解A可解可解S0可解可解最优解树最优解树什么是博弈？什么是博弈？博弈树搜索的特点博弈树搜索的特点例：博弈树搜索例：博弈树搜索一字棋游戏一字棋游戏 例：设有如图所示九个空格，例：设有如图所示九个空格，A、B二人对奕，轮到谁走谁就往空格上二人对奕，轮到谁走谁就往空格上放一只自己的棋子，最先使自己棋子构成三子一线的就获得胜利。放一只自己的棋子，最先使自己棋子构成三子一线的就获得胜利。 设设A的棋子用的棋子用“a”表示，表示，B的棋子用的棋子用“b”表示，表示，A先走棋。先走棋。 为了不生成太大的博弈树，假设每次仅扩展两层。为了不生成太大的博弈树，假设每次仅扩展两层。一字棋一字棋例：博弈树搜索例：博弈树搜索一字棋游戏一字棋游戏 - 剪枝技术