资源描述：
《4-与或图搜索》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、1与或图搜索人工智能2主要内容与或图的概念与或树搜索博弈树搜索（重点）人工智能3与或图的概念在上一章状态空间搜索的问题中，一个问题可以有几种求解方法，只要其中一种方法可以求解，则该问题就可以求解。即该节点的后继节点之间是“或”的关系，即只要一个后继节点能够求解，则该节点也就可以求解了。从初始节点到目标节点之间，可以得到一条由节点序列组成的求解路径但现实世界中，有时一个问题也可能需要求解几个子问题，这些子问题必须全部求解，才可求解原始问题，即这些子问题之间是“与”的关系。这类问题可以用与或图表示人工智能4与或图的概念对于一个复杂问
2、题，直接求解往往比较困难。此时，可以通过下述方法进行简化分解等价变换人工智能5分解把一个复杂问题分解为若干个较简单的子问题，每个子问题又继续分解为若干个更简单的子问题，重复此过程，直到不需要再分解或者不能在分解为止。然后对每个子问题分别求解，最后把各子问题的解复合起来就得到了原问题的解。这时子节点间是“与”关系通常用一条弧把各边连接起来构成的图称为“与图”若一节点有k个与关系子节点，则称该节点有一个k-连接符…...K个人工智能6等价变换对于复杂问题，除了可用“分解”方法进行求解外，还可利用等价变换，把它变换为若干个较容易求解的
3、新问题，若新问题中有一个可解，则就得到了原问题的解问题的等价变换过程，也可用一个图表示，称为“或图”…...人工智能7与或图目标目标初始节点sabc与图和或图结合起来使用，此时的图称为“与或图”，其中既有“与”节点，也有“或”节点后面介绍的更多的是“与或树”人工智能8与或图的其他概念本原问题不能在分解或变换，而且直接可解的子问题端节点与终止节点没有子节点的节点称为端节点本原问题对应的节点称为终止节点终止节点一定是端节点，端节点不一定是终止节点人工智能9与或图的其他概念可解节点在与或树中，满足下列条件之一的称为可解节点是一个终止节
4、点是一个“或”节点，且其子节点中至少有一个是可解节点是一个“与”节点，且其子节点全部是可解节点不可解节点不是可解节点的节点解树由可解节点构成，且由这些可解节点可推出初始节点（对应于原始问题）为可解节点的子树称为解树在解树中一定包含初始节点人工智能10AO*算法也是一种启发式搜索算法，与A*算法有些类似具体算法步骤（略）人工智能112.3博弈树搜索博弈诸如下棋、打牌、战争等一类竞争性智能活动称为博弈最简单的一种博弈具有以下特征二人零和双方对垒，轮流采取行动；对一方有利的对另一方必然不利；博弈结果只能有三种情况：A胜B败、B胜A败、
5、平局全信息对垒过程中，双方都了解当前格局及过去的历史非偶然双方都是理智的分析决定自己的行动，不存在“碰运气”的偶然因素人工智能12博弈树在博弈过程中，任何一方都希望自己取得胜利。因此，在某一方当前有多个行动方案可供选择时，他总是挑选对自己最有利而对对方最不利的那个方案行动。如果我们站在A方立场，则可供A选择的若干方案之间是“或”关系，因为主动权在A方手里，他或者选择这个方案，或者选择另一个方案，完全由A决定但若B也有若干可供选择的方案，则对A来说这些方案之间是“与”关系，因为这时主动权在B，这些可供选择的方案中的任何一个都可能被
6、B选中，A必须考虑对自己最不利的情况的发生把上述博弈过程用图表示出来，得到的是一棵“与／或”树注意：该“与／或”树是始终站在某一方（例如Ａ方）的立场上得出的，不能一会站在Ａ方立场，一会又站在Ｂ方立场人工智能13博弈树的特点博弈的初始格局是初始节点在博弈树中，“或”节点和“与”节点是逐层交替出现的己方扩展的节点之间是“或”关系对方扩展的节点之间是“与”关系双方轮流扩展节点所有能使己方获胜的终局都是本原问题，相应的节点是可解节点；所有使对方获胜的终局都是不可解节点人工智能14例—分钱币问题有一堆数目为Ｎ的钱币，由两位选手轮流进行分堆
7、，要求每个选手每次只把其中某一堆分成数目不等的两小堆，直到有一位选手无法把钱币再分成不相等的两堆时就得认输人工智能15分钱币问题 状态空间图及搜索解图（7）（6,1）（5,2）（4,3）（5,1,1）（4,2,1）（3,2,2）（3,3,1）（4,1,1,1）（3,2,1,1）（2,2,2,1）（3,1,1,1,1）（2,2,1,1,1）（2,1,1,1,1,1）对方先走我方必胜人工智能16对于较简单的博弈问题，可以求出解图，解图代表了从开局到终局任何阶段上的弈法，但这对于复杂的博弈问题是不可能实现的在博弈问题中，每个格局可供选
8、择的行动方案有很多，因此会生成十分庞大的博弈树。中国象棋一盘棋平均走50步，总状态数约为10161。假设1毫微秒走一步，约需10145年。西洋跳棋博弈树约有1040个节点围棋结论：不可能穷举。试图利用完整的博弈树来进行分析是很困难的人工智能17博弈树搜索可行的办
