6.与或树.ppt

人工智能人工智能与或树与或树与或树总体要求与或树总体要求深度优先-会求解树广度优先-会求解树博弈树（抽一段）Alpha、beta剪枝 6.3 6.3 与与/或树的搜索策略或树的搜索策略一般搜索过程宽度优先搜索深度优先搜索有序搜索博弈树搜索-剪枝技术可解节点与不可解节点可解节点与不可解节点在与/或树上执行搜索过程，目的在于表明起始节点有解或无解。可解节点的递归定义为：可解节点的递归定义为：l终叶节点是可解节点，直终叶节点是可解节点，直接和本原问题相关连；接和本原问题相关连；l非终叶节点含有非终叶节点含有“或或”子子节点时，只要子节点中有节点时，只要子节点中有一个是可解节点，该非终一个是可解节点，该非终叶节点便为可解节点；叶节点便为可解节点；l非终叶节点含有非终叶节点含有“与与”子子节点时，只有子节点全为节点时，只有子节点全为可解节点时，该非终叶节可解节点时，该非终叶节点才是可解节点。点才是可解节点。注意：注意：终叶节点一定是端节点，终叶节点一定是端节点，但端节点不一定是终叶节点。但端节点不一定是终叶节点。由可解子节点来确定先辈节点是由可解子节点来确定先辈节点是否为可解节点的过程称为否为可解节点的过程称为可解标可解标示过程示过程。由不可解子节点来确定先辈节点由不可解子节点来确定先辈节点是否为可解节点的过程称为是否为可解节点的过程称为不可不可解标示过程解标示过程。不可解节点的定义为：不可解节点的定义为：关于可解节点的三个条件全关于可解节点的三个条件全部不满足的节点，称为不可解部不满足的节点，称为不可解节点；节点；一般搜索过程流程一般搜索过程流程(1)把原始问题作为初始节点S，并把它作为当前节点。(2)应用分解或等价变换算符对当前节点进行扩展。(3)为每个子节点设置指向父节点的指针。(4)选择合适子节点作为当前节点，反复执行第(2)、(3)步，在此期间多次调用可解标示过程和不可解标示过程，直到初始节点被标示为可解节点或不可解节点为止。由这个搜索过程所形成的节点和指针结构称为搜索树。搜索中，通过可解标示过程确定初始节点是可解的，则由此初始节点及其下属的可解节点就构成了解树。提高与提高与/或树搜索效率的两个或树搜索效率的两个性质性质与/或搜索有两个特有性质，可用来提高搜索效率：如果已确定某个节点为可解节点，其不可解的后裔节点不再有用，可从搜索树中删去；若已确定某个节点是不可解节点，其全部后裔节点都不再有用，可从搜索树中删去。但当前这个不可解节点还不能删去，在判断其先辈节点的可解性时还要用到。宽度优先搜索算法流程宽度优先搜索算法流程基本思想：先产生的节点先扩展，先进先出。1.把初始节点S放入OPEN表。2.把OPEN表中的第一个节点(记为节点n)取出放入CLOSLD表。3.如果n可扩展，则做下列工作：扩展n，将其子节点放入OPEN表的尾部，并为每个子节点配置父指针，以备标示过程使用。考察子节点中是否有终叶节点。若有，则标示这些终叶节点为可解节点，并应用可解标示过程对其先辈节点中的可解节点进行标示。若S也被标示为可解节点，就得到了解树，搜索成功，退出搜索过程；若无法确定S可解，则从OPEN表中删去具有可解先辈的节点。转步骤2。宽度优先搜索算法流程宽度优先搜索算法流程4.如果n不可扩展，则做下列工作：标示n为不可解节点。应用不可解标示过程对n的先辈节点中不可解的节点进行标示。如果S被标示为不可解节点，则搜索失败，原始问题无解，退出搜索过程；如果无法确定S不可解，则从OPEN表中删去具有不可解先辈的节点。转步骤2。宽度优先搜索算法流程宽度优先搜索算法流程宽度优先搜索算法流程宽度优先搜索算法流程例：与例：与/或树的宽度优先搜索或树的宽度优先搜索例：设有如图所示的与/或树，其中t1，t2，t3，t4均为终叶节点，A和B是不可解的端节点。试采用与/或树的宽度优先搜索法对该图进行搜索。例：与例：与/或树的宽度优先搜索或树的宽度优先搜索Step1：扩展1号节点，得到2、3号节点。2、3都不是终叶节点，接着扩展2。OPENOPENCLOSEDCLOSED1 12,32,31 13 32,12,1例：与例：与/或树的宽度优先搜索或树的宽度优先搜索Step3：扩展2，得到4、t1。t1是终叶节点，标示为可解节点，应用可解标示过程，对其先辈节点中的可解节点进行标示。t1的父节点是“与”节点，仅由t1可解不能确定2是否可解，应继续搜索。OPENOPENCLOSEDCLOSED3,43,42,12,1t t1 1,2,1,2,1例：与例：与/或树的宽度优先搜索或树的宽度优先搜索Step3：扩展3得到5、B，都不是终叶节点，接着扩展4。Step4：扩展4得到A、t2。t2是终叶节点，标示4为可解节点。应用可解标示过程标出4、2均为可解节点。还不能确定1为可解节点。此时5号节点是OPEN表中的第一个待考察的节点，所以下一步扩展5号节点。OPENOPENCLOSEDCLOSED4 43,3,t t1 1,2,1,2,15 5t t2 2,4,3,4,3,t t1 1,2,1,2,1例：与例：与/或树的宽度优先搜索或树的宽度优先搜索Step5：扩展5得到t3、t4。都是终叶节点，标示5为可解节点。应用可解标示过程得到5、3、1均为可解节点。Step6：搜索成功，得到解树。OPENOPENCLOSEDCLOSED5,5,t t2 2,4,3,4,3,t t1 1,2,1,2,1深度优先搜索的几点说明深度优先搜索的几点说明与/或树的深度优先搜索和宽度优先搜索过程基本相同。只要把第(3)步的第点改为“扩展节点n，将其子节点放入OPEN表的首部，并为每个子节点配置父指针，以备标示过程使用”，就可使后产生的节点先被扩展。也可像状态空间的有界深度优先搜索那样，为与/或树的深度优先搜索规定一个深度界限，使搜索在规定范围内进行。有界深度优先搜索算法流程有界深度优先搜索算法流程1.把初始节点S放人OPEN表。2.把OPEN表中第一个节点n取出，放入CLOSLD表。3.如果n的深度深度界限，转第(5)步的第点。4.如果n 可扩展，做下列工作：扩展n，将子节点放入OPEN表首部，配置父指针，在 标示过程使用。若子节点中有终叶节点，标示其为可解节点，对其先辈 节点应用可解标示过程进行标示。若S被标示为可解，得到解树，成功退出搜索；若无法确定S为可解节点，从OPEN表中删去有可解先辈的节点。转第(2)步。有界深度优先搜索算法流程有界深度优先搜索算法流程5.如果n不可扩展，则做下列工作：标示n为不可解节点。应用不可解标示过程对n的先辈节点中不可解节点进行标示。如果S被标示为不可解节点，则搜索失败退出；如果不能确定S为不可解节点，则从OPEN表中删去有不可解先辈的节点。转第(2)步。例：与例：与/或树的深度优先搜索或树的深度优先搜索对与/或树进行有界深度优先搜索，并规定深度界限为4，则扩展节点的顺序是：1，3，B，5，2，4解树与宽度优先搜索相同。与与/或树的深度、宽度优先搜索或树的深度、宽度优先搜索特点特点都是盲目搜索。搜索从初始节点开始，先自上而下进行搜索，寻找终叶节点及端点节，然后再自下而上进行标示。一旦初始节点被标示为可解或不可解节点，搜索就不再继续进行。搜索都按确定路线进行，当选择某个节点进行扩展时，只考虑节点在与/或树中的位置，没有考虑要付出的代价，因而求得的解树不一定是代价最小的解树，即不一定是最优解树。有序搜索的基本思想有序搜索的基本思想 与/或树的有序搜索是求代价最小的解树的搜索方法。为求得代价最小的解树，每次确定待扩展节点时，需要往前多看几步，计算扩展这个节点可能要付出的代价，并选择代价最小的节点进行扩展。像这样根据代价决定搜索路线的方法称为与/或树的有序搜索，它是一种启发式搜索策略。解树的代价计算方法解树的代价计算方法通过计算解树中节点的代价得到。若问题可解，由子节点代价推算父节点代价，逐层上推，最终求出S的代价，即解树的代价。设设设设c c(x x,y y)表示节点表示节点表示节点表示节点x x到其子节点到其子节点到其子节点到其子节点y y的代价，则的代价，则的代价，则的代价，则x x的代价计算方法如下：的代价计算方法如下：的代价计算方法如下：的代价计算方法如下：如果如果如果如果x x是终叶节点，则定义是终叶节点，则定义是终叶节点，则定义是终叶节点，则定义x x的代价：的代价：的代价：的代价：h h(x x)=0)=0如果如果如果如果x x不可扩展，且不是终叶节点，则定义：不可扩展，且不是终叶节点，则定义：不可扩展，且不是终叶节点，则定义：不可扩展，且不是终叶节点，则定义：h h(x x)=)=如果如果如果如果x x是是是是“或或或或”节点，节点，节点，节点，y y1 1，y y2 2，y yn n是它的子节点，则是它的子节点，则是它的子节点，则是它的子节点，则x x的代价为：的代价为：的代价为：的代价为：如果如果如果如果x x是是是是“与与与与”节点则节点则节点则节点则x x的代价有两种计算方法：的代价有两种计算方法：的代价有两种计算方法：的代价有两种计算方法：和代价法和代价法和代价法和代价法 最大代价法最大代价法最大代价法最大代价法例：与例：与/或树的有序搜索或树的有序搜索例：设有如图所示与例：设有如图所示与/或树，包括两棵解树，一棵由或树，包括两棵解树，一棵由S,A,t1,t2组成，另一棵组成，另一棵由由S,B,D,G,t4,t5组成。在与组成。在与/或树中，边上的数字是该边的代价，或树中，边上的数字是该边的代价，t1,t2,t3,t4,t5为终叶节点，代价为为终叶节点，代价为0，E,F是端节点，代价为是端节点，代价为。试计算解树代价。试计算解树代价。和代价和代价最大代价最大代价左边左边解树解树h(A)=11h(S)=13h(A)=6h(S)=8右边右边解树解树h(G)=3h(D)=4h(B)=6h(S)=8h(G)=2h(D)=3h(B)=5h(S)=7代价计算中存在的问题代价计算中存在的问题计算h(x)的条件：已知x所有子节点的代价。问题：搜索是自上而下进行的，只有不可扩展节点的代价是已知的（或0），因此除非x的所有子节点都不可扩展，否则x的代价无法计算得到。解决方案：根据问题本身提供的启发性信息定义一个启发函数，由启发函数估算子节点的代价，然后反推计算父节点和先辈节点的代价。每当有新一代的节点生成时，都要自下而上地重新计算先辈节点的代价。希望树希望树希望树的定义希望树的定义 选择待扩展节点时，挑选有希望成为最优解树一部分的节点进行扩展，保证任一时刻求出的部分解树的代价都是最小的。由这些节点及先辈节点（包括初始节点S）构成的与/或树有可能成为最优解树一部分，被称为希望树。注意：搜索过程中，随着新节点的不断生成，节点的代价值不断变化。因此，希望树也是在不断变化的。有序搜索是一个不断选择、不断修正希望树的过程。希望树的构成希望树的构成初始节点S在希望树中；如果节点x在希望树中，则一定有：如果x是“或”节点，y1，y2，yn是它的子节点，则具有 值的那个子节点yi也应在希望树中。如果x是“与”节点，则它的全部子节点都应在希望树中。有序搜索算法流程有序搜索算法流程(1)把初始节点S放入OPEN表中。(2)根据当前搜索树中节点的代价求出以S为根的希望树T。(3)依次把OPEN表中T的端节点N选出放入CLOSED表中。(4)如果N是终叶节点，则做下列工作：标示N为可解节点。对T应用可解标示过程，标记N的先辈节点。若S被标记为可解，则T就是最优解树，成功退出。否则，从OPLN表中删去具有可解先辈的节点。(5)如果N不是终叶节点，且不可扩展，则做下列工作：标示N为不可解节点。对T应用不可解标示过程，标记N的先辈节点。若初始节点S被标示为不可解节点，则失败退出。否则，从OPEN表中删去有不可解先辈的节点。(6)如果N不是终叶节点，但可扩展，则做下列工作：扩展N，产生N的所有子节点。把子节点放入OPEN表，并为每个子节点配置父指针。计算子节点的h值及其先辈节点的h值。(7)转第(2)步。3.2.4 3.2.4 与与/或树的有序搜索或树的有序搜索例：与例：与/或树的有序搜索或树的有序搜索例：设与/或树初始节点为S0，每次扩展两层，一层是“与”节点，一层是“或”节点。希望树生成时，采用和代价法，c(x,yi)=1。S0扩展后得到如图所示与/或树，B，C，E，F用启发函数估算出的h值分别是：h(B)=3，h(C)=3，h(E)=3，h(F)=2Step1Step1：h(A)=c(A,B)+h(B)+c(A,C)+h(C)=(1+3)+(1+3)=8hA(S0)=8+1=9h(D)=7，hD(S0)=8S0的右子树的右子树是希望树是希望树对希望树的端节点对希望树的端节点E扩展扩展两层后得到的与两层后得到的与/或树或树例：与例：与/或树的有序搜索或树的有序搜索Step2Step2：h(G)=7h(H)=6h(E)=7h(D)=11hD(S0)=12S0的左子树是希望树的左子树是希望树左子树代价：左子树代价：左子树代价：左子树代价：hA(S0)=9例：与例：与/或树的有序搜索或树的有序搜索Step3Step3：h(L)=2，h(M)=6，h(B)=3，h(A)=8，hA(S0)=9终叶节点终叶节点L和和B都是可解节点都是可解节点C无法判断是否可解无法判断是否可解节点节点A和和S0也无法判断也无法判断例：与例：与/或树的有序搜索或树的有序搜索Step4Step4：扩展扩展扩展扩展Ch(N)=2，h(P)=7，h(C)=3，h(A)=8，hA(S0)=9终叶节点终叶节点N、C、B可解可解A可解可解S0可解可解最优解树最优解树什么是博弈？什么是博弈？博弈一直是启发式搜索的一个重要应用领域，早在20世纪60年代就已经出现若干博弈系统，美国IBM公司的“深蓝”系统已达到了国际特级大师级的水平。“二人零和、全信息、非偶然”是最简单的博弈：1.对垒的A、B双方轮流采取行动，结果只有三种情况：A胜B败，A败B胜，双方和局；2.对垒过程中，任何一方都了解当前及过去历史；3.任何一方在采取行动前都要根据当前实际情况，进行得失分析，选取对自己最有利而对对方最不利的对策。博弈树的形成博弈树的形成博弈过程中，设我方为A方，则可供A方选择的若干行动方案之间是“或”关系；在A方行动方案基础上，B方也有若干个可供选择的行动方案，则这些方案对A方来说就是“与”关系。如此，逐层扩展，并用图表示博弈过程，得到的就是一棵与/或树，描述博弈过程的与/或树被称为博弈树。博弈树搜索的特点博弈树搜索的特点博弈的初始格局是初始节点。博弈树中，“或”节点和“与”节点是逐层交替出现的。自己一方扩展的节点之间是“或”关系，对方扩展的节点之间是“与”关系。双方轮流扩展节点。所有能使自己一方获胜的终局都是本原问题，相应节点是可解节点；所有使对方获胜的终局都是不可解节点。问题：如何从众多可供选择的行动方案中选出一个对自己有利的行动方案。最常用的分析方法是最常用的分析方法是最常用的分析方法是最常用的分析方法是极大极小分析法极大极小分析法极大极小分析法极大极小分析法极大极小分析法的基本思想极大极小分析法的基本思想根据问题特性定义一个估价函数。考虑每一方案实施后，对方可能采取的所有行动，利用估价函数估算当前博弈树端节点得分（静态估值）。利用端节点的估值推算其父节点得分（倒推值）。对“或”节点，为了选一个对自己最有利的方案，选其子节点中的最大得分作为父节点得分；对“与”节点，立足于最坏情况，选其子节点中的最小得分作为父节点得分。具有较大倒推值的行动方案就是当前最好的行动方案。倒推值的计算倒推值的计算注意：由于完整的博弈树过于庞大，在博弈问题中，可行的方法是只生成一定深度的博弈树。例：博弈树搜索例：博弈树搜索一字棋一字棋游戏游戏 例：设有如图所示九个空格，A、B二人对奕，轮到谁走谁就往空格上放一只自己的棋子，最先使自己棋子构成三子一线的就获得胜利。设A的棋子用“a”表示，B的棋子用“b”表示，A先走棋。为了不生成太大的博弈树，假设每次仅扩展两层。一字棋一字棋对对对对A A方，设棋局为方，设棋局为方，设棋局为方，设棋局为P P，估价函数，估价函数，估价函数，估价函数e e(P P)定义为定义为定义为定义为 ：若若若若P P是是是是A A必胜的棋局，则必胜的棋局，则必胜的棋局，则必胜的棋局，则e e(P P)=+)=+若若若若P P是是是是B B必胜的棋局，则必胜的棋局，则必胜的棋局，则必胜的棋局，则e e(P P)=-)=-若若若若P P是胜负未定的棋局，则是胜负未定的棋局，则是胜负未定的棋局，则是胜负未定的棋局，则e e(P P)=)=e e(+(+P P)-)-e e(-(-P P)l le e(+(+P P)：P P上可能使上可能使上可能使上可能使a a三子成一线的数目。三子成一线的数目。三子成一线的数目。三子成一线的数目。l le e(-(-P P)：P P上可能使上可能使上可能使上可能使b b三子成一线的数目。三子成一线的数目。三子成一线的数目。三子成一线的数目。b ba ae e(P P)=3-1=2)=3-1=2例：博弈树搜索例：博弈树搜索一字棋一字棋游戏游戏e e(P P)=)=e e(+(+P P)-)-e e(-(-P P)=2-1=1=2-1=1A A的最佳走步的最佳走步的最佳走步的最佳走步A A走走走走S S3 3后，后，后，后，B B的最优选择的最优选择的最优选择的最优选择是是是是S S4 4，因为它的静态估，因为它的静态估，因为它的静态估，因为它的静态估值较小，对值较小，对值较小，对值较小，对A A不利。不利。不利。不利。极大极小法的缺点极大极小法的缺点首先，生成一定深度的博弈树。然后，对端节点进行估值，再计算上层节点的倒推值，效率较低。分析可知：博弈树具有“与”、“或”节点逐层交替出现的特点，如能边生成节点边计算估值及倒推值，就有可能删去一些不必要的节点，从而减少搜索及计算的工作量。-剪枝技术什么是什么是-剪枝技术？剪枝技术？边生成边计算，从而剪去某些分枝的技术。对“与”节点，取当前子节点中最小倒推值作为它的倒推值上界，该值被称为值。对“或”节点，取当前子节点中最大倒推值作为它的倒推值下界，该值被称为值。例：例：-剪枝技术剪枝技术例：设按每次生成两层的原则得到如图所示博弈树。各端节点估值如图所示，其中S6的估值还没有计算出。由由由由S S3 3、S S4 4的估值得到的估值得到的估值得到的估值得到S Sl l的倒推值为的倒推值为的倒推值为的倒推值为3 3。设设设设S S6 6的估值的估值的估值的估值 2 2，则，则，则，则S S2 2的倒推值为的倒推值为的倒推值为的倒推值为2 2，此时，此时，此时，此时，S S0 0的倒推值为的倒推值为的倒推值为的倒推值为3 3。设设设设S S6 6的估值的估值的估值的估值22，则，则，则，则S S2 2的倒推值的倒推值的倒推值的倒推值22，此时，此时，此时，此时，S S0 0的倒推值也为的倒推值也为的倒推值也为的倒推值也为3 3。结论：结论：结论：结论：虽然虽然虽然虽然S S6 6的估值还没有计算出，但的估值还没有计算出，但的估值还没有计算出，但的估值还没有计算出，但不影响对上层节点倒推值的推算，这不影响对上层节点倒推值的推算，这不影响对上层节点倒推值的推算，这不影响对上层节点倒推值的推算，这表示这个分枝可以从博弈树中删去。表示这个分枝可以从博弈树中删去。表示这个分枝可以从博弈树中删去。表示这个分枝可以从博弈树中删去。-剪枝技术剪枝技术的一般规律的一般规律剪枝对“或”节点x，如果x的值不能降低其父节点的值，则对x以下的分枝可停止搜索，并使x的倒推值为。这种剪枝称为剪枝。剪枝对“与”节点x，如果x的值不能升高其父节点的值，则对x以下的分枝可停止搜索，并使x的倒推值为。这种剪枝称为剪枝。S0B BA AD DB BC CB BD DHHGGF FB BD DHHGGN NMML LB BD DHH*P PB BD D*QQB B*I IB B*S SR R2 8 4 1 *-2 *5 9 1 *-5 *21-2 5 1-5251212*So A BC CD DE EF FGGHHI IJ JKK L M N P Q R S T U