《可分解产生式系统的搜索策略.docx》由会员分享，可在线阅读，更多相关《可分解产生式系统的搜索策略.docx（4页珍藏版）》请在三一文库上搜索。
1、第三章可分解产生式系统的搜索策略3.1与或图搜索本章主要内容：1 .与或图的解法*- . .- . .一- *2 .解图耗散的计算3 .与或图启发搜索算法AO*4 .极小极大搜索过程*5. a 3搜索过程一相关概念1 .与节点：数据库分解得到的子节点(分解)见图3.1与或图或节点：数据库使用某规则后得到的子节点(变化)2 .K一连接符：从一个父节点指向一组 K个后继节点的节点集。(对照图3.1说明，只有1和2两种连接符.若全为1一连接符，则为普通图)3 .解节点集N:包含若干目标节点。重点，要会搜索解图二解图的求法从节点n开始，正确选择一个连接符；再丛该连接符所指的每一个后继节点出发， 继续选
2、一个连接符，如此下去直到产生的每一个后继节点成为节点集N中的一个元素为止。(图3.2给出n0T %7,n8的三个解图)三解图的耗散计算若n是N中元素，则K (n, N) =0;若n有连接符指向后继节点 .1，n I则k(n,N) =Cn K(n1, N)K(a ,N)其中Cn为该连接符的耗散。最佳解图的耗散一一最佳耗散 h (n)。图3.2, h (n)=5。四.能解与不能解若非终节点有“或”节点时，其子节点至少一个能解，则该节点能解。1 .能解节点4i若非终节点有“与”节点时，仅当子节点全能解，则该节点能解。若非终节点有“或”节点时，均不能解，则该节点不能解。2 .不能解节点I若非终节点有“
3、与”节点时，至少一个子节点不能解，则该节点不能解。3.2 与或图启发搜索算法 AO*、算法：P105 (只考虑h(n)分量，深度g(n)不能说明问题)与A及A*算法的区别：46步完成自顶向下的图生成，712步完成自下而上的耗散值修正计算，进行连接符的标记及节点能解标记。3.3 博弈树的搜索讨论双人完备信息博弈问题的搜索策略。双人完备信息：两位对手轮流走，知道对方前面的走步，能估计出对方未来的走步可能。1分钱币游戏图3.4 MIN 人，MAX 计算机，每个选手每次将其中一堆分成数目不等的两 小堆，直到某选手无法再分成不等的小堆为输。状态图3.4计算机必须考虑应对人的每种方法，故可看成与节点；而计
4、算机判断清楚以后，只 选其中一种方法，看成或节点，实际是与或图搜索。图中粗线表示计算机致胜的与或解 图。解图代表了从开局到终局的弈法，这对许多博弈问题不可实现。应把目标确定为寻 找一步好棋，等对手回应后再找另一步好棋的实用策略。一一极小极大搜索过程。重点，要会搜索2极小极大搜索过程看出未来几步棋（有限深度）后，从当前可能走的步中选一步相对好棋来走。有极值f MAX 取+8 MAX赢棋局估计函数 f（p） V MIN 取- -8 MIN赢均态取0（MAX程序方，MIN人，MAXt走）图3.5是一个考虑两步棋的例子：MIN层取最小（有利于选手，按最坏打算） ，MAX层取最大（不利于选手）。算法见P
5、14 （不细讲）：第一阶段一：宽度优先法生成规定深度的全部博弈树，计算f（p）值;第二阶段一：从底向上倒推估值，直到初始节点S,由f （s）选较好的走步，对手响应后，以当前状态为 S,重复调用该过程。例题：3X3 一字棋：九宫棋盘轮流下子，谁先成三字一线即胜。程序方（ MAX先走, 棋子“ X”，人方（MIN ）为“ 0”，设搜索两步棋。f （p）规定为：MAX三子成线的可能数一 MIN三子成线的可能数。若P是MAX胜节点，取f （p） = 8,若MIN获胜，取f （ p） = *。MAX第一次走步前的搜索：（考虑对称性）10 TO -2MAXI二轮走步前的搜索（设对方走成 -fr ）:322
6、MA通三步搜索（略画） 3 a 3搜索过程是对MIN/MA）过程的改进。MIN/MAX法先生成全部规定深度搜索树，然后再进行端节点估值和倒推计算，显然降低效率。如图 3.8。基本思想：不一定生成全部搜索树再倒推估值（例-8）,把生成节点与估值结合起来，即：深度优先生成节点后马上估值，再根据一定的条件判定，尽早剪掉无用的分支 例：如图3.9 一字棋。说明：深度优先生成完第 6个节点后，即可判定第 1个节点倒推值为-1,这说明：s节点的倒推值不会小于一1 （因其取下层的极大值）；称为极大层的下界 ”=1;当生成第8个节点估值一1后，说明：第7个节点的倒推值不会大于一1,可立即取为-1,没有必要再生成节点 7其余子节点。（因为，比-1大min层取极小值也取不上, 而且即使比一1小，对于s也无用，因其取下层最大）。称为极小层的上界 3= 1。这样，只要搜索时记住 “、3值，并时时比较，即可尽早“剪枝”。搜索过程中，“、3值可能修改，但a值永不下降，3值永不上升。S的倒推值最终 为后续节点倒推值中的最大者。本章小结：与或图的求解就是找到从出事节点到终节点集的一个解图；AO*算法当h (n) w h* (n)且单调时，一定能找到最佳解图；“有限搜索后寻找一步好棋”是解决博弈树搜索的实用方法。极小极大法就是这个思想。“ 一3搜索是对其改进，可提高效率。思考题：能否画搜索3步棋的搜索树？