资源描述：
《第三章可分解产生式系统的搜索策略》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、第三章可分解产生式系统的搜索策略3.1与或图搜索本章主要内容：1.与或图的解法*2.解图耗散的计算*3.与或图启发搜索算法A0*4.极小极人搜索过程*5.a—B搜索过程一相关概念1.与节点：数据库分解得到的子节点（分解）见图3.1与或图或节点：数据库使用菜规则后得到的子节点（变化）2.K-连接符:从一个父节点指向一组K个后继节点的节点集。（对照图3.1说明，只有1—和2—两种连接符.若全为1—连接符，则为普通图）。3.解节点集N：包含若干目标节点。重点，耍会搜索解图二解图的求法从节点n开始，止确选择一个连接符；再从该连接符所指的每一个后继节点出发，继
2、续选一个连接符，如此下去直到产生的侮一个后继节点成为节点集N中的一个元素为止。（图3.2给出®_｛心,叫｝的三个解图）三解图的耗散计算①若n是N中元素，则K（n,N）=0；②若n有连接符指向后继节点｛%,・・・,％｝,则g,/V）=C“+K（®,"）+•••+K（©,N）其中C”为该连接符的耗散。③最佳解图的耗散——最佳耗散//（n）o图3.2,（力=5。四.能解与不能解「若非终节点有“或”节点时，具子节点至少一个能解，则该节点能解。1.能解节点彳I若非终节点冇“与”节点时，仅当子节点全能解，则该节点能解。「若非终节点有“或”节点时，均不能解，则该节
3、点不能解。2.不能解节点I若非终节点有“与”节点时，至少一个子节点不能解，则该节点不能解。3.2与或图启发搜索算法AO*一、算法：P105（只考虑/?（〃）分量，深度g®）不能说明问题）与A及A*算法的区别：4—6步完成口顶向下的图生成，7—12步完成口下而上的料散值修正计算，进行连接符的标记及节点能解标记。3.3博弈树的搜索讨论双人完备信息I•専弈问题的搜索策略。双人完备信息：两位对手轮流走，知道对方询而的走步，能估计出对方未来的走步可能。1分钱币游戏图3.4MIN——人，MAX——计算机，每个选手每次将其中一堆分成数目不等的两小堆，直到某选手无法
4、再分成不等的小堆为输。状态图3.4计算机必须考虑应対人的每种方法，故可看成与节点；而计算机判断清楚以后，只选其中一种方法，看成或节点，实际是与或图搜索。图中粗线表示计算机致胜的与或解图。解图代表了从开局到终局的弈法，这対许多博弈问题不可实现。应把目标确定为寻找一步好棋，等对手回应后再找另一步好棋的实用策略。一一极小极大搜索过程。重点，要会搜索2极小极大搜索过程看出未来儿步棋（有限深度）后，从当询可能走的步中选一步相对好棋来走。有极值棋局佔计函数/（刃Y均态MAX取++8MAX赢MIN収・・ooMIN赢取0（MAX——程序方，MIN——人，MAX先走）
5、图3.5是一个考虑两步棋的例子：M1N层取最小（有利于选手，按最坏打算）,MAX层取最大（不利于选手）。算法见P14（不细讲）：笫一•阶段A④：宽度优先法牛成规定深度的全部博弈树，计算/（卩）值；第二阶段⑥一⑧：从底向上倒推估值，直到初始节点S,由/（$）选较好的走步，对手响应后，以当前状态为S,重复调用该过程。例题：3X3—字棋：九宫棋盘轮流下子，谁先成三字一线即胜。程序方（MAX）先走,棋子“X”，人方（MIN）为“0”，设搜索两步棋。/（〃）规定为：MAX三子成线的可能数-MIN三子成线的可能数。若P是MAX胜节点，取f（p）=8,若MIN获胜
6、，取f（p）=-^QMAX第一次走步前的搜索：（考虑对称性）213221MAX第三步搜索（略画）。3a—B搜索过程是对MIN/MAX过程的改进。皿佩冰法先生成全部规定深度搜索树，然后再进行端节点估值和倒推计算，显然降低效率。如图3.8。基本思想：不一定牛•成全部搜索树再倒推估值（例一g）,把生成节点与估值结合起来，即：深度优先生成节点后马上估值，再根据一定的条件判定，尽早剪掉无用的分支。例：如图3.9—字棋。说明：深度优先生成完第6个节点后，即可判定第1个节点倒推值为一1,这说明：s节点的倒推值不会小于一1（因其取下层的极人值）；称为极人层的下界«=
7、-1;当生成第8个节点估值一1后，说明：第7个节点的倒推值不会大于一1,可立即取为一1,没有必要再生成节点7其余子节点。（因为，比一1大min层取极小值也収不上而月•即使比一1小，对于s也无用，因其取下层最大）。称为极小层的上界B=—l。这样，只要搜索时记住a、B值，并时时比较，即可尽早“剪枝”。搜索过程中，a、B值可能修改，但a值永不下降，B值永不上升。S的倒推值最终为后续节点倒推值中的最人者。本章小结：•与或图的求解就是找到从岀事节点到终节点集的一个解图；•AC/算法当h(n)Wh*(n)且单调吋，一•定能找到最佳解图；•“有限搜索后寻找一步好棋
8、”是解决烛弈树搜索的实用方法。极小极人法就是这个思想。a-P搜索是对其改进，可提高效率。思考题：能否画搜索3
