文档介绍：第三章可分解产生式系统的搜索策略
与或图搜索
本章主要内容:
与或图的解法*
解图耗散的计算*
与或图启发搜索算法AO*
极小极大搜索过程*
α—β搜索过程
一相关概念
:数据库分解得到的子节点(分解)
或节点:数据库使用某规则后得到的子节点(变化) 与或图
—连接符:从一个父节点指向一组K个后继节点的节点集。
(,只有1—和2——连接符,则为普通图)。
3. 解节点集N:包含若干目标节点。
二解图的求法重点,要会搜索解图
从节点n 开始,正确选择一个连接符;再丛该连接符所指的每一个后继节点出发,
继续选一个连接符,如此下去直到产生的每一个后继节点成为节点集N中的一个元素
为止。
( 给出的三个解图)
三解图的耗散计算
若n 是N中元素,则K(n,N)=0;
若n 有连接符指向后继节点,则

其中为该连接符的耗散。
③最佳解图的耗散——最佳耗散。,=5。
四. 能解与不能解
若非终节点有“或”节点时,其子节点至少一个能解,则该节点能解。
能解节点
若非终节点有“与”节点时,仅当子节点全能解,则该节点能解。
若非终节点有“或”节点时,均不能解,则该节点不能解。

若非终节点有“与”节点时,至少一个子节点不能解,则该节点不能解。
*
一、算法:P105 (只考虑分量,深度不能说明问题)
与A及A*算法的区别:4—6步完成自顶向下的图生成,7—12步完成自下而上的耗
散值修正计算,进行连接符的标记及节点能解标记。
博弈树的搜索
讨论双人完备信息博弈问题的搜索策略。
双人完备信息:两位对手轮流走,知道对方前面的走步,能估计出对方未来的走步可能。
1 分钱币游戏
图 MIN——人,MAX——计算机,每个选手每次将其中一堆分成数目不等的两
小堆,直到某选手无法再分成不等的小堆为输。

计算机必须考虑应对人的每种方法,故可看成与节点;而计算机判断清楚以后,只
选其中一种方法,看成或节点,实际是与或图搜索。图中粗线表示计算机致胜的与或解
图。
解图代表了从开局到终局的弈法,这对许多博弈问题不可实现。应把目标确定为寻
找一步好棋,等对手回应后再找另一步好棋的实用策略。——极小极大搜索过程。
2 极小极大搜索过程重点,要会搜索
看出未来几步棋(有限深度)后,从当前可能走的步中选一步相对好棋来走。
有极值 MAX 取+ +∞ MAX赢
棋局估计函数 MIN 取‐‐∞ MIN 赢
均态取0
(MAX——程序方,MIN——人,MAX先走)
:MIN层取最小(有利于选手,按最坏打算),MAX
层取最大(不利于选手)。
算法见P14(不细讲):
第一阶段②—④:宽度优先法生成规定深度的全部博弈树,计算值;
第二阶段⑥—⑧:从底向上倒推估值,直到初始节点S,由选较好的走步,
对手响应后,以当前状态为S,重复调用该过程。
例题:3×3一字棋:九宫棋盘轮流下子,谁先成三字一线即胜。程序方(MAX)先走,
棋子“X”,人方(MIN)为“0”,设搜索两步棋。