3.4 小结

　　1．用可分解产生式系统求解问题时，求解过程可归结为对一个隐含的与或图进行搜索。初始数据库对应于与或图的根节点，规则对应于k-连接符，结束条件的数据库对应于一组终节点集会，搜索策略的任务就是找到从初始节点到一组终节点集N的一个解图。解图及其耗散值可由递归定义给出。
　　2．与或图的启发式搜索算法AO*是通过评价函数f（n）＝h（n）来引导搜索过程，适用于分解之后得到的子问题不存在相互作用的情况。若S→N集存在解图，当h（n）≤h*（n）且h（n）满足单调限制条件时，AO*算法一定能找到最佳解图，即在这种情况下，AO*具有可采纳性。
　　3．博弈问题可用产生式系统来描述，求解过程也是一个对与或图进行搜索的问题。本章主要讨论双人完备信息的博弈问题，一般意义下求解的策略是要找到一个完全取胜的解图。实际上只有简单的博弈或复杂博弈的残局，这种完全取胜的策略才可行。通常可行的实用策略是搜索被限制在一定的范围，搜索的目标是确定一步好棋，等对手回手后，再继续搜索。MINIMAX就是按这种思想建立的过程，而α-β过程是MINIMAX过程的改进，并可提高效率。还有其他一些改善MINIMAX的方法。