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

3.1图搜索(sōusuǒ)策略3.2盲目搜索3.3启发式搜索3.4博弈树搜索3搜索(sōusuǒ)推理技术1共一百页从问题表示到问题的解决，有一个求解的过程。常见的AI问题求解技术有两种，即“搜索”（Search）和“推理”（Reasoning）方法。搜索是AI研究的一个重要课题，几乎所有的AI问题都可以被归结为搜索问题。各种搜索技术的研究是AI初期（1956－1970）的“热门”课题。虽然现在已有不少成熟的搜索技术出现于AI手册和各种AI书籍中，并在一些知识系统种得到广泛应用。但搜索效率的提高(tígāo)仍然是现在和今后AI研究者关心的一个重要问题。问题求解的第二种方法是逻辑推理。通过构造一个逻辑系统，由它可以从已有的断言（公理）推导出新的断言。并用逻辑形式语言描述的一组公理来表达问题域。用这种方法来解决问题就是通过推理来积聚越来越多的断言，直到获得问题的解答。虽然问题求解可通过搜索方法，也可用逻辑推理，但二者的侧重点是不一样的。前者着重于寻求问题解答的过程，而后者强调前提（初始）问题空间（公理集合）与问题解答间连接的逻辑正确性。或者简单地讲，搜索着重于发现（Discovery），而推理强调证明（Proof）。

2共一百页3.1图搜索(sōusuǒ)策略3.1.1问题求解(qiújiě)的过程3.1.2图搜索的一般过程3共一百页3.1.1问题求解(qiújiě)的过程1.问题的表示:主要采用状态空间法(状态空间图)和问题归约法(与或图)。2.问题的求解:通过(tōngguò)在图(“状态空间图”或”与或图”)中进行搜索,寻找一条路径的方法.一般搜索:从初始节点出发,扩展节点,并沿子节点推进,继续扩展选择的子节点,直到找到通向目标结点的路径,或找到解树为止。肓目搜索:是按预定的控制策略进行搜索,在搜索过程中获得的中间信息并不改变控制策略。启发式搜索:是在搜索过程中加入了与问题有关的启发性信息,缩小问题的搜索范围，指导搜索朝着最有希望的方向前进，以尽快地找到问题的（最优）解。4共一百页3.1.2图搜索(sōusuǒ)的一般过程例：从某王姓家族的四代中找王A的后代且其寿命为X的人。

王A：寿命47，有儿子王B1、王B3、王B2

王B1：寿命77，有儿子王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的人，我们最可能(kěnéng)用的手工方法是从家族表的开始往下，例中还要求所找的人是某人的后代，就比较复杂了。如果用图来表示，就很容易了。图中把姓氏省去，每个成员的后代按例子中给出名字的先后顺序。5共一百页3.1.2图搜索的一般(yībān)过程(续)图搜索策略可看作一种在图中寻找路径的方法。初始节点和目标节点分别代表初始数据库和满足终止条件的数据库。求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。研究(yánjiū)图搜索的一般策略，能够给出图搜索过程的一般步骤。6共一百页3.1.2图搜索(sōusuǒ)的一般过程（续）数据结构:OPEN：未扩展节点表CLOSED：已扩展节点表算法过程(1)建立一个只含有起始节点S的搜索图G,把S放到一个叫作OPEN的未扩展节点表中;(2)建立一个叫做CLOSED的已扩展节点表,其初始为空表;(3)LOOP:若OPEN表是空表,则失败退出(tuìchū);(4)选择OPEN表上的第一个节点,把它从OPEN表移出并放进CLOSED表中,称此节点为节点n;(5)若n为一目标节点,则有解并成功退出,此解是追踪图G中沿着指针从n到S这条路径而得到的(指针将在第(7)步中设置);7共一百页3.1.2图搜索(sōusuǒ)的一般过程（续）(6)扩展节点n，同时生成不是n的祖先的那些后继(hòujì)节点的集合M，把M的这些成员作为n的后继(hòujì)节点添入图G中；(7)对那些未曾在G中出现过的(即未曾在OPEN表上或CLOSED表中出现过的)M成员设置一个通向n的指针,把M的这些成员加进OPEN表。对已经在OPEN或CLOSED表上的每一个M成员，确定是否需要更改通到n的指针方向。对已在CLOSED表上的每个M成员，确定是否需要更改图G中通向它的每个后裔节点的指针方向；(8)按某一任意方式或按某个探试值,重排OPEN表;(9)GoLoop。8共一百页3.1.2图搜索(sōusuǒ)的一般过程（续）图搜索(sōusuǒ)过程框图9共一百页3.1.2图搜索(sōusuǒ)的一般过程（续）过程说明:①搜索(sōusuǒ)图:图搜索(sōusuǒ)的一般过程生成一个明确的图G,称为搜索(sōusuǒ)图。②搜索树:图搜索的一般过程生成G的一个子集T称为搜索树。由步骤(7)中设置的指针来确定。③G中每个节点(S除外)都有一个只指向G中一个父辈节点的指针,该父辈节点就定为树中那个节点的惟一父辈节点。④OPEN表上的节点都是搜索图上未被扩展的端节点,而CLOSED表上的节点,或者是已被扩展但没有生成后继节点的端节点,或者是搜索树的非端节点。10共一百页3.1.2图搜索(sōusuǒ)的一般过程（续）⑤步骤(8)对OPEN表上的节点进行排序,以便选出一个”最好”的节点作为步骤(4)扩展(kuòzhǎn)使用。 (1)排序可以是任意的即肓目的(盲目搜索) (2)可以用启发信息为依据(启发式搜索)⑥当扩展某个节点时,搜索图已经保存了从初始节点到该节点的搜索树。⑦每当被选作扩展的节点为目标节点时,这一过程就宣告成功结束。这时，从目标节点按指向父节点的指针不断回溯,能够重现从起始节点到目标节点的成功路径。⑧当搜索树不再剩有末被扩展的端节点时(即OPEN表为空时)，过程就以失败告终。从起始节点,达不到目标节点。11共一百页3.1.2图搜索的一般(yībān)过程（续）⑨步骤(6)扩展节点时,生成一个节点的所有后继(hòujì)节点。⑩步骤(7)的说明:特别地用于启发式搜索扩展节点1以前的搜索图扩展节点1以后搜索图12共一百页3.2盲目(mángmù)搜索3.2.1宽度优先搜索(sōusuǒ)3.2.1深度优先搜索3.2.3等代价搜索13共一百页3.2.1宽度(kuāndù)优先搜索宽度优先(yōuxiān)搜索：如果搜索是以接近起始节点的程度来依次扩展节点，那么这种搜索叫做宽度优先搜索(breadth-firstsearch)。特点：这种搜索是逐层进行的；在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。14共一百页3.2.1宽度优先(yōuxiān)搜索（续）宽度优先(yōuxiān)搜索算法:(1)把起始节点放到OPEN表中(如果该起始节点为一目标节点,则求得一个解答)。(2)如果OPEN是个空表则没有解，失败退出，否则继续。(3)把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED的扩展节点表中。(4)扩展节点n，如果没有后继节点，则转向步骤(2)。(5)把n的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针。(6)如果n的任一个后继节点是个目标节点,则找到一个解答，成功退出，否则转向步骤(2)。15共一百页3.2.1宽度优先(yōuxiān)搜索（续）宽度优先搜索算法说明:(1)搜索树:搜索过程产生的节点和指针构成一棵隐式定义的状态空间图的子树,称为搜索树。(2)如果问题有解,宽度优先算法能够保证找到一条通向目标节点的最短路径(即找到最优解)。(3)如果问题无解，对于有限图，该算法会失败退出；对于无限图，则永远不会终止。(4)宽度优先搜索是图搜索一般过程的特殊情况，将图搜索一般过程中的第8步具体化为本算法中的第6步，这实际(shíjì)是将OPEN表作为“先进先出”的队列进行操作。

16共一百页3.2.1宽度(kuāndù)优先搜索（续）17共一百页3.2.1宽度(kuāndù)优先搜索（续）例:八数码(shùmǎ)难题，在3×3的方格棋盘上，分别放置了标有数字1,2,3,4,5,6,7,8的八张牌，初始状态如图S0所示，目标状态如图Sg所示，要求应用宽度优先搜索策略寻找从初始状态到目标状态的解路径。18共一百页3.2.1宽度(kuāndù)优先搜索（续）八数码难题的宽度(kuāndù)优先搜索树19共一百页3.2.2深度优先(yōuxiān)搜索深度优先(yōuxiān)搜索：在搜索过程中，首先扩展最新产生的(即最深的)节点，深度相等的节点可以任意排列，这种搜索叫做深度优先搜索(depth-firstsearch)。特点：首先，扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进行下去；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代的路径。20共一百页3.2.2深度(shēndù)优先搜索（续）节点深度:(1)起始节点(即根节点)的深度为0。(2)任何其他节点的深度等于其父辈节点的深度加1。深度界限:为了避免考虑太长的路径(防止搜索过程沿着无益的路径扩展下去),往往给出一个节点扩展的最大深度,称为深度界限。任何节点如果达到了深度界限,那么都将把它们作为(zuòwéi)没有后继节点来处理。即使应用了深度界限,深度优先搜索所求得的解答路径也不一定就是最短路径。21共一百页3.2.2深度(shēndù)优先搜索（续）含有深度界限的深度优先搜索算法:(1)把起始节点S放到未扩展节点OPEN表中。如果此节点为一目标节点,则得到一个解。(2)如果OPEN为一空表,则失败退出。(3)把第一个节点(节点n)从OPEN表移到CLOSED表。(4)如果节点n的深度等于最大深度,则转向步骤(2)。(5)扩展节点n,产生其全部后裔,并把它们放入OPEN表的前头(qiántou)。如果没有后裔，则转向步骤(2)。(6)如果后继节点中有任一个为目标节点,则求得一个解,成功退出;否则,转向步骤(2)。22共一百页23共一百页3.2.2深度(shēndù)优先搜索（续）八数码难题深度界限为5的深度优先(yōuxiān)搜索树24共一百页3.2.3等代价(dàijià)搜索宽度优先的局限:在宽度优先搜索中作了一种假设,认为状态空间中各边的代价都相同,且都为一个单位量。从而可用路径的长度(chángdù)代替路径的代价。然而,对许多问题这种假设是不现实的,它们的状态空间中的各个边的代价不可能完全相同。 例:城市交通问题。为此,需要在搜索树中给每条边都标上其代价。代价树:在搜索树中给每条边都标上其代价。这种边上标有代价的树称为代价树。等代价搜索:寻找从起始状态至目标状态的具有最小代价的路径问题,叫做等代价搜索。在等代价搜索算法中,是沿着等代价路径断层进行扩展的。25共一百页3.2.3等代价(dàijià)搜索（续）例:城市交通问题.设有5个城市,它们之间的交通路线如图所示,图中的数字表示两个城市之间的交通费用(fèiyong),即代价。用等代价搜索,求从A市出发到E市,费用(fèiyong)最小的交通路线。26共一百页3.2.3等代价(dàijià)搜索（续）解:其代价(dàijià)搜索树如右下图:最优解:A,C,D,E27共一百页3.2.3等代价(dàijià)搜索（续）记号(jìhɑo)c(i,j):从节点I到其后继节点j的连接弧线代价。g(i):从起始节点S到任一节点i的路径代价(即是从起始节点S到节点i的最少代价路径上的代价)28共一百页3.2.3等代价(dàijià)搜索（续）等代价搜索算法:(1)把起始节点S放到未扩展节点有OPEN中。如果此起始节点为一目标(mùbiāo)节点,则求得一个解，否是令g(S)=0。(2)如果OPEN是个空表,则没有解而失败退出。(3)从OPEN表中选择一个节点I,使其g(i)为最小。如果有几个节点都合格,那么就要选择一个目标节点作为节点i(如果有目标节点的话)，否则，就从中选一个作为节点i，把节点i从OPEN表移至扩展节点表CLOSED中。29共一百页3.2.3等代价(dàijià)搜索（续）(4)如果节点i为目标节点,则求得一个解。(5)扩展节点i。如果没有后继节点，则转向步骤(bùzhòu)(2);(6)对于节点i的每个后继节点j,计算g(j)=g(i)+c(i,j),并把所有后继节点j放进OPEN表.提供回到节点i的指针。(7)转向步骤(2)。30共一百页31共一百页3.3启发式搜索(sōusuǒ)3.3.1启发式搜索(sōusuǒ)策略和估价函数3.3.2有序搜索3.3.3A*算法3.3.4图搜索策略的评价32共一百页3.3启发式搜索(sōusuǒ)（续）盲目搜索存在的问题扩展节点数目较多。效率低，耗费过多的计算时间和空间。分析前面介绍的宽度优先、深度优先搜索，或等代价搜索算法,其主要的差别是OPEN表中待扩展节点的顺序问题。如果找到一种方法用于排列待扩展节点的顺序，即选择(xuǎnzé)最有希望的节点加以扩展，那么，搜索效率将会大为提高。

33共一百页3.3.1启发式搜索策略(cèlüè)和估价函数启发性信息：指那种与具体问题求解过程有关的，并可指导搜索过程朝着最有希望方向前进的控制信息。三种启发性信息：(1)用于决定要扩展(kuòzhǎn)的下一个节点，以免像在宽度优先或深度优先搜索中那样盲目地扩展(kuòzhǎn)。(2)在扩展一个节点的过程中，用于决定要生成哪一个或哪几个后继节点，以免盲目地同时生成所有可能的节点。(3)用于决定某些应该从搜索树中抛弃或修剪的节点。启发式搜索：利用启发信息的搜索方法叫做启发式搜索。34共一百页3.3.1启发式搜索(sōusuǒ)策略和估价函数（续）估价函数(evaluationfunction):用于度量节点的”希望”(此节点在通向目标结点的最佳路径上的”希望”)的量度。记号f(n):表示节点n的估价函数值。用函数f(n)的值来排列图搜索的一般算法(suànfǎ)中的OPEN表中节点。节点按递增顺序排列,即优先扩展具有低估价值的节点,根据低估价值节点更有可能处在最佳路径上。35共一百页3.3.2有序搜索(sōusuǒ)有序搜索：应用某个算法(例如等代价法)选择OPEN表上具有(jùyǒu)最小f值的节点作为下一个要扩展的节点，这种搜索方法叫做有序搜索或最佳优先搜索，其算法就叫做有序搜索算法（orderedsearch）或最佳优先算法（best-firstsearch）。有序搜索总是选择最有希望的节点作为下一个要扩展的节点.36共一百页3.3.2有序搜索(sōusuǒ)(续)有序搜索算法:(1)把起始节点S放到OPEN表中，计算f(S),并把其值与节点S联系起来。(2)如果OPEN表是个空表,则失败退出，无解。(3)从OPEN表中选择一个f值最小的节点i，结果(jiēguǒ)有几个节点合格,当其中有一个为目标节点时，则选择此目标节点,否则就选择其中任一个节点作为节点i。(4)把节点i从OPEN表中移出，并把它放入CLOSED的扩展节点表中。(5)如果i是个目标节点，则成功退出，求得一个解，37共一百页3.3.2有序搜索(sōusuǒ)(续)(6)扩展节点i，生成其全部后继节点。对于i的每一个后继节点j:a)计算f(j)。b)如果j既不在OPEN表中，也不在CLOSED表中，则用估价函数f把它添入OPEN表，从j加一指向父辈节点i的指针(以便(yǐbiàn)找到目标节点时记住一个解答路径)。c)如果j已在OPEN表或CLOSED表上，则比较刚刚对j计算过的f值和前面计算过的该节点在表中的f值.如果新的f值较小，则

I.以此新值取代旧值。 II.从j指向i,而不是指向它的父辈节点。 III.如果节点j在CLOSED表中,则把它移回OPEN表。(7)转向(2),即GOTO(2);38共一百页3.3.2有序搜索(sōusuǒ)(续)39共一百页3.3.2有序搜索(sōusuǒ)(续)在有序搜索中定义f(i)为节点i的深度,则退化为宽度优先算法搜索。定义f(i)为从起始节点至节点i这段路径的代价,则退化为等代价搜索。估价函数的作用f的选择直接决定了有序搜索中被扩展节点的数目,即直接影响了搜索算法的效率。对搜索结果具有决定性的作用，如果选择不合适，有序搜索就可能失去一个最好的解甚至全部的解。估价函数的选择，如果没有适用的准确的希望量度，那么f的选择将涉及两个方面的内容：一方面是时间和空间之间的折衷方案；另一方面是保证有一个最优的解或任意解。一个节点处在最佳路径上的概率；求出任意一个节点与目标节点集之间的距离度量或差异度量；根据格局(géjú)（博弈问题）或状态的特点来打分。40共一百页3.3.2有序搜索(sōusuǒ)(续)例:八数码难题.设问题的初始状态S0和目标状态Sg如图所示,定义估价函数为:f(n)=d(n)+W(n) 其中,d(n)表示节点n在搜索树中的深度;

W(n)表示节点n中”不在位”的数码个数. 请计算初始状态S0的估价函数值f(S0). 解:对初始节点S0,由于(yóuyú)d(n)=0,W(n)=4,因此有:f(S0)=441共一百页八数码(shùmǎ)难题有序搜索树42共一百页3.3.3A*算法(suànfǎ)估价函数f(n)的定义:是从起始节点约束地通过节点n而到达目标节点的最小代价路径的代价的一个(yīɡè)估计。估价函数的形式:f(n)=g(n)+h(n) 其中,g(n)是从初始节点S0到节点n的实际代价;h(n)是从节点n到目标节点Sg的最优路径的估计代价。43共一百页3.3.3A*算法(suànfǎ)（续）定义3.1在GRAPHSEARCH过程(guòchéng)中,如果步骤(8)的重排OPEN表是依据f(n)=g(n)+h(n)进行的,则称该过程为A算法。说明:在图搜索的一般算法中,在搜索的每一步都利用估价函数f(n)=g(n)+h(n)对Open表中的节点进行排序,找出一个最有希望的节点作为下一次扩展的节点,则该搜索算法称为A算法。44共一百页3.3.3A*算法(suànfǎ)（续）例:八数码难题。设问题的初始状态(zhuàngtài)和目标状态(zhuàngtài)如图所示,估价函数为:f(n)=d(n)+W(n) 其中,d(n)表示节点n在搜索树中的深度;

W(n)表示节点n中”不在位”的数码个数。45共一百页3.3.3A*算法(suànfǎ)（续）记号:k(ni,nj):表示任意两个节点ni和nj之间最小代价路径(lùjìng)的实际代价(对于两节点间没有通路的节点,函数k没有定义).h*(n):表示整个目标节点集合{ti}上所有k(n,ti)中最小的一个,即从节点n到目标节点最优路径的实际代价。g*的定义:g*(n)=k(S,n)f*的定义:f*(n)=g*(n)+h*(n)46共一百页3.3.3A*算法(suànfǎ)（续）估价函数f是f*的一个估计:f(n)=g(n)+h(n) 其中g(n)是g*(n)的估计,h(n)是h*(n)的估计。g(n),通常为从S到n这段路径的实际代价则有g(n)≥g*(n)h(n):是从节点n到目标节点Sg的最优路径的估计代价。它的选择依赖于有关问题领域的启发信息(xìnxī)，叫做启发函数。例如八数码中的W(n)。47共一百页3.3.3A*算法(suànfǎ)（续）定义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)的下界,即对任意的节点(jiédiǎn)n均有h(n)≤h*(n)。那么这时的A算法就称为A*算法。48共一百页3.3.3A*算法(suànfǎ)（续）例:八数码难题.设问题的初始状态和目标状态如前图所示,估价函数(hánshù)为:f(n)=d(n)+W(n) 其中,d(n)表示节点n在搜索树中的深度;

W(n)表示节点n中”不在位”的数码个数.d(n)是对g*(n)的一个估计，d(n)≥g*(n)W(n)是对h*(n)的一个估计49共一百页3.3.3A*算法(suànfǎ)（续）算法步骤:(1)把S放入OPEN表,记f=h,令CLOSED为空表。(2)重复下列过程,直至找到目标节点为止。若OPEN为空表,则宣告失败。(3)选取(xuǎnqǔ)OPEN表中未设置过的具有最小f值的节点为最佳节点BESTNODE,并把它放入CLOSED表。(4)若BESTNODE为一目标节点,则成功求得一解。(5)若BESTNODE不是目标节点,则扩展之,产生后继节点SUCCESSOR。50共一百页3.3.3A*算法(suànfǎ)（续）(6)对每个SUCCESSOR进行下列过程:a)建立从SUCCESSOR返回BESTNODE的指针。b)计算g(SUC)=g(BES)+g(BES,SUC)。c)如果SUCCESSOR∈OPEN,则称此节点(jiédiǎn)为OLD,并把它添至BESTNODE的后继节点(jiédiǎn)表中。d)比较新旧路径代价.如果g(SUC)<g(OLD),则重新确定OLD的父辈节点为BESTNODE,记下较小代价g(OLD),并修正f(OLD)值。51共一百页3.3.3A*算法(suànfǎ)（续）(6)对每个SUCCESSOR进行下列过程:e)若至OLD节点的代价较低或一样,则停止扩展节点。f)若SUCCESSOR不在CLOSE表中,则看其是否在CLOSED表中。g)若SUCCESSOR在CLOSE表中,则转向(zhuǎnxiàng)(c);h)若SUCCESSOR既不在OPEN表中,又不在CLOSED表中,则把它放入OPEN表中,并添入BESTNODE后裔表,然后转向(7)。(7)计算f值。(8)GOLOOP。52共一百页A*算法参考(cānkǎo)框图53共一百页3.3.3A*算法(suànfǎ)（续）例1:八数码难题.定义如下两种估价函数:构成两个A*算法A1*和A2*。A1*: h1(n):“不在位”的棋子数 g1(n):实际走的步数(节点深度)A2*: h2(n):所有棋子偏离目标位置(wèizhi)的距离总和 g2(n):实际走的步数(节点深度) 则有:h1(n)≤h2(n)54共一百页3.3.3A*算法(suànfǎ)（续）八数码难题(nántí)的A1*算法的搜索图55共一百页3.3.3A*算法(suànfǎ)（续）八数码难题的A2*算法(suànfǎ)的搜索图56共一百页3.3.3A*算法(suànfǎ)（续）A*算法的特点:若存在从初始节点S0到目标(mùbiāo)节点Sg的路径,则A*算法必能结束在最佳路径上。使用启发函数h(n)的A*算法，比不使用h(n)(h(n)≡0)的算法,求得最佳路径时扩展的节点数要少.一般来说,在满足h(n)≤h*(n)的条件下,h(n)的值越大,说明它携带的启发性信息越多,搜索时扩展的节点就越少,搜索效率就越高,当h(n)=h*(n)时,则不会去扩展多余的节点就可找到解.57共一百页3.3.3A*算法(suànfǎ)（续）例2:迷宫(mígōng)图从入口到出口有若干条通路，求从入口到出口处最短路径的走法。下图为一简单迷宫(mígōng)示意图及其平面坐标表示。58共一百页3.3.3A*算法(suànfǎ)（续）问题状态:物体在迷宫中的位置坐标(zuòbiāo)(x,y)。则初始状态:(1,1)目标状态:(4,4)操作规则（迷宫走法规定为向上、下、左、右前进一步）U:上方无墙→向上走一步(x,y+1)D:下方无墙→向下走一步(x,y-1)L:左方无墙→向左走一步(x-1,y)R:右方无墙→向右走一步(x+1,y)59共一百页3.3.3A*算法(suànfǎ)（续）取h(n)＝|XG-xn|+|YG-yn|，g(n)＝d(n),f(n)=g(n)+h(n)，显然可以满足A*的条件。 其中,(XG,YG)为目标点坐标，(xn,yn)为节点(jiédiǎn)n的坐标。再设当不同节点的f值相等时，以深度优先排序。60共一百页3.3.3A*算法(suànfǎ)（续）迷宫(mígōng)问题搜索图61共一百页3.3.3A*算法(suànfǎ)（续）例3:修道士和野人问题(M-C问题)。状态:(m,c,b)操作:Pij,Qij证明h(n)＝m+c-2b是满足A*条件的。 若不考虑限制条件,如果船在左岸,也就是说，船一次可以将三人从左岸运到右岸，然后再有一个人将船送回来。这样，船一个来回可以运过河2人，而船仍然在左岸。而最后剩下的三个人，则可以一次将他们全部从左岸运到右岸。则至少(zhìshǎo)摆渡次数为:62共一百页3.3.3A*算法(suànfǎ)（续）考虑船在右岸的情况。船在右岸，需要一个人将船运到左岸。对于状态(m，c，0)来说，其所需要的最少摆渡(bǎidù)数，相当于船在左岸时状态(m+1，c，1)或(m，c+1，1)所需要的最少摆渡(bǎidù)数，再加上第一次将船从右岸送到左岸的一次摆渡(bǎidù)数。因此所需要的最少摆渡(bǎidù)数为：(m+c+1)-2+1化简有：(m+c+1)-2+1=m+c。

综合船在左岸和船在右岸两种情况下，所需要的最少摆渡(bǎidù)次数用一个式子表示为：m+c-2b。其中b＝1表示船在左岸，b＝0表示船在右岸。

由于该摆渡(bǎidù)次数是在不考虑限制条件下，推出的最少所需要的摆渡(bǎidù)次数。因此，当有限制条件时，最优的摆渡(bǎidù)次数只能大于等于该摆渡(bǎidù)次数。所以该启发函数h是满足A*条件的。定义估价函数f(n)=g(n)+h(n),其中g(n)=d(n),h(n)=m+c-2b63共一百页3.3.3A*算法(suànfǎ)（续）M-C问题(wèntí)的A*算法搜索图64共一百页3.3.4图搜索(sōusuǒ)策略的评价准则1、完备性：有解时能否保证找到解2、最优性：如果问题存在多个解，那么利用该搜索策略一定能够找到最优解。3、时间复杂度：根据搜索过程中产生的节点数目来度量4、空间复杂度：在执行搜索的过程中需要(xūyào)的内存，取决于储存的最大节点数。时间与空间的复杂度往往要与问题难度的某种度量一起考虑65共一百页3.3.4图搜索(sōusuǒ)策略的评价（续）问题难度的度量 时间与空间的复杂度往往要与问题难度的某种度量一起考虑（状态空间图的大小）平均分支因子b：节点的后继节点的平均个数d：最浅的目标节点的深度（解深度）m：状态空间中任何(rènhé)路径的最大深度66共一百页3.3.4图搜索策略(cèlüè)的评价（续）宽度优先搜索当b有限时，搜索是完备(wánbèi)的从寻找最短路径的解（或深度最浅的解）的意义上最优时间复杂度：O(bd)（b：平均分枝因子，d：解深度）空间复杂度：O(bd)（b：平均分枝因子，d：解深度）67共一百页3.3.4图搜索策略(cèlüè)的评价（续）深度优先搜索不完备(wánbèi)非最优时间复杂度：O(bm)（b：平均分枝因子，m：状态空间的最大深度）空间复杂度：O(b.m)（b：平均分枝因子，m：状态空间的最大深度）68共一百页3.3.4图搜索(sōusuǒ)策略的评价（续）含有(hányǒu)深度界限的深度优先搜索当l≥d时完备(l：深度限，d：解深度)非最优时间复杂度：O(bl)（b：平均分枝因子，l：深度限）空间复杂度：O(b.l)（b：平均分枝因子，l：深度限）69共一百页3.3.4图搜索(sōusuǒ)策略的评价（续）等代价搜索完备从寻找到根结点代价最小路径的解的意义上最优时间复杂度：O(bd)（b：平均分枝(fēnzhī)因子，d：解深度）空间复杂度：O(bd)（b：平均分枝因子，d：解深度）70共一百页3.3.4图搜索(sōusuǒ)策略的评价（续）有序搜索不完备不优化时间复杂度：O(bm)（b：平均分枝因子，m：状态(zhuàngtài)空间的最大深度）71共一百页3.3.4图搜索(sōusuǒ)策略的评价（续）A*算法完备优化时间复杂度：O(bd)（b：平均分枝因子，d：解深度）在内存空间中保存了所有(suǒyǒu)的节点A*也称为最佳图搜索算法72共一百页3.4博弈(bóyì)树搜索3.4.1博弈问题概述3.4.2极小极大(jídà)分析法3.4.3α-β搜索过程73共一百页3.4.1博弈(bóyì)问题概述如下棋、打牌、竞技、战争等一类竞争性智能(zhìnénɡ)活动称为博弈。博弈有很多种，我们讨论最简单的“二人零和、全信息、非偶然”博弈，其特征如下：（1）双人对弈，对垒的双方轮流走步。（2）信息完备，对垒双方所得到的信息是一样的，不存在一方能看到，而另一方看不到的情况。（3）零和。即对一方有利的棋，对另一方肯定是不利的，不存在对双方均有利、或均无利的棋。对弈的结果是一方赢，而另一方输，或者双方和棋。（4）任何一方在采取行动前都要根据当前的实际情况，进行得失分析，选取对自已为最有利而对对方最为不利的对策，不存在掷骰子之类的"碰运气"因素。即双方都是很理智地决定自己的行动。74共一百页3.4.1博弈问题(wèntí)概述(续)博弈树搜索与状态空间搜索的区别由机器完全控制结点的扩展，到由博弈双方分别控制每一步操作后的结果不可预测 由于对手的操作带来不确定性：机器无从知道对方将会如何操作 对手总是试图给对方带来不便在实际使用中的一些其它问题 特别(tèbié)大的状态空间 国际象棋：

平均分枝因子：35

每盘棋每方平均走棋：50步

状态空间大小：35100（1040不同的合法的状态） 每一次搜索均有时间的限制 对搜索的结果要求更高75共一百页3.4.1博弈(bóyì)问题概述(续)博弈问题的知识表示 在博弈过程中，任何一方都希望自己取得胜利。因此，当某一方当前有多个行动方案可供选择时，他总是挑选对自己最为有利而对对方最为不利的那个行动方案。 如果我们站在MAX方的立场上，则可供MAX方选择的若干行动方案之间是“或”关系，因为主动权操在MAX方手里，他或者选择这个行动方案，或者选择另一个行动方案，完全(wánquán)由MAX方自已决定。 当MAX方选取任一方案走了一步后，MIN方也有若干个可供选择的行动方案，此时这些行动方案对MAX方来说它们之间则是"与"关系，因为这时主动权操在MIN方手里，这些可供选择的行动方案中的任何一个都可能被MIN方选中，MAX方必须应付每一种情况的发生。

这样，如果站在某一方(如MAX方，即MAX要取胜)，把上述博弈过程用图表示出来，则得到的是一棵"与或树"。描述博弈过程的与或树称为博弈树76共一百页3.4.1博弈问题(wèntí)概述(续)博弈树的特点 (1)博弈的初始格局是初始节点。

(2)在博弈树中，"或"节点和"与"节点是逐层交替出现的。自己一方扩展的节点之间是"或"关系，对方扩展的节点之间是"与"关系。双方轮流地扩展节点。

(3)所有自己一方获胜的终局都是本原问题，相应的节点是可解节点；所有使对方获胜的终局都认为是不可解节点。

假定MAX先走，处于奇数深度级的节点都对应(duìyìng)下一步由MAX走，这些节点称为MAX节点，相应地偶数级为MIN节点。

77共一百页3.4.1博弈问题(wèntí)概述(续)问题空间模型化 四元组：（初始状态，操作集合，终止(zhōngzhǐ)测试（非目标测试），判定函数） 以下棋为例：初始状态：棋的开局操作集合：下棋的规则终止测试：如果以输、赢、和局为下棋的终止，终止测试代表对输、赢、和局的判定判定函数：通过它可以估计每一种状态下输、赢、和局的可能大小（比如：可以-1表示输，0表示和局，1表示赢）78共一百页3.4.1博弈问题(wèntí)概述(续)例：分钱币问题 有一堆数目为N的钱币，由两位选手(MAX,MIN)轮流进行分堆，要求每个选手每次只把其中某一堆分成数目不等的两小堆。例如选手甲把N分成两堆后，轮到选手乙就可以挑其中一堆来分，如此进行下去直到有一位选手先无法把钱币再分成不相等的两堆时就得认输(rènshū)。用无序数字序列x1，x2，…，xn表示n堆钱币不同的个数，再用两个说明符号代表选手，无序数列和符号M组合（x1，x2，…，xn，M）就代表由某个选手走步的状态。初始状态：（7，MIN）规则：if（x1，…，xn，M）∧（xi＝y+z，y≠z）

then（x1，…，xi-1，y，z，xi+1，…，xn，M）79共一百页3.4.1博弈(bóyì)问题概述(续)分钱币问题状态空间图 图中所有终节点均表示该选手必输的情况，取胜(qǔshèng)方的目标是设法使棋局发展为结束在对方走步时的终节点上，因此节点A是MAX的搜索目标，而节点B，C则为MIN的搜索目标。80共一百页3.4.1博弈问题(wèntí)概述(续)分钱币问题 寻找MAX的取胜策略便和求与或图的解图一致起来，即MAX要取胜，必须对所有与节点取胜，但只需对一个或节点取胜，这就是(jiùshì)一个解图。因此实现一种取胜的策略就是(jiùshì)搜索一个解图的问题，解图就代表一种完整的博弈策略。

81共一百页3.4.1博弈问题(wèntí)概述(续)对于分钱币问题这种较简单的博弈，或者复杂博弈的残局，可以用类似于与或图的搜索技术求出解图，解图代表了从开局到终局任何阶段上的弈法。但是这对许多博弈问题是不可能实现的。完全取胜策略（或和局）必须丢弃(diūqì)，而应当把目标确定为寻找一步好棋，等对手回敬后再考虑寻找另一步好棋这种实际可行的实用策略。这种情况下每一步结束条件可根据时间限制、存储空间限制或深度限制等因素加以确定。搜索策略可采用宽度、深度或启发式方法，一个阶段搜索结束后，要从搜索树中提取一个优先考虑的"最好的"走步，这就是实用策略的基本点。82共一百页3.4.2极小(jíxiǎo)极大分析法基本思想首先假定，有一个评价函数可以对所有的棋局进行评估。当评价函数值大于0时，表示棋局对我方有利，对对方不利。当评价函数小于0时，表示棋局对我方不利，对对方有利。而评价函数值越大，表示对我方越有利。当评价函数值等于正无穷大时，表示我方必胜。评价函数值越小，表示对我方越不利。当评价函数值等于负无穷大时，表示对方必胜。假设双方都是对弈高手(gāoshǒu)，在只看一步棋的情况下，我方一定走评价函数值最大的一步棋，而对方一定走评价函数值最小的一步棋。83共一百页3.4.2极小(jíxiǎo)极大分析法（续）极小极大搜索方法 当轮到我方走棋时，首先按照一定的搜索深度生成出给定深度d以内的所有状态，计算所有叶节点的评价函数值。然后从d-1层节点开始逆向计算：对于我方要走的节点（用MAX标记，称为(chēnɡwéi)极大节点）取其子节点中的最大值为该节点的值（因为我方总是选择对我方有利的棋）；对于对方要走的节点（用MIN标记，称为(chēnɡwéi)极小节点）取其子节点中的最小值为该节点的值（对方总是选择对我方不利的棋）。一直到计算出根节点的值为止。获得根节点取值的那一分枝，即为所选择的最佳走步。84共一百页3.4.2极小(jíxiǎo)极大分析法（续）算法框架整个算法分为四个步骤：1、以当前状态为根结点产生一个博弈(bóyì)树。2、对博弈树的每一个叶结点，利用判定函数给出它的判定值。3、从叶结点开始，一层一层地回溯。在回溯过程中，利用最大/最小判定为每一个结点给出其判定值。4、MAX方选择下一层中判定值最大的结点，作为它的下一状态。85共一百页3.4.2极小(jíxiǎo)极大分析法（续）例86共一百页3.4.2极小(jíxiǎo)极大分析法（续）例一字棋游戏设有九个空格(kōnɡɡé)，由MAX，MIN二人对弈，轮到谁走棋谁就往空格(kōnɡɡé)上放一只自己的棋子，谁先使自己的棋子构成“三子成一线”(同一行或列或对角线全是某人的棋子)，谁就取得了胜利。设程序方MAX的棋子用（×）表示，对手MIN的棋子用（○）表示，MAX先走。87共一百页3.4.2极小(jíxiǎo)极大分析法（续）静态估计函数f（p）规定如下：若p对任何一方来说都不是获胜(huòshènɡ)的格局， 则f（p）＝（所有空格都放上MAX的棋子之后，MAX的三子成线（行、列、对角）的总数－（所有空格都放上MIN的棋子之后，MIN的三子成线（行、列、对角）的总数）若p是MAX获胜的格局，则f（p）＝∞；若p是MIN获胜的格局，则f（p）＝－∞。当p的格局如图时，则可得f（p）＝6－4＝2；假定具有对称性的两个棋局算作一个棋局88共一百页3.4.2极小(jíxiǎo)极大分析法（续）第一阶段搜索树89共一百页3.4.2极小(jíxiǎo)极大分析法（续）第二阶段搜索树90共一百页3.4.2极小(jíxiǎo)极大分析法（续）第三阶段搜索树91共一百页3.4.3α-β搜索(sōusuǒ)过程在极小极大搜索方法中，由于