人工智能与知识工程-搜索推理技术1

1、1,3.1 图搜索策略 3.2 盲目搜索 3.3 启发式搜索 3.4 博弈树搜索,3搜索推理技术,2,从问题表示到问题的解决，有一个求解的过程。常见的AI问题求解技术有两种，即“搜索”（Search）和“推理”（Reasoning）方法。 搜索是AI研究的一个重要课题，几乎所有的AI问题都可以被归结为搜索问题。各种搜索技术的研究是AI初期（1956 1970）的“热门”课题。虽然现在已有不少成熟的搜索技术出现于AI手册和各种AI书籍中，并在一些知识系统种得到广泛应用。但搜索效率的提高仍然是现在和今后AI研究者关心的一个重要问题。 问题求解的第二种方法是逻辑推理。通过构造一个逻辑系统，由它可以从

2、已有的断言（公理）推导出新的断言。并用逻辑形式语言描述的一组公理来表达问题域。用这种方法来解决问题就是通过推理来积聚越来越多的断言，直到获得问题的解答。 虽然问题求解可通过搜索方法，也可用逻辑推理，但二者的侧重点是不一样的。前者着重于寻求问题解答的过程，而后者强调前提（初始）问题空间（公理集合）与问题解答间连接的逻辑正确性。或者简单地讲，搜索着重于发现（Discovery），而推理强调证明（Proof）。,3,3.1图搜索策略,3.1.1 问题求解的过程 3.1.2 图搜索的一般过程,4,3.1.1问题求解的过程,1.问题的表示: 主要采用状态空间法(状态空间图)和问题归约法(与或图)。 2.

3、问题的求解: 通过在图(“状态空间图”或”与或图”)中进行搜索, 寻找一条路径的方法. 一般搜索: 从初始节点出发, 扩展节点, 并沿子节点推进, 继续扩展选择的子节点, 直到找到通向目标结点的路径, 或找到解树为止。 肓目搜索:是按预定的控制策略进行搜索, 在搜索过程中获得的中间信息并不改变控制策略。 启发式搜索: 是在搜索过程中加入了与问题有关的启发性信息, 缩小问题的搜索范围，指导搜索朝着最有希望的方向前进，以尽快地找到问题的（最优）解。,5,3.1.2图搜索的一般过程,例：从某王姓家族的四代中找王A的后代且其寿命为X的人。 王A：寿命47，有儿子王B1、王B3、王B2王B1：寿命77，

4、有儿子王C1、王C2王B3：寿命52，有儿子王D1王B2：寿命65，有儿子王E1、王E2王F1：寿命32王G1：寿命96王C2：寿命87，有儿子王F1王D1：寿命77，没有儿子王E1：寿命57，有儿子王G1王E2：寿命92，有儿子王H1 王C1：寿命27，没有儿子王H1：寿命51若X=57， 如果是一个N代的家族表中找其寿命为X的人，我们最可能用的手工方法是从家族表的开始往下，例中还要求所找的人是某人的后代，就比较复杂了。如果用图来表示，就很容易了。图中把姓氏省去，每个成员的后代按例子中给出名字的先后顺序。,6,3.1.2图搜索的一般过程(续),图搜索策略可看作一种在图中寻找路径的方法。初始节

5、点和目标节点分别代表初始数据库和满足终止条件的数据库。求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。研究图搜索的一般策略，能够给出图搜索过程的一般步骤。,7,3.1.2图搜索的一般过程（续）,数据结构: OPEN：未扩展节点表 CLOSED：已扩展节点表 算法过程 (1) 建立一个只含有起始节点S的搜索图G, 把S放到一个叫作OPEN的未扩展节点表中; (2) 建立一个叫做CLOSED的已扩展节点表, 其初始为空表; (3) LOOP: 若OPEN表是空表, 则失败退出; (4) 选择OPEN表上的第一个节点,把它从OPEN表移出并放进CLOSED表中,称此节点

6、为节点n; (5) 若n为一目标节点,则有解并成功退出, 此解是追踪图G中沿着指针从n到S这条路径而得到的(指针将在第(7)步中设置);,8,3.1.2图搜索的一般过程（续）,(6) 扩展节点n，同时生成不是n的祖先的那些后继节点的集合M，把M的这些成员作为n的后继节点添入图G中； (7) 对那些未曾在G中出现过的(即未曾在OPEN表上或CLOSED表中出现过的)M成员设置一个通向n的指针, 把M的这些成员加进OPEN表。 对已经在OPEN或CLOSED表上的每一个M成员，确定是否需要更改通到n的指针方向。 对已在CLOSED表上的每个M成员，确定是否需要更改图G中通向它的每个后裔节点的指针方

7、向； (8) 按某一任意方式或按某个探试值, 重排OPEN表; (9) Go Loop。,9,3.1.2图搜索的一般过程（续）,图搜索过程框图,10,3.1.2图搜索的一般过程（续）,过程说明: 搜索图: 图搜索的一般过程生成一个明确的图G, 称为搜索图。 搜索树: 图搜索的一般过程生成G的一个子集T称为搜索树。 由步骤(7)中设置的指针来确定。 G中每个节点(S除外)都有一个只指向G中一个父辈节点的指针, 该父辈节点就定为树中那个节点的惟一父辈节点。 OPEN表上的节点都是搜索图上未被扩展的端节点, 而CLOSED表上的节点, 或者是已被扩展但没有生成后继节点的端节点, 或者是搜索树的非端节

8、点。,11,3.1.2图搜索的一般过程（续）, 步骤(8)对OPEN表上的节点进行排序, 以便选出一个”最好”的节点作为步骤(4)扩展使用。 (1) 排序可以是任意的即肓目的(盲目搜索) (2) 可以用启发信息为依据(启发式搜索) 当扩展某个节点时, 搜索图已经保存了从初始节点到该节点的搜索树。 每当被选作扩展的节点为目标节点时,这一过程就宣告成功结束。 这时，从目标节点按指向父节点的指针不断回溯,能够重现从起始节点到目标节点的成功路径。 当搜索树不再剩有末被扩展的端节点时(即OPEN表为空时)，过程就以失败告终。 从起始节点, 达不到目标节点。,12,3.1.2图搜索的一般过程（续）, 步骤

9、(6)扩展节点时, 生成一个节点的所有后继节点。 步骤(7)的说明: 特别地用于启发式搜索,扩展节点1以前的搜索图 扩展节点1以后搜索图,13,3.2盲目搜索,3.2.1 宽度优先搜索 3.2.1 深度优先搜索 3.2.3 等代价搜索,14,3.2.1宽度优先搜索,宽度优先搜索： 如果搜索是以接近起始节点的程度来依次扩展节点，那么这种搜索叫做宽度优先搜索(breadth-first search)。 特点：这种搜索是逐层进行的；在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。,15,3.2.1宽度优先搜索（续）,宽度优先搜索算法: (1) 把起始节点放到OPEN表中(如果该起始节点

10、为一目标节点,则求得一个解答)。 (2) 如果OPEN是个空表则没有解，失败退出，否则继续。 (3) 把第一个节点(节点n) 从OPEN表移出，并把它放入CLOSED的扩展节点表中。 (4) 扩展节点n，如果没有后继节点，则转向步骤(2)。 (5) 把n的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针。 (6) 如果n的任一个后继节点是个目标节点, 则找到一个解答，成功退出，否则转向步骤(2)。,16,3.2.1宽度优先搜索（续）,宽度优先搜索算法说明: (1) 搜索树: 搜索过程产生的节点和指针构成一棵隐式定义的状态空间图的子树,称为搜索树。 (2) 如果问题有解, 宽度

11、优先算法能够保证找到一条通向目标节点的最短路径(即找到最优解)。 (3) 如果问题无解，对于有限图，该算法会失败退出；对于无限图，则永远不会终止。 (4)宽度优先搜索是图搜索一般过程的特殊情况，将图搜索一般过程中的第8步具体化为本算法中的第6步，这实际是将OPEN表作为“先进先出”的队列进行操作。,17,3.2.1宽度优先搜索（续）,18,3.2.1宽度优先搜索（续）,例: 八数码难题， 在33的方格棋盘上，分别放置了标有数字1,2,3,4,5,6,7,8的八张牌，初始状态如图S0所示， 目标状态如图Sg所示，要求应用宽度优先搜索策略寻找从初始状态到目标状态的解路径。,19,3.2.1宽度优先

12、搜索（续）,八数码难题的宽度优先搜索树,20,3.2.2深度优先搜索,深度优先搜索： 在搜索过程中，首先扩展最新产生的(即最深的)节点，深度相等的节点可以任意排列，这种搜索叫做深度优先搜索 (depth-first search) 。 特点：首先，扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进行下去；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代的路径。,21,3.2.2深度优先搜索（续）,节点深度: (1) 起始节点(即根节点)的深度为0。 (2) 任何其他节点的深度等于其父辈节点的深度加1。 深度界限: 为了避免考虑太长的路径(防止搜索过程沿着无益的路径扩展

13、下去), 往往给出一个节点扩展的最大深度, 称为深度界限。 任何节点如果达到了深度界限,那么都将把它们作为没有后继节点来处理。 即使应用了深度界限, 深度优先搜索所求得的解答路径也不一定就是最短路径。,22,3.2.2深度优先搜索（续）,含有深度界限的深度优先搜索算法: (1) 把起始节点S放到未扩展节点OPEN表中。如果此节点为一目标节点,则得到一个解。 (2) 如果OPEN为一空表,则失败退出。 (3) 把第一个节点(节点n)从OPEN表移到CLOSED表。 (4) 如果节点n的深度等于最大深度,则转向步骤(2)。 (5) 扩展节点n, 产生其全部后裔,并把它们放入OPEN表的前头。如果没

14、有后裔，则转向步骤(2)。 (6) 如果后继节点中有任一个为目标节点,则求得一个解,成功退出;否则,转向步骤(2)。,23,24,3.2.2深度优先搜索（续）,八数码难题深度界限为5的深度优先搜索树,25,3.2.3等代价搜索,宽度优先的局限: 在宽度优先搜索中作了一种假设, 认为状态空间中各边的代价都相同, 且都为一个单位量。从而可用路径的长度代替路径的代价。 然而, 对许多问题这种假设是不现实的, 它们的状态空间中的各个边的代价不可能完全相同。 例: 城市交通问题。 为此, 需要在搜索树中给每条边都标上其代价。 代价树: 在搜索树中给每条边都标上其代价。这种边上标有代价的树称为代价树。 等

15、代价搜索: 寻找从起始状态至目标状态的具有最小代价的路径问题, 叫做等代价搜索。在等代价搜索算法中, 是沿着等代价路径断层进行扩展的。,26,3.2.3等代价搜索（续）,例: 城市交通问题. 设有5个城市, 它们之间的交通路线如图所示, 图中的数字表示两个城市之间的交通费用,即代价。用等代价搜索, 求从A市出发到E市, 费用最小的交通路线。,27,3.2.3等代价搜索（续）,解: 其代价搜索树如右下图:最优解: A,C,D,E,28,3.2.3等代价搜索（续）,记号 c(i, j): 从节点I 到其后继节点j 的连接弧线代价。 g(i):从起始节点S到任一节点i 的路径代价(即是从起始节点S到

16、节点i 的最少代价路径上的代价),29,3.2.3等代价搜索（续）,等代价搜索算法: (1) 把起始节点S放到未扩展节点有OPEN中。如果此起始节点为一目标节点,则求得一个解，否是令g(S)=0。 (2) 如果OPEN是个空表,则没有解而失败退出。 (3) 从OPEN表中选择一个节点I,使其g(i)为最小。如果有几个节点都合格,那么就要选择一个目标节点作为节点i(如果有目标节点的话)，否则，就从中选一个作为节点i，把节点i从OPEN表移至扩展节点表CLOSED中。,30,3.2.3等代价搜索（续）,(4) 如果节点i 为目标节点,则求得一个解。 (5) 扩展节点i。如果没有后继节点，则转向步骤

17、(2); (6) 对于节点i的每个后继节点j ,计算g(j)=g(i)+c(i,j), 并把所有后继节点j 放进OPEN表.提供回到节点i的指针。 (7) 转向步骤(2)。,31,32,3.3启发式搜索,3.3.1 启发式搜索策略和估价函数 3.3.2 有序搜索 3.3.3 A*算法 3.3.4 图搜索策略的评价,33,3.3启发式搜索（续）,盲目搜索存在的问题 扩展节点数目较多。 效率低， 耗费过多的计算时间和空间。 分析前面介绍的宽度优先、深度优先搜索，或等代价搜索算法,其主要的差别是OPEN表中待扩展节点的顺序问题。如果找到一种方法用于排列待扩展节点的顺序，即选择最有希望的节点加以扩展，

18、那么，搜索效率将会大为提高。,34,3.3.1启发式搜索策略和估价函数,启发性信息：指那种与具体问题求解过程有关的，并可指导搜索过程朝着最有希望方向前进的控制信息。三种启发性信息： (1) 用于决定要扩展的下一个节点，以免像在宽度优先或深度优先搜索中那样盲目地扩展。 (2) 在扩展一个节点的过程中，用于决定要生成哪一个或哪几个后继节点，以免盲目地同时生成所有可能的节点。 (3) 用于决定某些应该从搜索树中抛弃或修剪的节点。 启发式搜索： 利用启发信息的搜索方法叫做启发式搜索。,35,3.3.1启发式搜索策略和估价函数（续）,估价函数(evaluation function): 用于度量节点的”

19、希望”(此节点在通向目标结点的最佳路径上的”希望”)的量度。 记号f (n) : 表示节点n的估价函数值。 用函数f (n)的值来排列图搜索的一般算法中的OPEN表中节点。 节点按递增顺序排列, 即优先扩展具有低估价值的节点, 根据低估价值节点更有可能处在最佳路径上。,36,3.3.2有序搜索,有序搜索：应用某个算法(例如等代价法)选择OPEN表上具有最小f值的节点作为下一个要扩展的节点，这种搜索方法叫做有序搜索或最佳优先搜索， 其算法就叫做有序搜索算法（ordered search）或最佳优先算法（best-first search）。 有序搜索总是选择最有希望的节点作为下一个要扩展的节点.

20、,37,3.3.2有序搜索(续),有序搜索算法: (1) 把起始节点S放到OPEN表中， 计算f(S),并把其值与节点S联系起来。 (2) 如果OPEN表是个空表,则失败退出，无解。 (3) 从OPEN表中选择一个f值最小的节点i，结果有几个节点合格,当其中有一个为目标节点时，则选择此目标节点,否则就选择其中任一个节点作为节点i。 (4) 把节点i 从OPEN表中移出，并把它放入CLOSED 的扩展节点表中。 (5) 如果i是个目标节点，则成功退出，求得一个解，,38,3.3.2有序搜索(续),(6) 扩展节点i， 生成其全部后继节点。对于i的每一个后继节点j: a) 计算f(j)。 b) 如

21、果j既不在OPEN表中，也不在CLOSED表中，则用估价函数f把它添入OPEN表，从j加一指向父辈节点i的指针(以便找到目标节点时记住一个解答路径)。 c) 如果j已在OPEN表或CLOSED表上，则比较刚刚对j计算过的f值和前面计算过的该节点在表中的f值.如果新的f值较小，则 I . 以此新值取代旧值。 II. 从j指向i,而不是指向它的父辈节点。 III. 如果节点j在CLOSED表中,则把它移回OPEN表。 (7) 转向(2),即GOTO(2);,39,3.3.2有序搜索(续),40,3.3.2有序搜索(续),在有序搜索中 定义f(i)为节点i的深度, 则退化为宽度优先算法搜索。 定义f

22、(i)为从起始节点至节点i这段路径的代价, 则退化为等代价搜索。 估价函数的作用 f的选择直接决定了有序搜索中被扩展节点的数目,即直接影响了搜索算法的效率。 对搜索结果具有决定性的作用，如果选择不合适，有序搜索就可能失去一个最好的解甚至全部的解。 估价函数的选择，如果没有适用的准确的希望量度，那么f的选择将涉及两个方面的内容：一方面是时间和空间之间的折衷方案；另一方面是保证有一个最优的解或任意解。 一个节点处在最佳路径上的概率； 求出任意一个节点与目标节点集之间的距离度量或差异度量； 根据格局（博弈问题）或状态的特点来打分。,41,3.3.2有序搜索(续),例: 八数码难题.设问题的初始状态S

23、0和目标状态Sg如图所示, 定义估价函数为: f(n)=d(n)+W(n) 其中, d(n)表示节点n在搜索树中的深度; W(n)表示节点n中”不在位”的数码个数. 请计算初始状态S0的估价函数值f(S0). 解: 对初始节点S0, 由于d(n)=0, W(n)=4, 因此有: f(S0)=4,42,八数码难题有序搜索树,43,3.3.3 A*算法,估价函数f(n)的定义: 是从起始节点约束地通过节点n而到达目标节点的最小代价路径的代价的一个估计。 估价函数的形式: f(n)=g(n)+h(n) 其中, g(n)是从初始节点S0到节点n的实际代价; h(n)是从节点n到目标节点Sg的最优路径的

24、估计代价。,44,3.3.3 A*算法（续）,定义3.1 在GRAPHSEARCH过程中, 如果步骤(8)的重排OPEN表是依据f (n) = g (n) + h (n)进行的, 则称该过程为A算法。 说明: 在图搜索的一般算法中, 在搜索的每一步都利用估价函数f(n)=g(n)+h(n)对Open表中的节点进行排序, 找出一个最有希望的节点作为下一次扩展的节点,则该搜索算法称为A算法。,45,3.3.3 A*算法 （续）,例: 八数码难题。设问题的初始状态和目标状态如图所示, 估价函数为: f (n) = d(n) + W(n) 其中, d(n)表示节点n在搜索树中的深度; W(n)表示节点

25、n中”不在位”的数码个数。,46,3.3.3 A*算法 （续）,记号: k (ni, nj): 表示任意两个节点ni和nj之间最小代价路径的实际代价(对于两节点间没有通路的节点,函数k没有定义). h*(n):表示整个目标节点集合ti上所有k(n,ti)中最小的一个, 即从节点n 到目标节点最优路径的实际代价。 g*的定义: g*(n) = k (S, n) f*的定义: f*(n) = g*(n) + h*(n),47,3.3.3 A*算法 （续）,估价函数f 是f*的一个估计: f (n) = g (n) + h (n) 其中g (n)是g*(n)的估计, h (n)是h*(n)的估计。

26、g (n), 通常为从S到n这段路径的实际代价则有g (n) g*(n) h (n):是从节点n到目标节点Sg的最优路径的估计代价。它的选择依赖于有关问题领域的启发信息， 叫做启发函数。 例如八数码中的W(n)。,48,3.3.3 A*算法 （续）,定义3.2 在A算法中, 如果对所有的n存在h(n)h*(n),则称h(n)为h*(n)的下界。 定义3.3 采用h*(n)的下界h(n)为启发函数的A算法, 称为A*算法. 当h=0时, A*算法就变为有序搜索算法。 说明:当定义的启发函数h(n)是h*(n)的下界, 即对任意的节点n均有h(n) h*(n)。那么这时的A算法就称为A*算法。,4

27、9,3.3.3 A*算法 （续）,例: 八数码难题. 设问题的初始状态和目标状态如前图所示, 估价函数为: f (n) = d(n) + W(n) 其中, d(n)表示节点n在搜索树中的深度; W(n)表示节点n中”不在位”的数码个数. d(n)是对g*(n)的一个估计，d(n) g*(n) W(n)是对h*(n)的一个估计,50,3.3.3 A*算法 （续）,算法步骤: (1) 把S放入OPEN表,记f =h,令CLOSED为空表。 (2) 重复下列过程, 直至找到目标节点为止。若OPEN为空表,则宣告失败。 (3) 选取OPEN表中未设置过的具有最小f值的节点为最佳节点BESTNODE,并

28、把它放入CLOSED表。 (4) 若BESTNODE为一目标节点,则成功求得一解。 (5) 若BESTNODE不是目标节点,则扩展之, 产生后继节点SUCCESSOR。,51,3.3.3 A*算法 （续）,(6) 对每个SUCCESSOR进行下列过程: a) 建立从SUCCESSOR返回BESTNODE的指针。 b) 计算g (SUC)=g (BES) + g (BES, SUC)。 c) 如果SUCCESSOROPEN, 则称此节点为OLD,并把它添至BESTNODE的后继节点表中。 d) 比较新旧路径代价.如果g(SUC)g(OLD),则重新确定OLD的父辈节点为BESTNODE,记下较小

29、代价g(OLD), 并修正f (OLD)值。,52,3.3.3 A*算法 （续）,(6) 对每个SUCCESSOR进行下列过程: e) 若至OLD节点的代价较低或一样,则停止扩展节点。 f) 若SUCCESSOR不在CLOSE表中,则看其是否在CLOSED表中。 g) 若SUCCESSOR在CLOSE表中,则转向(c); h) 若SUCCESSOR既不在OPEN表中,又不在CLOSED表中,则把它放入OPEN表中,并添入BESTNODE后裔表, 然后转向(7)。 (7) 计算f值。 (8) GO LOOP。,53,A*算法参考框图,54,3.3.3 A*算法 （续）,例1: 八数码难题. 定义

30、如下两种估价函数: 构成两个A*算法A1*和A2*。 A1*: h1(n): “不在位”的棋子数 g1(n): 实际走的步数(节点深度) A2*: h2(n): 所有棋子偏离目标位置的距离总和 g2(n): 实际走的步数(节点深度) 则有: h1(n) h2(n),55,3.3.3 A*算法 （续）,八数码难题的A1*算法的搜索图,56,3.3.3 A*算法 （续）,八数码难题的A2*算法的搜索图,57,3.3.3 A*算法 （续）,A*算法的特点: 若存在从初始节点S0到目标节点Sg的路径, 则A*算法必能结束在最佳路径上。 使用启发函数h (n)的A*算法，比不使用h (n) (h(n)0

31、)的算法, 求得最佳路径时扩展的节点数要少. 一般来说, 在满足h (n)h*(n)的条件下, h(n)的值越大, 说明它携带的启发性信息越多, 搜索时扩展的节点就越少, 搜索效率就越高, 当h (n)=h*(n)时,则不会去扩展多余的节点就可找到解.,58,3.3.3 A*算法 （续）,例2:迷宫图 从入口到出口有若干条通路，求从入口到出口处最短路径的走法。下图为一简单迷宫示意图及其平面坐标表示。,59,3.3.3 A*算法 （续）,问题状态: 物体在迷宫中的位置坐标(x, y)。则初始状态: (1, 1) 目标状态: (4, 4) 操作规则（迷宫走法规定为向上、下、左、右前进一步 ） U:

32、 上方无墙向上走一步(x, y+1) D: 下方无墙向下走一步(x, y-1) L: 左方无墙向左走一步(x-1, y) R: 右方无墙向右走一步( x+1, y),60,3.3.3 A*算法 （续）,取h(n)|XG - xn| + |YG - yn| ， g(n)d(n),f(n) = g(n) + h(n)， 显然可以满足A*的条件。 其中, (XG, YG) 为目标点坐标，(xn, yn)为节点n的坐标。再设当不同节点的f值相等时，以深度优先排序。,61,3.3.3 A*算法 （续）,迷宫问题搜索图,62,3.3.3 A*算法 （续）,例3:修道士和野人问题(M-C问题)。 状态: (

33、m, c, b) 操作: Pij, Qij 证明h(n)m+c-2b是满足A*条件的。 若不考虑限制条件, 如果船在左岸,也就是说，船一次可以将三人从左岸运到右岸，然后再有一个人将船送回来。这样，船一个来回可以运过河2人，而船仍然在左岸。而最后剩下的三个人，则可以一次将他们全部从左岸运到右岸。则至少摆渡次数为:,63,3.3.3 A*算法 （续）,考虑船在右岸的情况。船在右岸，需要一个人将船运到左岸。对于状态(m，c，0)来说，其所需要的最少摆渡数，相当于船在左岸时状态(m+1，c，1)或(m，c+1，1)所需要的最少摆渡数，再加上第一次将船从右岸送到左岸的一次摆渡数。因此所需要的最少摆渡数为

34、：(m+c+1)-2+1化简有：(m+c+1)-2+1=m+c。综合船在左岸和船在右岸两种情况下，所需要的最少摆渡次数用一个式子表示为：m+c-2b。其中b1表示船在左岸，b0表示船在右岸。由于该摆渡次数是在不考虑限制条件下，推出的最少所需要的摆渡次数。因此，当有限制条件时，最优的摆渡次数只能大于等于该摆渡次数。所以该启发函数h是满足A*条件的。 定义估价函数f (n) = g(n) + h(n), 其中g(n) = d(n), h(n)= m+c-2b,64,3.3.3 A*算法 （续）,M-C问题的A*算法搜索图,65,3.3.4图搜索策略的评价,准则 1、完备性：有解时能否保证找到解 2

35、、最优性：如果问题存在多个解，那么利用该搜索策略一定能够找到最优解。 3、时间复杂度：根据搜索过程中产生的节点数目来度量 4、空间复杂度：在执行搜索的过程中需要的内存，取决于储存的最大节点数。 时间与空间的复杂度往往要与问题难度的某种度量一起考虑,66,3.3.4图搜索策略的评价（续）,问题难度的度量 时间与空间的复杂度往往要与问题难度的某种度量一起考虑（状态空间图的大小） 平均分支因子b：节点的后继节点的平均个数 d：最浅的目标节点的深度（解深度） m：状态空间中任何路径的最大深度,67,3.3.4图搜索策略的评价（续）,宽度优先搜索 当b有限时，搜索是完备的 从寻找最短路径的解（或深度最浅

36、的解）的意义上最优 时间复杂度： O(bd) （b：平均分枝因子，d：解深度） 空间复杂度： O(bd) （b：平均分枝因子，d：解深度）,68,3.3.4图搜索策略的评价（续）,深度优先搜索 不完备 非最优 时间复杂度： O(bm) （b：平均分枝因子，m：状态空间的最大深度） 空间复杂度： O(b.m) （b：平均分枝因子，m：状态空间的最大深度）,69,3.3.4图搜索策略的评价（续）,含有深度界限的深度优先搜索 当ld时完备(l：深度限，d：解深度) 非最优 时间复杂度： O(bl) （b：平均分枝因子，l：深度限） 空间复杂度： O(b.l) （b：平均分枝因子，l：深度限）,70,

37、3.3.4图搜索策略的评价（续）,等代价搜索 完备 从寻找到根结点代价最小路径的解的意义上最优 时间复杂度： O(bd) （b：平均分枝因子，d：解深度） 空间复杂度： O(bd) （b：平均分枝因子，d：解深度）,71,3.3.4图搜索策略的评价（续）,有序搜索 不完备 不优化 时间复杂度： O(bm) （b：平均分枝因子，m：状态空间的最大深度）,72,3.3.4图搜索策略的评价（续）,A*算法 完备 优化 时间复杂度： O(bd) （b：平均分枝因子，d：解深度） 在内存空间中保存了所有的节点 A*也称为最佳图搜索算法,73,3. 4 博弈树搜索,3.4.1 博弈问题概述 3.4.2 极

38、小极大分析法 3.4.3 -搜索过程,74,3. 4. 1博弈问题概述,如下棋、打牌、竞技、战争等一类竞争性智能活动称为博弈。博弈有很多种，我们讨论最简单的“二人零和、全信息、非偶然”博弈，其特征如下： （1）双人对弈，对垒的双方轮流走步。 （2）信息完备，对垒双方所得到的信息是一样的，不存在一方能看到，而另一方看不到的情况。 （3）零和。即对一方有利的棋，对另一方肯定是不利的，不存在对双方均有利、或均无利的棋。对弈的结果是一方赢，而另一方输，或者双方和棋。 （4）任何一方在采取行动前都要根据当前的实际情况，进行得失分析，选取对自已为最有利而对对方最为不利的对策，不存在掷骰子之类的碰运气因素。

39、即双方都是很理智地决定自己的行动。,75,3. 4. 1博弈问题概述(续),博弈树搜索与状态空间搜索的区别 由机器完全控制结点的扩展，到由博弈双方分别控制 每一步操作后的结果不可预测 由于对手的操作带来不确定性：机器无从知道对方将会如何操作 对手总是试图给对方带来不便 在实际使用中的一些其它问题 特别大的状态空间 国际象棋： 平均分枝因子：35 每盘棋每方平均走棋：50步 状态空间大小：35100 （1040不同的合法的状态） 每一次搜索均有时间的限制 对搜索的结果要求更高,76,3. 4. 1博弈问题概述(续),博弈问题的知识表示 在博弈过程中，任何一方都希望自己取得胜利。因此，当某一方当前

40、有多个行动方案可供选择时，他总是挑选对自己最为有利而对对方最为不利的那个行动方案。 如果我们站在MAX方的立场上，则可供MAX方选择的若干行动方案之间是“或”关系，因为主动权操在MAX方手里，他或者选择这个行动方案，或者选择另一个行动方案，完全由MAX方自已决定。 当MAX方选取任一方案走了一步后，MIN方也有若干个可供选择的行动方案，此时这些行动方案对MAX方来说它们之间则是与关系，因为这时主动权操在MIN方手里，这些可供选择的行动方案中的任何一个都可能被MIN方选中，MAX方必须应付每一种情况的发生。这样，如果站在某一方(如MAX方，即MAX要取胜)，把上述博弈过程用图表示出来，则得到的是

41、一棵与或树。描述博弈过程的与或树称为博弈树,77,3. 4. 1博弈问题概述(续),博弈树的特点 (1) 博弈的初始格局是初始节点。(2) 在博弈树中，或节点和与节点是逐层交替出现的。自己一方扩展的节点之间是或关系，对方扩展的节点之间是与关系。双方轮流地扩展节点。(3) 所有自己一方获胜的终局都是本原问题，相应的节点是可解节点；所有使对方获胜的终局都认为是不可解节点。假定MAX先走，处于奇数深度级的节点都对应下一步由MAX走，这些节点称为MAX节点，相应地偶数级为MIN节点。,78,3. 4. 1博弈问题概述(续),问题空间模型化 四元组：（初始状态，操作集合，终止测试（非目标测试），判定函数

42、） 以下棋为例： 初始状态：棋的开局 操作集合：下棋的规则 终止测试：如果以输、赢、和局为下棋的终止，终止测试代表对输、赢、和局的判定 判定函数：通过它可以估计每一种状态下输、赢、和局的可能大小（比如：可以-1表示输，0表示和局，1表示赢）,79,3. 4. 1博弈问题概述(续),例：分钱币问题 有一堆数目为N的钱币，由两位选手(MAX,MIN)轮流进行分堆，要求每个选手每次只把其中某一堆分成数目不等的两小堆。例如选手甲把N分成两堆后，轮到选手乙就可以挑其中一堆来分，如此进行下去直到有一位选手先无法把钱币再分成不相等的两堆时就得认输。 用无序数字序列x1，x2，xn 表示n堆钱币不同的个数，再

43、用两个说明符号代表选手，无序数列和符号M组合（x1，x2，xn ，M）就代表由某个选手走步的状态。 初始状态：（7，MIN） 规则：if （x1，xn ，M）（xiy+z，yz）then （x1，xi-1 ，y，z，xi+1 ，xn，M ）,80,3. 4. 1博弈问题概述(续),分钱币问题状态空间图 图中所有终节点均表示该选手必输的情况，取胜方的目标是设法使棋局发展为结束在对方走步时的终节点上，因此节点A是MAX的搜索目标，而节点B，C则为MIN的搜索目标。,81,3. 4. 1博弈问题概述(续),分钱币问题 寻找MAX的取胜策略便和求与或图的解图一致起来，即MAX要取胜，必须对所有与节点取

44、胜，但只需对一个或节点取胜，这就是一个解图。因此实现一种取胜的策略就是搜索一个解图的问题，解图就代表一种完整的博弈策略。,82,3. 4. 1博弈问题概述(续),对于分钱币问题这种较简单的博弈，或者复杂博弈的残局，可以用类似于与或图的搜索技术求出解图，解图代表了从开局到终局任何阶段上的弈法。但是这对许多博弈问题是不可能实现的。 完全取胜策略（或和局）必须丢弃，而应当把目标确定为寻找一步好棋，等对手回敬后再考虑寻找另一步好棋这种实际可行的实用策略。这种情况下每一步结束条件可根据时间限制、存储空间限制或深度限制等因素加以确定。搜索策略可采用宽度、深度或启发式方法，一个阶段搜索结束后，要从搜索树中提

45、取一个优先考虑的最好的走步，这就是实用策略的基本点。,83,3. 4. 2极小极大分析法,基本思想 首先假定，有一个评价函数可以对所有的棋局进行评估。当评价函数值大于0时，表示棋局对我方有利，对对方不利。当评价函数小于0时，表示棋局对我方不利，对对方有利。而评价函数值越大，表示对我方越有利。当评价函数值等于正无穷大时，表示我方必胜。评价函数值越小，表示对我方越不利。 当评价函数值等于负无穷大时，表示对方必胜。假设双方都是对弈高手，在只看一步棋的情况下，我方一定走评价函数值最大的一步棋，而对方一定走评价函数值最小的一步棋。,84,3. 4. 2极小极大分析法（续）,极小极大搜索方法 当轮到我方走

46、棋时，首先按照一定的搜索深度生成出给定深度d以内的所有状态，计算所有叶节点的评价函数值。然后从d-1层节点开始逆向计算：对于我方要走的节点（用MAX标记，称为极大节点）取其子节点中的最大值为该节点的值（因为我方总是选择对我方有利的棋）；对于对方要走的节点（用MIN标记，称为极小节点）取其子节点中的最小值为该节点的值（对方总是选择对我方不利的棋）。一直到计算出根节点的值为止。获得根节点取值的那一分枝，即为所选择的最佳走步。,85,3. 4. 2极小极大分析法（续）,算法框架 整个算法分为四个步骤： 1、以当前状态为根结点产生一个博弈树。 2、对博弈树的每一个叶结点，利用判定函数给出它的判定值。

47、3、从叶结点开始，一层一层地回溯。在回溯过程中，利用最大/最小判定为每一个结点给出其判定值。 4、MAX方选择下一层中判定值最大的结点，作为它的下一状态。,86,3. 4. 2极小极大分析法（续）,例,87,3. 4. 2极小极大分析法（续）,例 一字棋游戏 设有九个空格，由MAX，MIN二人对弈，轮到谁走棋谁就往空格上放一只自己的棋子，谁先使自己的棋子构成“三子成一线”(同一行或列或对角线全是某人的棋子)，谁就取得了胜利。 设程序方MAX的棋子用（）表示，对手MIN的棋子用（）表示，MAX先走。,88,3. 4. 2极小极大分析法（续）,静态估计函数f（p）规定如下： 若p对任何一方来说都不是获胜的格局， 则f（p）（所有空格都放上MAX的棋子之后，MAX的三子成线（行、列、对角）的总数（所有空格都放上MIN的棋子之后，MIN的三子成线（行、列、对角）的总数） 若p是MAX获胜的格局，则f（p）； 若p是MIN获胜的格局，则f（p）。 当p的格局如图时，则可得f（p）642； 假定具有对称性的两个棋局算作一个棋局,89,3. 4. 2极小极大分析法（续）,第