人工智能基础与应用第四章

第4章搜索搜索是人工智能的一个基本问题，是推理不可分割的一部分。一个问题的求解过程就是搜索过程，所以搜索实际上是求解问题的一种方法。4.1搜索概述4.1.1搜索的基本概念人类的思维过程，可以看作是一个搜索的过程。我们曾经遇到过很多有趣的智力游戏问题，比如传教士和野人问题：有三传教士和三个野人过河，河岸上只有一条能装下两个人的船，在河的任何一方或者船上，如果野人的人数大于传教士的人数，那么传教士就会有危险。你能不能找出一种安全的渡河方法呢？如果要作这个游戏，在每一次渡河之后，都会有几种渡河方案供你选择，究竟哪种方案才有利于在满足题目所规定的约束条件下顺利过河呢？人工智能要解决的问题大多数是结构不良或者非结构的问题，对这样的问题一般不存在成熟的求解算法，而只能利用已有的知识一步步地摸索着前进。在这个过程中，存在着如何寻找一条推理路线，使得付出的代价尽可能地少，而问题又能够得到解决。我们称寻找这样路线的过程为搜索。4.1.2搜索的分类根据在问题求解过程中是否运用启发性知识，搜索可分为盲目搜索和启发式搜索。盲目搜索是按预定的控制策略进行，在搜索的过程中所获得的信息不用来改进控制策略的一种搜索。由于搜索总是按预先规定的路线进行，没有考虑问题本身的特性，这种方法缺乏对问题求解的针对性，需要进行全方位的搜索，而没有选择最优的搜索途径，因此，这种搜索具有盲目性，效率较低。启发式搜索是在搜索中加入了与问题有关的启发式信息，用来指导搜索朝着最有希望的方向前进，加速问题的求解过程，并找到最优解。4.2状态空间搜索状态空间法状态空间法的基本思想：用“状态”和“操作”来表示或求解问题。问题是用“状态”和“操作”来表示，问题求解过程是用“状态空间”来表示的。状态是表示问题求解过程中每一步问题状况的数据结构，它可形式地表示为：Sk={Sk0,Sk1,……}。在这种状态中，当对每一个分量都给予确定的值时，就得到了一个具体的状态。操作，也称算符，它是把问题一个状态变换为另一种状态的手段。操作可理解为状态集合上的一个函数，它描述了状态之间的关系。状态空间用来描述一个问题的全部状态以及这些状态之间的相互关系。状态空间法基本过程：首先为问题选择适当的“状态”及“操作”的形式化描述方法；然后从某个初始状态出发，每次使用一个“操作”，递增的建立起操作序列，直到达到目标状态为止；此时，由初始状态到目标状态所使用的算符序列就是该问题的一个解。八数码难题在3*3的方格棋盘上，分别放置了标有数字1、2、3、4、5、6、7、8的八张牌，初始状态S0,目标状态为Sg。可以使用的操作有：空格左移、上移、下移、右移状态任一时刻,综合数据库的情况;237

51486{A，B，C，D} （c,a,b,0,0）状态空间状态空间所有可能的状态的全体.237

51486586

12743124

65783……状态转移初始状态目标状态状态转移规则237

51486237

45186搜索(search)路径状态序列搜索寻找从初始状态到目标状态的路径;S0Sg搜索问题状态空间237

5148612384765搜索不是检索237

5148612384765搜索与检索的区别状态是否动态生成;检索:静态;在数据库中检索某人的纪录;搜索:动态生成;下棋难点237

5148612384765状态空间搜索步骤状态空间搜索实际上就是对有向图的搜索。先把问题的初始状态当作当前扩展节点对其进行扩展，生成一组子节点，然后检查问题的目标状态是否出现在这些子节点中。若出现，则搜索成功，找到了该问题的解；若没有出现，则按照某种搜索策略从已生成的子节点中选择一个作为当前扩展节点。重复上述过程，直到目标状态出现在子节点中或没有可供扩展的节点为止。状态空间搜索算法（准备）若要讨论状态空间搜索的一般算法，需要：Open表和Closed表这样两个数据结构。其中，Open表用于存放还没有扩展的节点，因此，Open表称为未扩展的节点表。

Closed表用于存放已经扩展或将要扩展的节点，因此，Closed称为已扩展的节点表。用S0表示问题的初始状态，G表示搜索过程所得到的搜索图，M表示当前扩展节点新生成的且不为自己先辈的子节点集。算法(simpleversion)1．建立一个只有起始节点S0组成的图G,把S0放到OPEN表中；2．建立一个CLOSED表，置为空；3．While(!NULL(OPEN))a)从OPEN表中取出（并删除）第一个节点n放入

CLOSED表。

b)如果n是目标节点，成功结束；

c)扩展节点n，把n的后继加入G中；

d)把n的后继加入OPEN表中,并建立它们到n的指针；

e)

对OPEN表中的节点排序；4．返回FAIL；例子SOPENCLOSE{S}{}123{}{S}{1,2,3}{S}{2,1,3}{S}45{1,3}{S,2}{1,3,4,5}{S,2}{3,1,4,5}{S,2}{1,4,5}{S,2,3}6{1,4,5,6}{S,2,3}算法4.1状态空间图的一般搜索算法：1、把初始节点S0放入Open表中，并建立目前仅包含S0的图G；2、检查是否为空，若为空，则问题无解，失败退出；3、把Open表的第一个节点取出放入Closed表中，并记该节点为节点n；4、考察节点n是否为目标节点，若是则得到问题的解，成功退出；5、扩展节点n,生成一组子节点。把这组节点中不为节点n先辈的子节点记入集合M,并把这些节点作为节点n的子节点加入G中。6、针对中子节点的不同情况，分别处理如下（1-3）：对那些没有在G中出现过的M成员设置一个指向其父节点的指针，并把它放入Open表中。对那些原来已在G中出现过，但还没有被扩展的M成员，确定是否需要修改指向其父节点的指针。对原来已在G中出现过，并已经扩展了的M成员，确定是否需要修改其后继节点指向父节点的指针。7、按某种策略对Open表中节点排序。8、转第2步。示例如下：2S1345{1,2,3}{S}{3,1,2}

{S}OPENCLOSE{S}{}{4,5,1,2}

{S,3}67{6,7,5,1,2}

{S,3,4}89{8,9,7,5,1,2}

{S,3,4,6}{10,11,9,7,5,1,2}

{S,3,4,6,8}10111213{13,10,11,9,7,5,2}

{S,3,4,6,8,1,12}14{14,10,11,9,7,5,2}

{S,3,4,6,8,1,12,13}2S13{1,2,3}{S}{3,1,2}

{S}OPENCLOSE{S}{}245{4,5,1,2}

{S,3}67{6,7,5,1,2}

{S,3,4}89{8,9,7,5,1,2}

{S,3,4,6}{10,11,9,7,5,1,2}

{S,3,4,6,8}10111213{13,10,11,9,7,5,2}

{S,3,4,6,8,1,12}14OPEN表中的节点修改指针2S13{1,2,3}{S}{3,1,2}

{S}OPENCLOSE{S}{}245{4,5,1,2}

{S,3}67{6,7,5,1,2}

{S,3,4}89{8,9,7,5,1,2}

{S,3,4,6}{10,11,9,7,5,1,2}

{S,3,4,6,8}10111213{13,10,11,9,7,5,2}

{S,3,4,6,8,1,12}14{13,10,11,9,7,5}

{S,3,4,6,8,1,12,2}2S13{1,2,3}{S}{3,1,2}

{S}OPENCLOSE{S}{}245{4,5,1,2}

{S,3}67{6,7,5,1,2}

{S,3,4}89{8,9,7,5,1,2}

{S,3,4,6}{10,11,9,7,5,1,2}

{S,3,4,6,8}10111213{13,10,11,9,7,5,2}

{S,3,4,6,8,1,12}14{13,10,11,9,7,5}

{S,3,4,6,8,1,12,2}CLOSED表中的节点修改指针2S13{1,2,3}{S}{3,1,2}

{S}OPENCLOSE{S}{}245{4,5,1,2}

{S,3}67{6,7,5,1,2}

{S,3,4}89{8,9,7,5,1,2}

{S,3,4,6}{10,11,9,7,5,1,2}

{S,3,4,6,8}10111213{13,10,11,9,7,5,2}

{S,3,4,6,8,1,12}14{13,10,11,9,7,5}

{S,3,4,6,8,1,12,2}CLOSED表中节点(8)的后裔(10)修改指针算法说明各种搜索策略的主要区别在于对Open表中节点排序的不同；一旦被考察的节点是目标节点时,算法成功结束;

算法结束后，将生成一个图G，称为搜索图。同时由于每个节点都有一个指针指向父节点，这些指针指向的节点构成G的一个支撑树，称为搜索树。

修改指针:找最优解；检查新产生的节点以前是否产生过，计算量较大;2S134567891011121314搜索图2S1324567891011121314搜索树4.2.1状态空间盲目搜索无须重新安排OPEN表的搜索叫做无信息搜索或盲目搜索，它包括宽度优先搜索、深度优先搜索和等代价搜索等。盲目搜索只适用于求解比较简单的问题。一、宽度优先搜索宽度优先搜索(breadth-firstsearch)又称为广度优先搜索，是一种盲目搜索策略。其基本思想是，从初始节点开始，向下逐层对节点进行依次扩展，并考察它是否为目标节点，在对下层节点进行扩展（或搜索）之前，必须完成对当前层的所有节点的扩展。在搜索过程中，未扩展节点表OPEN中的节点排序准则是：先进入的节点排在前面，后进入的节点排在后面。二、深度优先搜索另一种盲目(无信息)搜索叫做深度优先搜索(depth-firstsearch)。在深度优先搜索中，首先扩展最新产生的(即最深的)节点。深度相等的节点可以任意排列。我们定义节点的深度如下：(1)起始节点(即根节点)的深度为0。(2)任何其他节点的深度等于其父辈节点的深度加1。三、等代价搜索在等代价搜索算法中，把从节点i到其后继节点j的连接弧线代价记为c(i,j)，把从起始节点s到任一节点i的路径代价记为g(i)。在搜索树上，假设g(i)也是从起始节点s到节点i的最少代价路径上的代价，因为它是惟一的路径。等代价搜索方法以g(i)的递增顺序扩展其节点，等代价搜索方法：

(1)把起始节点s放到未扩展节点表OPEN中。如果此起始节点为一目标节点，则求得一个解；否则令g(s)=0。

(2)如果OPEN是个空表，则没有解而失败退出。

(3)从OPEN表中选择一个节点i，使其g(i)为最小。如果有几个节点都合格，那么就要选择一个目标节点作为节点i(要是有目标节点的话)；否则，就从中选一个作为节点i。把节点i从OPEN表移至扩展节点表CLOSED中。

(4)如果节点i为目标节点，则求得一个解。

(5)扩展节点i。如果没有后继节点，则转向步骤(2)。

(6)对于节点i的每个后继节点j，计算g(j)=g(i)+c(i,j)，并把所有后继节点j放进OPEN表。提供回到节点i的指针。

(7)转向步骤(2)。4.2.2状态空间启发式搜索前面我们讨论的各种搜索策略的一个共同的特点就是它们的搜索路线是事先决定好的，没有利用被求解问题的任何特性信息，在决定要扩展的节点时，没有考虑该节点到底是否可能出现在解的路径上，也没有考虑它是否有利于问题的求解以及所求的解是否为最优解，这样的搜索策略具有很大的盲目性。如果能够找到一种方法用于排列待扩展节点的顺序，即选择最有希望的节点加以扩展，那么，搜索效率将会大为提高。在许多情况下，能够通过检测来确定合理的顺序。本节所介绍的搜索方法就是优先考虑这类检测，称这类搜索为启发式搜索(heuristicallysearch)或有信息搜索(informedsearch)。一、启发式搜索策略和估价函数我们用f(n)表示节点n的估价函数，则f(n)可以为任意函数。如f(n)可以表示节点n处于最佳路径的概率，也可以表示节点n到目标节点的距离。一般来说，估价一个节点价值必须考虑两方面的因素：已经付出的代价和将要付出的代价。二、最佳优先搜索最佳优先搜索(best-firstsearch)又称为有序搜索(orderedsearch)，它总是选择最有希望的节点作为下一个要扩展的节点，而这种最有希望的节点是按估价函数f(n)的值来挑选的，一般估价函数的值越小，它的希望程度就越大。根据习惯，我们把OPEN表上的节点按照它们估价函数值的递增顺序排列。根据推测，某个具有低的估价值的节点较有可能处在最佳路径上。最佳优先搜索算法：（1）把起始节点s放到OPEN表中，计算其估价值f(s)。（2）如果OPEN是个空表，则失败退出，无解。（3）从OPEN表中选择一个f值最小的节点i。结果有几个节点合格，当其中有一个为目标节点时，则选择此目标节点，否则就选择其中任一个节点作为节点i。（4）把节点i从OPEN表中移出，并把它放入CLOSED表中。（5）如果i是个目标节点，则成功退出，求得一个解。（6）扩展节点i，生成其全部后继节点。对于i的每一个后继节点j：(a)计算f(j)。(b)如果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）。三、A*算法g*(n)：从S0到n的最小代价值值h*(n)：从n到Sg的最小代价值f*(n)=g*(n)+h*(n)：从S0经过n到Sg的最小代价值值g(n)、h(n)、f(n)分别是g*(n)、h*(n)、f*(n)的估计值对A算法（全局择优）的g(n)、h(n)分别提出如下限制：g(n)是对g*(n)的估计，且g(n)>0;h(n)是h*(n)的下界，即对任意节点n均有h(n)≤h*(n)。则称得到的算法为A*算法。4.3与/或树搜索与/或树是不同于状态空间法的另外一种用于表示问题及求解过程的形式化方法，通常用于表示比较复杂的问题求解。与/或树搜索的目标是寻找解树，从而求得原始问题的解。如果在搜索的某一时刻，通过可解标示过程可确定初始节点是可解的，则由初始节点及其下属的可解节点就构成了解树。如果在某时刻被选为扩展的解点不可扩展，并且它不是终止节点，则此节点就是不可解节点。此时可应用不可解标示过程确定初始节点是否为不可解节点，如果可以肯定初始节点是不可解节点，则搜索失败，否则继续扩展节点。4.3.1与/或树的盲目搜索对于与/或树的盲目搜索，通常有宽度优先搜索、深度优先搜索和有界深度优先搜索等。因篇幅所限，我们这里仅介绍与/或树的宽度优先搜索算法。与/或树的宽度优先搜索1、把初始节点S0放入Open表中；2、把Open表的第一个节点取出放入Closed表中，并记该节点为节点n；3、若节点n可扩展，则做下列工作：①扩展节点n，将其子节点放入Open表的尾部，并为每一个子节点设置指向父节点的指针；②考察这些子节点是否有终止节点。若有，则标记这些终止节点为可解节点，并用可解标记过程对其父节点或先辈节点中可解节点进行标记。如初始节点S0被标记为可解节点，得到解树，成功退出。如不能确定为S0可解节点，则从Open表中删除具有可解先辈的节点；③转第2步4、如果节点不可扩展，则做下列工作：①标记节点n为不可解节点；②用不可解标记过程对节点n的先辈节点中不可解节点进行标记。如初始节点S0被标记为不可解节点，原问题无解而失败退出。如不能确定S0为不可解节点，则从Open表中删除具有不可解先辈的节点；③转第2步4.3.2与/或树的启发式搜索解树的代价希望树与/或树的启发式搜索解树的代价最优解树是指代价最小的那棵解树。终止节点，代价为0或节点代价取其子节点中的最小值与节点有和代价法与节点代价最大值法；不可解节点代价∝根节点的代价为解树的代价例子:解树的代价(1)n0n1n2n3n4n5n6n7n8代价:9

k(n0,N)=C(n0,n1)+K(n1,N)=1+K(n1,N)=1+C(n1,n3)+K(n3,N)=1+1+K(n3,N)=1+1+2+K(n5,N)+K(n6,N)=1+1+2+1+K(n6,N)+K(n6,N)=1+1+2+1+2+K(n7,N)+K(n8,N)+K(n6,N)=1+1+2+1+2+K(n6,N)=1+1+2+1+2+2+K(n7,N)+K(n8,N)=1+1+2+1+2+2=9n0n1n2n3n4n5n6n7n8代价:8

k(n0,N)=C(n0,n1)+K(n1,N)=1+K(n1,N)=1+C(n1,n3)+K(n3,N)=1+1+K(n3,N)=1+1+2+K(n5,N)+K(n6,N)=1+1+2+2+K(n7,N)+K(n8,N)+K(n6,N)=1+1+2+2+K(n6,N)=1+1+2+2+2+K(n7,N)+K(n8,N)=1+1+2+2+2=8例子:解树的代价(2)例子:解树的代价(3)代价:7代价:5n0n1n2n3n4n5n6n7n8n0n1n2n3n4n5n6n7n8n0n1n2n3n4n5希望树从n到N的解树中，代价最小的解树称为最佳解树。

为找到最佳解树，搜索过程的任何时刻都应该选择那些最有希望成为最佳解树一部分的节点进行扩展。由于这些节点及其父节点所构成的与/或树最有可能成为最佳解树的一部分，因此称之为希望树。希望树主要是针对或节点而言。希望树定义初始节点S0在希望树T中；如果n是具有子节点n1,n2,…,nk的或节点，则n的某个子节点ni在希望树中的充分必要条件是：

h(ni)=min{c(n,ni)+h(ni)}如果n是与节点，则n的全部子节点都在希望树T中。与/或树的启发式搜索与/或树的启发式搜索算法也称为AO*算法。与/或树的启发式搜索需要不断地选择、修正希望树AO*算法利用h(n)探索求解k(n0,N)=C1+K(n1,N) =1+K(n1,N)k(n0,N)=C2+K(n4,N)+K(n5,N) =2+K(n4,N)+K(n5,N)n0n1n4n5c1c2k(n0,N)=C1+K(n1,N)

1+h(n1)k(n0,N)=C2+K(n4,N)+K(n5,N)

2+h(n4)+h(n5)扩展一个部分解树后,要重新计算这个解树代价的估计值;

n0n1n4n5c1c2c3n3k(n0,N)=C1+K(n1,N)

1+h(n1)k(n0,N)=C1+C3+K(n3,N)

2+h(n3)两个过程树生成过程，即扩展节点计算解树代价的过程特点用标记来追踪解树把初始节点S0放入Open表中，计算

h(S0)；计算希望树T；把OPEN表中取出T的端节点n放入CLOSED表。如节点n不是终止节点且可扩展，生成n的所有后继并将所有扩展节点放入Open表中，为每个后继设置指向其父节点的指针，计算这些子节点及其先辈节点的h值，转2；如节点n不是终止节点且不可扩展，标记n为不可解节点；在树T上应用不可解标记过程，并为n的先辈节点中所有不可解节点进行标记，如果初始节点可以标记为不可解节点，失败退出，否则从OPEN表中删除具有不可解先辈的所有节点，转2；如节点n是终止节点，标记n为可解节点；在树T上应用可解标记过程，如果初始节点可以标记为可解节点，成功退出，否则从OPEN表中删除具有可解先辈的所有节点后转2；4.4博弈树的启发式搜索博弈具有“二人零和、全信息、非偶然”的特征。(1)所谓“二人零和”指的是：对垒的MAX、MIN双方轮流采取行动，博弈的结果只有