1、第三章第三章 搜索技术搜索技术 一般来说，一个智能体有多个评价未知的直接选项一般来说，一个智能体有多个评价未知的直接选项的时候，可以首先检验各个不同的能导致已知评价的状的时候，可以首先检验各个不同的能导致已知评价的状态的可能序列，然后选择最佳序列，上述过程被称为态的可能序列，然后选择最佳序列，上述过程被称为搜搜索索。搜索算法把问题初始状态作为输入，并以行动序列。搜索算法把问题初始状态作为输入，并以行动序列的形式返回问题的解。的形式返回问题的解。在搜索过程中，除了问题中提供的定义之外没有任在搜索过程中，除了问题中提供的定义之外没有任何关于状态的附加信息，称为何关于状态的附加信息，称为盲目搜索盲目
2、搜索。若在搜索过程。若在搜索过程中知道一个非目标状态是否比其它状态中知道一个非目标状态是否比其它状态“更有希望更有希望”接接近目标的策略被称为近目标的策略被称为启发式搜索启发式搜索。第一节第一节 盲目搜索盲目搜索一、广度优先搜索一、广度优先搜索 广度优先搜索广度优先搜索是一个简单的搜索策略，首先是扩是一个简单的搜索策略，首先是扩展根节点，接着扩展根节点的所有后继，然后再扩展展根节点，接着扩展根节点的所有后继，然后再扩展它们的后继，依此类推。一般来讲，在下一层的任何它们的后继，依此类推。一般来讲，在下一层的任何节点扩展之前搜索树上本层深度的所有节点都已被扩节点扩展之前搜索树上本层深度的所有节点都
3、已被扩展过。展过。1.1.数据结构数据结构 OPENOPEN表：表：一个先进先出的队列，用于存储待扩展一个先进先出的队列，用于存储待扩展的节点。的节点。CLOSEDCLOSED表：表：一个用于存储已被扩展过的节点的线一个用于存储已被扩展过的节点的线性表。性表。上图中：1 1、OPEN=S;CLOSED=OPEN=S;CLOSED=2 2、OPEN=AOPEN=A1 1，A A2 2，A A3 3;CLOSED=S;CLOSED=S3 3、OPEN=AOPEN=A2 2，A A3 3，B B1 1，B B2 2;CLOSED=A CLOSED=A1 1，SS4 4、OPEN=AOPEN=A3 3
4、，B B1 1，B B2 2，B B3 3，B B4 4，CLOSED=ACLOSED=A2 2，A A1 1，SS5 5、OPEN=BOPEN=B1 1，B B2 2，B B3 3，B B4 4，B B5 5，CLOSED=ACLOSED=A3 3，A A2 2，A A1 1,S,S 1111、OPEN=COPEN=C2 2，C C3 3，C C4 4，D D1 1，CLOSED=CCLOSED=C1 1，B B5 5，B B4 4，B B3 3，B B2 2，B B1 1，A A3 3，A A2 2，A A1 1，SS深度广度时间内存需求211000.11秒1M字节4111，10011秒1
5、06M字节619分钟10G字节 831小时1T字节10129天101T字节1235年10P字节71091011101510假设，每个节点的分支数为假设，每个节点的分支数为1010；1000010000节点节点/秒；秒；10001000字节字节/节点节点3.3.小结小结（1 1）由于该种搜索方法总是在检查完）由于该种搜索方法总是在检查完N N层的节点之后才转向层的节点之后才转向N+1N+1层的检查，因此，它总能找到最短路径解。层的检查，因此，它总能找到最短路径解。（2 2）广度优先算法中内存的需求是比执行时间消耗更大的）广度优先算法中内存的需求是比执行时间消耗更大的问题。问题。（3 3）时间的需
6、求仍然是主要因素。）时间的需求仍然是主要因素。二、深度优先搜索二、深度优先搜索 深度优先搜索深度优先搜索是另一个简单的搜索策略，它总是是另一个简单的搜索策略，它总是扩展最新产生的（即最深的）节点，使得搜索沿着状扩展最新产生的（即最深的）节点，使得搜索沿着状态空间某一条单一的路径向下进行；只有当搜索到一态空间某一条单一的路径向下进行；只有当搜索到一个没有后继的状态时，它才考虑另一条替代路径。个没有后继的状态时，它才考虑另一条替代路径。节点的节点的深度深度定义如下：根节点的深度为定义如下：根节点的深度为0 0；其它任；其它任何节点的深度等于其父亲节点的深度何节点的深度等于其父亲节点的深度+1+1。
7、1.1.数据结构数据结构 OPENOPEN表：表：一个先进后出的堆栈，用于存储待扩展一个先进后出的堆栈，用于存储待扩展的节点。的节点。CLOSEDCLOSED表：表：一个用于存储已被扩展过的节点的线一个用于存储已被扩展过的节点的线性表。性表。D D：深度界限（许多复杂问题搜索树的深度可能无深度界限（许多复杂问题搜索树的深度可能无限深，为了避免考虑太长的路径，往往给出一个节点限深，为了避免考虑太长的路径，往往给出一个节点扩展的最大深度）。扩展的最大深度）。2.2.算法（算法（深度有界搜索深度有界搜索）（1 1）将初始节点）将初始节点S S放入放入OPENOPEN表中，若表中，若S S为目标节点，
8、则得到一为目标节点，则得到一 个解。个解。（2 2）若）若OPENOPEN表为空，则失败退出。表为空，则失败退出。（3 3）把第一个节点（节点）把第一个节点（节点n n）从）从OPENOPEN移到移到CLOSEDCLOSED表。表。（4 4）若节点）若节点n n的深度等于的深度等于D D（深度界限），则转（深度界限），则转（2 2）。）。（5 5）扩展节点）扩展节点n n，产生其所有后继，并将它们放入，产生其所有后继，并将它们放入OPENOPEN表中。表中。若没有后继，则转向（若没有后继，则转向（2 2）。）。（6 6）如果后继节点中有任一为目标节点，则得到一个解，成）如果后继节点中有任一为目
9、标节点，则得到一个解，成 功退出；否则，转向（功退出；否则，转向（2 2）SS1S2S3S5S4S6S71 1、OPEN=S;CLOSED=OPEN=S;CLOSED=2 2、OPEN=SOPEN=S1 1，S S2 2，S S3 3;CLOSED=S;CLOSED=S3 3、OPEN=SOPEN=S4 4，S S5 5，S S1 1，S S2 2，S S3 3;CLOSED=S CLOSED=S1 1，SS4 4、OPEN=SOPEN=S6 6，S S5 5，S S1 1，S S2 2，S S3 3，CLOSED=SCLOSED=S4 4，S S1 1，SS5 5、OPEN=SOPEN=S7
10、 7，S S5 5，S S1 1，S S2 2，S S3 3，CLOSED=SCLOSED=S6 6，S S4 4，S S1 1，S S 3.3.小结小结 （1 1）深度优先搜索算法是不完备的。）深度优先搜索算法是不完备的。（2 2）深度优先搜索耗费的空间量是路径长度值的线性函数，）深度优先搜索耗费的空间量是路径长度值的线性函数，OPENOPEN在每一层只保留一个状态的子状态，如果图中每个在每一层只保留一个状态的子状态，如果图中每个 状态平均有状态平均有B B个子状态，则搜索到图中第个子状态，则搜索到图中第n n层时要求层时要求B Bn n 个状态的空间，有大量分支的图时会有相当高的效率。个状
11、态的空间，有大量分支的图时会有相当高的效率。（3 3）深度优先搜索可尽快进入底层，但会在深处迷失方向，找）深度优先搜索可尽快进入底层，但会在深处迷失方向，找 不到目标的最短路径或陷入到一个不通往目标的无限长的不到目标的最短路径或陷入到一个不通往目标的无限长的 路径中。路径中。三、代价一致搜索三、代价一致搜索 当所有单步耗散相等的时候，广度优先搜索是最优的，当所有单步耗散相等的时候，广度优先搜索是最优的，因为它总是先扩展深度最浅的未扩展节点。简单的延伸一下，因为它总是先扩展深度最浅的未扩展节点。简单的延伸一下，取代扩展深度最浅的节点，取代扩展深度最浅的节点，代价一致搜索代价一致搜索扩展的是扩展的
12、是路径消耗路径消耗最低最低的节点的节点n n，如果所有单步耗散相等的话，如果所有单步耗散相等的话，代价一致搜索代价一致搜索算算法和广度悠闲搜索算法是一样的。法和广度悠闲搜索算法是一样的。第二节第二节 启发式搜索启发式搜索一、基本概念一、基本概念 先剖析先剖析“启发式搜索启发式搜索”这几个字：这几个字：启发启发（heuristicheuristic）：其内容包括发现、发明规则）：其内容包括发现、发明规则及其研究方法。及其研究方法。在状态空间搜索中，启发式被定义成一系列规则，在状态空间搜索中，启发式被定义成一系列规则，它从状态空间中选择最有希望到达问题解的路径。它从状态空间中选择最有希望到达问题解
13、的路径。启发式搜索1 1、在人工智能问题求解中为什么要研究启发式策略？、在人工智能问题求解中为什么要研究启发式策略？在问题求解中有在问题求解中有不确定性不确定性问题；问题；例：医学中的一些基本问题；例：医学中的一些基本问题；在问题求解中有在问题求解中有模糊性模糊性等问题；等问题；例：视觉问题例：视觉问题所求解问题可能有确定解，但它有所求解问题可能有确定解，但它有组合爆炸组合爆炸等问题存等问题存在，最终还是达不到问题求解的目的。在，最终还是达不到问题求解的目的。在问题求解中有定性描述过程存在，但对此类问题只在问题求解中有定性描述过程存在，但对此类问题只能借助经验给予能借助经验给予定量定量帮助描述
14、帮助描述。2 2、利用启发式搜索策略有何优势？、利用启发式搜索策略有何优势？可以帮助我们解决问题求解过程中存在的可以帮助我们解决问题求解过程中存在的不确定性不确定性、模糊性模糊性；可以降低问题求解的可以降低问题求解的复杂性复杂性；可以帮助我们可以帮助我们简化问题简化问题；3 3、启发式搜索的构成及目的、启发式搜索的构成及目的启发式搜索由启发式搜索由启发式方法启发式方法和和启发式搜索启发式搜索算法两部分算法两部分构成。构成。启发式搜索的目的是：利用启发式搜索可能得到一启发式搜索的目的是：利用启发式搜索可能得到一个次最佳解，也可能一无所获。这也是启发式搜索固个次最佳解，也可能一无所获。这也是启发式
15、搜索固有的局限性。有的局限性。二、二、启发式搜索的估价函数确定方法启发式搜索的估价函数确定方法 众所周知，在智能活动中，使用最多的方法不是完备性方法，众所周知，在智能活动中，使用最多的方法不是完备性方法，而是不一定完备的启发式方法。其原因是：而是不一定完备的启发式方法。其原因是：1 1、大多数智能系统不知道与实际问题有关的全部信息，因此，、大多数智能系统不知道与实际问题有关的全部信息，因此，在具体求解问题时只能借助部分信息加上经验去处理；在具体求解问题时只能借助部分信息加上经验去处理；2 2、理论值与工程中的关系；、理论值与工程中的关系；3 3、有些智能行为无法用现有的工具推导表示，只能用经验
16、关、有些智能行为无法用现有的工具推导表示，只能用经验关 系表示：系表示：由此可见，无论在理论方面还是在应用方面都需要启发式方由此可见，无论在理论方面还是在应用方面都需要启发式方法。法。我们知道在问题求解的搜索图中，从节点与节点我们知道在问题求解的搜索图中，从节点与节点之间的关系来看有：过去节点、当前节点、将来节点之间的关系来看有：过去节点、当前节点、将来节点三种类型，即三种类型，即过去节点当前节点将来节点 我们把这三种类型节点的关系用一个评估函数我们把这三种类型节点的关系用一个评估函数表示为：表示为：f(n)=g(n)+h(n)（2）其中：其中：g(n)表示从初始节点到当前节点的代价；表示从初
17、始节点到当前节点的代价；h(n)表示从当前节点到目标节点最佳路表示从当前节点到目标节点最佳路 径的估计代价。径的估计代价。在在 f(n)=g(n)+h(n)，中，若有，中，若有g(n)h(n)，则有，则有f(n)=g(n)（3）若有若有 g(n)2 （5）深度优先：深度优先：f2(n)=M n M，n2 （6）有界深度：有界深度：f3(n)=Mn+K k0 M，n2 （7）在（在（2）式中：当）式中：当g(n)h(n)时：时：f(n)f1(n)（8）在（在（2）式中，当）式中，当h(n)g(n)时时 f(n)f2(n)（9）三、启发式搜索算法三、启发式搜索算法1.1.局部优先搜索法局部优先搜索
18、法（瞎子爬山法）（瞎子爬山法）瞎子爬山法只考虑当前节点与目标节点之间的关系，即启瞎子爬山法只考虑当前节点与目标节点之间的关系，即启发式估价函数为：发式估价函数为：f(n)=h(n)f(n)=h(n)瞎子爬山法只选择邻居状态中状态最好的一个，而不事先瞎子爬山法只选择邻居状态中状态最好的一个，而不事先考虑下一步向哪个方向走。该方法能很快地朝着解的方向进展，考虑下一步向哪个方向走。该方法能很快地朝着解的方向进展，但常常会只找到局部最大值。但常常会只找到局部最大值。状态空间状态空间山肩山肩全局最大值全局最大值局部最大值局部最大值从不同初始状态爬山，到达的从不同初始状态爬山，到达的“峰顶峰顶”是不同的是
19、不同的。例例 用瞎子爬山法求下列九宫问题：用瞎子爬山法求下列九宫问题：f(n)=h(n)f(n)=h(n)其中：其中：h(n)h(n)表示格子中的数字和目标数字错表示格子中的数字和目标数字错位个数之和。位个数之和。（1）（2）2831647512384765283164752831476528316475283164752318476528314765231847652318476583214765123847651238476535533243102.2.最好优先搜索法（有序搜索法）最好优先搜索法（有序搜索法）最好优先搜索法也使用两张表来记录节点信息，在最好优先搜索法也使用两张表来记录节点信
20、息，在openopen表表中保留所有已生成而未考察的节点；在中保留所有已生成而未考察的节点；在ClosedClosed表中记录已访问表中记录已访问过的节点。算法中有一步是根据某些启发信息，按过的节点。算法中有一步是根据某些启发信息，按节点距离目节点距离目标状态的长度大小标状态的长度大小重排重排openopen表中的节点，这样，循环中的每一表中的节点，这样，循环中的每一步只考虑步只考虑openopen表中表中状态最好状态最好的节点，这就是最好优先搜索算法，的节点，这就是最好优先搜索算法，又称有序搜索法。又称有序搜索法。即：原始节点状态：即：原始节点状态：open=A1open=A1，A3A3，A
21、2An AmA2An Am 重排之后重排之后 重排后状态节点：重排后状态节点：open=A1open=A1，A2A2，A3AmAn A3AmAn*最好优先搜索算法描述和分析：最好优先搜索算法描述和分析：最好优先搜索算法总是从最好优先搜索算法总是从openopen表中选取最表中选取最“好好”的状态进的状态进行扩展。但是，由于启发信息有时可能出错，故算法并不丢弃行扩展。但是，由于启发信息有时可能出错，故算法并不丢弃其他的状态而把它们保留在其他的状态而把它们保留在openopen表中，当某一个启发信息将搜表中，当某一个启发信息将搜索导向错误路径时，算法可以从索导向错误路径时，算法可以从openope
22、n表中检索先前产生的表中检索先前产生的“次次最好最好”状态，并且考虑方向转向空间的另一部份状态，并且考虑方向转向空间的另一部份。A1A3A2A4A5A6A7A8A9A20A19A18A17A16A15A14A13A12A11A10如图以 包围的区域出错，则返回到未包围的区域*启发式搜索技术小结启发式搜索技术小结 f(n)=g(n)+h(n)f(n)=g(n)+h(n)中：中：g(n)g(n)保证了宽度优先搜索的性质，保证了宽度优先搜索的性质，h(n)h(n)保证了有最好的路径，因此，最好优先搜索方法为我们保证了有最好的路径，因此，最好优先搜索方法为我们提供了启发式搜索的一般原则，总结起来有：提
23、供了启发式搜索的一般原则，总结起来有：a a、根据产生式规则和一些其他的操作，生成当前考察结点、根据产生式规则和一些其他的操作，生成当前考察结点 的子状态；的子状态；b b、检查每个子状态以前是否已经考察过（已在、检查每个子状态以前是否已经考察过（已在openopen表或表或 ClosedClosed表中），以防止循环；表中），以防止循环；c c、每个状态都以、每个状态都以f(n)f(n)值为依据进行搜索；值为依据进行搜索；d d、openopen表中的状态按表中的状态按f(n)f(n)值排序；值排序；e e、通过设计、通过设计openopen表和表和ClosedClosed表的存储方式，可以提高算法表的存储方式，可以提高算法 的效率。的效率。四、启发式搜索过程的基本性质四、启发式搜索过程的基本性质 1 1、找最短路径：只要有解存在，用一个启发式策略、找最短路径：只要有解存在，用一个启发式策略 就能找到。就能找到。可采纳性可采纳性 2 2、比较两个启发式的好坏。、比较两个启发式的好坏。信息性信息性 3 3、用启发式搜索得到某一状态，能否保证同样的状、用启发式搜索得到某一状态，能否保证同样的状 态在以后的搜索中不会出现更大的代价。态在以后的搜索中不会出现更大的代价。单调性单调性
