第4章搜索策略

人工智能原理篇搜索策略第四章本章导读现实世界中多数问题都是非结构化的，一般不能用直接求解的方法来求解这样的问题，而只能利用已有的知识一步一步地摸索着前进。因此，常常使用基于搜索策略的方法来求解问题。搜索策略是人工智能的基本求解策略之一，已在人工智能各领域得到了广泛应用。本章主要介绍基于状态空间表示法的搜索策略，包括盲目搜索策略和启发式搜索策略。学习目标熟悉搜索的基本内容。理解搜索策略的思想。掌握宽度优先搜索、深度优先搜索和等代价搜索等盲目搜索策略。掌握A搜索和A*搜索等启发式搜索策略。目录

4搜索概述盲目搜索策略启发式搜索策略010203搜索概述01搜索的概念4.1.1搜索就是根据问题的实际情况，按照一定的策略或规则，从知识库中寻找可利用的知识，从而构造出一条代价较小的推理路线，使问题得到解决的过程。搜索是人工智能中的一个核心技术，是推理不可分割的一部分，它直接关系到智能系统的性能和运行效率。在搜索问题中，主要的工作是找到正确的搜索策略。搜索策略反映了状态空间或问题空间扩展的方法，也决定了状态或问题的访问顺序。在人工智能中，通过运用搜索策略解决问题的基本思想是：首先把问题的初始状态（即起始节点）作为当前状态，选择适用的操作符对其进行操作，生成一组子状态（即后继节点），然后检查目标状态是否在其中出现。若出现，则搜索成功，找到了问题的解；若未出现，则按某种搜索策略从已生成的状态中再选一个状态作为当前状态。重复上述过程，直到目标状态出现或者不再有可供操作的状态及操作符为止。在运用搜索策略求解问题的过程中，涉及的数据结构除了状态空间图之外，还需要两个辅助的数据结构，即存放已访问但未扩展节点的OPEN表，以及存放已扩展节点的CLOSED表。状态空间图的搜索过程如左图所示。搜索过程4.1.2

（6）扩展节点n，生成后继节点集合M，并将集合M中的成员作为n的后继节点添加入搜索图中。（7）针对M中后继节点的不同情况，分别做如下处理。①对那些未曾在搜索图中出现过的（既未曾在OPEN表中，也未在CLOSED表中出现过）M成员，设置其父节点指针指向n，并加入OPEN表中。②对那些原来已在搜索图中出现过，但还没有扩展的（已经在OPEN表或CLOSED表中出现过）M成员，确定是否需要将其原来的父节点更改为n。③对那些先前已在搜索图中出现过，并已经扩展了的（已在CLOSED表中）M成员，确定是否需要修改其后继节点指向父节点的指针。若修改了其父节点，则将该节点从CLOSED表中移出，重新加入OPEN表中。（8）按某一方式或按某个估价值，重排OPEN表。继续执行步骤（3）。知识库

添砖加瓦在搜索过程中需要解决的基本问题有：（1）搜索过程是否一定能找到一个解。（2）当搜索过程找到一个解时，找到的是否是最佳解。（3）搜索过程的时间与空间复杂性如何。（4）搜索过程是否能终止运行或是否会陷入一个死循环。根据搜索过程中是否运用与问题有关的信息，可以将搜索策略分为盲目搜索策略和启发式搜索策略。在搜索过程中对OPEN表的节点排序，主要目的是希望从未扩展节点中选出一个最具有希望的节点作为下一个扩展节点使用。若此时的排序是任意的或者是盲目的，则为盲目搜索；若排序是以各种启发式思想或其他准则为依据的，则为启发式搜索。搜索策略4.1.3盲目搜索策略02盲目搜索策略又称无信息搜索策略，也就是说，在搜索过程中，只按照预先规定的搜索策略进行搜索，而没有任何中间信息来改变这些策略。常用的盲目搜索策略有宽度优先搜索、深度优先搜索和等代价搜索等。

4.2.1宽度优先搜索宽度优先搜索宽度优先搜索的搜索过程可用如左图所示的算法描述。宽度优先搜索算法【例4-1】

猫捉老鼠问题，猫位于A处，它发现K处有一只老鼠（见左图），请用宽度优先搜索算法帮猫寻找捕捉路线。猫和老鼠的位置表示【解】使用宽度优先搜索算法解决猫捉老鼠问题的步骤如下。（1）猫所在的位置A是起始节点，将A放入OPEN表中。（2）判断该起始节点A是否为一目标节点，若是，则求得一个解并成功退出；否则继续。节点A不是老鼠所在的位置，所以不是目标节点。（3）判断OPEN表是否为空表，若是空表，则没有解，失败退出；否则继续。OPEN表中有节点A，非空，继续执行。（4）把OPEN表中的第一个节点（记为节点n）移出，并放入CLOSED表中。将节点A从OPEN表中移出，并放入CLOSED表中。（5）判断节点n是否有后继节点，若有，则继续；否则，转向（3）。节点A有后继节点，继续执行。（6）扩展节点n，把节点n的所有后继节点放入OPEN表的末端，并提供从这些后继节点回到父节点n的指针。即扩展节点A，其后继节点有B和C，将它们放入OPEN表的末端，并提供回到父节点A的指针。（7）判断刚产生的这些后继节点中是否存在一个目标节点，若存在，则找到一个解，成功退出。解可从目标节点到起始节点的返回指针中得到。否则转向（3）。后继节点B和C都不是目标节点，转向（3）。循环执行上述操作，其OPEN表和CLOSED表的状态变化如表所示。OPEN表和CLOSED表的状态变化循环次数OPEN表CLOSED表0（初始化）A空1B、CA2C、D、EA、B3D、E、F、GA、B、C4E、F、G、HA、B、C、D5F、G、HA、B、C、D、E6G、H、I、JA、B、C、D、E、F7H、I、J、KA、B、C、D、E、F、G从表可以看出，在第7次循环中，步骤（7）判断G

产生的后继节点K是目标节点。此时，找到一个解，成功退出。便可得到猫捉老鼠的捕捉路线为。

该搜索结束后得到的搜索树如左图所示。宽度优先搜索树

神经元4.2.2深度优先搜索添砖加瓦节点深度的定义如下。（1）起始节点（即根节点）的深度为0。例如，图中节点A的深度为0。（2）任何其他节点的深度等于其父节点深度加1。例如，图中节点D的深度是2，等于其父节点B的深度1加1。深度相等的节点可以任意排列。例如，图中节点B和C的排列也可以是先C后B。深度优先搜索含有深度界限的深度优先搜索的搜索过程可用如左图所示的算法描述。有界深度优先搜索算法【例】请用含有深度界限的深度优先搜索算法解决例1中的猫捉老鼠问题。【解】使用含有深度界限的深度优先搜索算法解决猫捉老鼠问题的步骤如下。（1）猫所在的位置A是起始节点，将A放入OPEN表中。（2）判断该起始节点A是否为一目标节点，若是，则求得一个解并成功退出；否则继续。节点A不是老鼠所在的位置，所以不是目标节点。（3）判断OPEN表是否为空表，若是空表，则没有解，失败退出；否则继续。OPEN表中有节点A，非空，继续执行。（4）把OPEN表中的第一个节点（记为节点n）移出，并放入CLOSED表中。将节点A从OPEN表中移出，并放入CLOSED表中。（5）判断节点n的深度是否等于深度界限，若等于，则转向（3）；否则继续。针对猫捉老鼠问题，将深度界限设为3。第1次循环中节点A的深度为0，不等于深度界限。（6）判断节点n是否有后继节点，若有，则继续；否则，转向（3）。节点A有后继节点，继续执行（7）扩展节点n，把节点n的所有后继节点放入OPEN表的前端，并提供从这些后继节点回到父节点n的指针。扩展节点A，把A的后继节点B和C放入OPEN表的前端。（8）判断刚产生的这些后继节点中是否存在一个目标节点，若存在，则找到一个解，成功退出。解可从目标节点到起始节点的返回指针中得到。否则转向（3）。后继节点B和C都不是目标节点，转向（3）。循环执行上述操作，第1次循环结束后，OPEN表的节点依次是B、C，然后进行第2次循环，扩展第一个节点B，其后继节点有D和E，将它们放入OPEN表的前端，并提供回到父节点B的指针。

可见，经过第2次循环后，OPEN表的节点依次为D、E、C。在整个搜索过程中，OPEN表和CLOSED表的状态变化如左表所示。循环次数OPEN表CLOSED表0（初始化）A空1B、CA2D、E、CA、B3H、E、CA、B、D4E、CA、B、D、H5CA、B、D、H、E6F、GA、B、D、H、E、C7I、J、GA、B、D、H、E、C、F8J、GA、B、D、H、E、C、F、I9GA、B、D、H、E、C、F、I、J10KA、B、D、H、E、C、F、I、J、GOPEN表和CLOSED表的状态变化从表可以看出，在第10次循环中，步骤（8）判断节点G产生的后继节点K是目标节点。此时，找到一个解，成功退出。便可得到猫捉老鼠的捕捉路线为。

该搜索结束后得到的搜索树如图所示。深度优先搜索树知识库深度优先搜索策略也是一个通用的与问题无关的方法，其性质有：（1）一般不能保证找到路径最短的解。（2）当深度界限设置不合理时，可能找不到解。（3）在最坏情况下，搜索空间等同于穷举。

4.2.3等代价搜索

等代价搜索算法

猫和老鼠位置表示

循环执行上述操作，第1次循环结束后，OPEN表的节点依次是B、C，然后进行第2次循环，扩展路径代价值最小的节点C，其后继节点有F和G，将它们放入OPEN表中，并提供回到父节点C的指针。可见，经过第2次循环后，OPEN表的节点依次为B、F、G。在整个搜索过程中，OPEN表和CLOSED表的状态变化如表所示。OPEN表和CLOSED表的状态变化

等代价搜索树某小说中讲述了一个曲折离奇的故事。在故事中，某人得到了藏有皇家宝藏秘密的宝匣，但是宝匣上面有一个9宫格拼图密码（见左图），只有将图片拼完整才可以打开宝匣。

请采用盲目搜索策略完成拼图任务。宝匣4.2.4案例：宝匣上的拼图【解】（1）用数字表示9宫格内的图片块，则该拼图的初始状态如图1所示，目标状态如图2所示。（2）移动拼图中空白的图块，可执行的操作有上、下、左、右，其中，需要约束空白图块不能移出9宫格之外。图1拼图的初始状态图2拼图的目标状态（3）使用宽度优先搜索完成拼图任务，其搜索顺序如图所示。拼图任务的宽度优先搜索树启发式搜索策略03

启发式搜索策略又称有信息搜索策略，是指在搜索过程中，利用与问题有关的信息，引导搜索朝最有利的方向进行，从而加快搜索的速度，提高搜索效率。启发式搜索策略中涉及的重要内容有启发性信息和估价函数，常用的启发式搜索策略有A搜索和A*搜索。启发式搜索策略的主要依据是问题自身的启发性信息。

启发性信息是指可确定搜索方向，简化搜索过程，且可反映问题特性的控制性信息。在启发式搜索过程中，主要根据与问题有关的启发性信息估计各个节点的代价，从而确定每一次搜索的方向。启发性信息又是通过估价函数而作用于搜索过程的。估价函数常用于估计节点的代价，即通过充分利用启发性信息估计出经过当前节点搜索到目标节点的代价。4.3.1启发性信息和估价函数

添砖加瓦启发性信息按其作用可分为3种。（1）用于确定要扩展的下一个节点，避免盲目地扩展节点。（2）在扩展节点的过程中，用于决定生成哪些后继节点，避免盲目地生成所有可能节点。（3）用于确定应从搜索树中修剪或删除的节点，避免盲目地保留“最不具有希望”的节点。

4.3.2A搜索

全局择优搜索的基本思想是当确定下一个扩展节点时，利用估价函数计算OPEN表中每个节点的估价值，然后从OPEN表的全部节点中选择一个值最小的节点作为下一个要考察的节点。由于该搜索是在OPEN表的全部节点范围内选择下一个要考察的节点，选择范围全面，故称为全局择优搜索。全局择优搜索的搜索过程可用如图所示的算法描述。全局择优搜索算法1．全局择优搜索【例】猫捉老鼠问题，在猫去捕捉老鼠的路程中，老鼠察觉到危险，于是，老鼠从K处出发经过P处逃到O处，如左图所示。

其中，两节点间弧的数值代表猫的体力消耗值，请用全局择优搜索算法帮猫寻找捕捉路线。猫和老鼠位置表示

OPEN表和CLOSED表的状态变化

全局择优搜索树

局部择优搜索算法2．局部择优搜索

OPEN表和CLOSED表的状态变化

4.3.3A*搜索

（7）把这些后继节点都送入OPEN表中，然后按照估价函数值从小到大的顺序对OPEN表中的全部节点进行排