在状态空间图中寻找目标或路径的基本方法就是图搜索，指从初始节点出发，沿着与之相连的边试探着前进，寻找目标节点的过程，也可以反向进行。

图搜索分为盲目搜索和启发式搜索两种。盲目搜索也称无信息搜索，是指在搜索过程中只按预定的控制策略进行搜索，而在搜索过程中获得的中间信息不被用来改进控制策略。由于搜索总是按预先规定的路线进行，没有考虑到问题本身的特性，所以这种搜索具有盲目性，效率不高，不便于复杂问题的求解。启发式搜索又称有信息搜索，是指在搜索中加入了与问题有关的启发性信息，用以指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。显然，启发式搜索优于盲目搜索。但由于启发式搜索需要具有与问题本身特性有关的信息，而这并非对每一类问题都可方便地抽取出来，因此盲目搜索仍然是一种应用较广泛的搜索策略。

1.数据驱动搜索模式

数据驱动搜索也称正向推理，搜索的过程是应用规则从给定条件产生新条件，再用规则从新条件产生更多的新条件，搜索过程一直持续到有一条满足目标要求的路径产生为止。

2.目标驱动搜索模式

目标驱动也称逆向推理或反向推理，推理着眼于目标，寻找产生目标的规则，通过反向连续的规则和子目标进行反向推理，直至找到问题给出的条件为止。

3.数据驱动和目标驱动相结合的双向搜索模式

双向搜索如图2-6所示。

图2-6　双向搜索

4.图搜索的实现

无论是哪种搜索模式，其求解问题都要在状态空间图中找到从初始状态到目标状态的路径。路径上的序列对应于解题的先后步骤，求解问题时必须尝试多条路径直到找到目标为止。

1）带回溯的搜索

若当前状态S未达到目标的要求，就对它的第一个子状态Schild1递归调用回溯过程；如果在以Schild1为根的子图中未能到目标，就对它的兄弟Schild2调用此过程；按此递归调用，直到结束为止。

注：递归应规定界线。

用该方法进行搜索时，用三张表来保存状态空间的节点。

（1）SL状态表：列出当前路径上的状态。如果找到了目标，SL就是解题路径上状态的有序集。

（2）NSL新状态表：包括了等待评估的节点，其后裔节点还未被扩展。

（3）DE不可解端点集：列出了找不到解题路径的状态。如果在搜索中再遇到它们，就会因检测到它们是DE中的成分而立刻将之排除。

算法描述：

算法的执行过程如图2-7所示。

backtrack是状态空间搜索的一个基本算法，以后我们要讲的深度优先、广度优先、最好优先等搜索，都有回溯的思想。

算法中几个表的作用是：

（1）用来处理状态表（NSL）使算法能返回（回溯）到其中任一状态。

（2）有一张“坏”状态表（DE）避免算法重新搜索无解的路径。

（3）有当前状态表（SL），当满足目标时可以将它〈作为结果〉返回。

（4）为避免陷入死循环，必须显式地对新状态进行检查，看它是否在三张表中。

2）广度优先搜索

广度优先搜索（Breadth First Search）又称宽度优先搜索，是一种盲目搜索策略。其基本思想是：从初始节点开始，逐层对节点进行依次扩展，并考察它是否为目标节点，在对下一层节点进行扩展（或搜索）之前，必须完成对当前层的所有节点的扩展（或搜索）。

广度优先搜索算法描述如图2-8所示。

其中Open表是一个队列即先进先出的结构，状态从右边进入，从左边移出。Closed表是backtrack算法中的SL和DE表的合并，即Closed=SL∪DE。

其对问题状态空间节点的搜索过程如图2-9所示。

图2-9中广度优先搜索算法执行过程的搜索轨迹为：

图2-7　backtrack算法搜索

图2-8　广度优先搜索算法流程

图2-9　广度优先搜索策略对问题状态空间搜索过程

上图用backtrack搜索算法，其搜索轨迹为：

由上可知，广度优先可以确保找到从开始到目标的最短路径。

3）深度优先搜索

深度优先搜索（Depth First Search）也是一种盲目搜索策略，其基本思想是：首先扩展最新产生的（最深的）节点，即从初始节点开始，在其后继节点中选择第一个节点，对其进行考察，若它不是目标节点，则对该节点进行扩展，并从它的后继节点中选择第一个节点进行考察。依次类推，一直搜索下去，当到达某个既非目标节点又无法继续扩展的节点（到达叶子节点或受到深度限制）时，才从当前节点返回到上一级节点，沿另一方向又继续前进。这种方法的搜索树是从树根开始一枝一枝逐渐形成的。

深度优先搜索算法的流程如图2-10所示。

图2-10　深度优先搜索算法流程

其中Open表是一个后进先出结构。

其搜索的轨迹如下：

其搜索过程如图2-11所示。

图2-11　深度优先搜索策略对问题状态空间搜索

注意：深度优先搜索并不能保证第一次遇到某个状态时的路径，是到这个状态的最短路径。

广度优先与深度优先搜索算法的比较如下。

广度优先：

（1）由于广度优先搜索方法总是在检查完n层的节点之后才转向n+1层的检查，因此，它总是能找到最短路径的解。

（2）对简单问题，该算法能找到最优解，对复杂问题找不到解。因为用Open表中状态数目表示的广度优先搜索对空间的利用率是当前路径长度的指数函数，若每个状态平均有B个子状态，在给定层上状态的数目就是B乘以上一层的状态数，因此第n层有Bn个状态。广度优先搜索在刚开始搜索第n层时要将其全放在Open表中，如果解题路径长的话，这个数目大得让程序无法工作。

深度优先：

（1）深度优先搜索可尽快进入底层，但会在深处迷失方向，找不到目标的最短路径或陷入一个不通往目标的无限长的路径中。

（2）深度优先在搜索有大量分枝的图时会有相当高的效率，因为它不需要把某一层上所有节点记入Open表中。

（3）深度优先搜索耗费的空间量是路径长度值的线性函数，Open在每一层只保留一个状态的子状态，如果图中每个状态平均有B个子状态，则搜索到图中第n层时要求B×n个状态的空间。

5.有界深度优先搜索

广度优先和深度优先是两种最基本的穷举搜索方法，在此基础上，根据需要再加上一定的限制条件，便可派生出许多特殊的搜索方法，例如有界深度优先搜索。有界深度优先搜索就是给出了搜索树深度限制，当从初始节点出发沿某一分枝扩展到一限定深度时，就不能再继续向下扩展，而只能改变方向继续搜索。节点x的深度（即其位于搜索树的层数）通常用d（x）表示，则有界深度优先搜索算法如下：

（1）把S0放入Open表中，置S0的深度d（S0）=0。

（2）若Open表为空，则失败，退出。

（3）取Open表中前面第一个节点N，放入Closed表中。

（4）若目标节点Sg=N，则成功，结束。

（5）若N的深度d（N）=dm（深度限制值），或者若N无子节点，则转步骤2。

（6）扩展N，将其所有子节点Ni配上指向N的返回指针后依次放入Open表中前部，置d（Ni）=d（N）+1，转步骤2。

设置深度界限的目的是：一旦搜索路径进入某一层时，深度界限便强迫该路径上的搜索失败，并形成搜索空间中该层之上的一块区域。

上述有界深度优先搜索算法是在DFS中规定搜索深度进行搜索。它先执行深度界限为1的深度优先搜索，如果未找到目标，再执行深度为2的深度优先搜索，如此不停地在每次重复时将深度加1。每次重复时，算法都执行以当前深度为界限的完全的深度优先搜索。每次重复之间并不传递任何与状态空间有关的信息。由于算法是按一层层的方式搜索状态空间的，所以它一定会找到通向目标的最短路径。

6.基于递归的搜索

递归在数学中指一个递归定义中使用了它自己的定义。

在计算机科学中，递归被用来定义和分析数据结构和过程。

一个递归过程包括：

（1）过程调用自身重复一串动作的递归步骤。

（2）防止过程无穷递归的终止条件。

［例］　测试一元素是否是表成员的过程可递归定义如下：

深度优先递归搜索算法：

算法使用了两个全局变量Closed和Open来维护状态表。

7.启发式搜索

前面讲的穷举搜索法，从理论上讲似乎可以解决任何状态空间的搜索问题，但实践表明，穷举搜索只能解决一些状态空间很小的简单问题，而对于那些状态空间较大的问题，穷举搜索就不能胜任了。因为大空间问题往往会导致“组合爆炸”。

有没有信息不完全的前提下得到相同的结论的可能呢？

众所周知，在智能活动中，使用最多的方法不是完备性方法，而是不一定完备的启发式方法。其原因是：

（1）大多数智能系统不知道与实际问题有关的全部信息，因此，在具体求解问题时只能借助部分信息加上经验去处理。

（2）有些智能行为无法用现有的工具推导表示，只能用经验关系表示。

由此可见，无论在理论方面还是在应用方面都需要启发式方法。(www.daowen.com)

“启发”（heuristic）包括发现、发明规则及其研究方法。

启发式搜索就是利用启发性信息进行制导的搜索。启发性信息就是有利于尽快找到问题的解的信息。按其用途划分，启发性信息一般可分为以下三类：

①用于扩展节点的选择，即用于决定先扩展哪一个节点，以免盲目扩展。

②用于生成节点的选择，即用于决定生成哪些后续节点，以免盲目地生成过多的无用节点。

③用于删除节点的选择，即用于决定删除哪些无用节点，以免造成进一步的时空浪费。

在状态空间搜索中，启发式被定义成一系列规则，它从状态空间中选择最有希望到达问题解的路径。

在人工智能问题求解领域研究启发式策略是十分必要的，可以借助启发式搜索策略帮助我们求解问题。因为：

①在问题求解中有不确定性问题，如医学中的一些基本问题。

②在问题求解中有模糊性等问题，如视觉问题。

③所求解问题可能有确定解，但它有“组合爆炸”等问题存在，最终还是达不到问题求解的目的。

④在问题求解中有定性描述过程存在，但对此类问题只能借助经验给予定量帮助描述。

显然，利用启发式搜索策略的优势在于：

①可以帮助我们解决问题求解过程中存在的不确定性、模糊性。

②可以降低问题求解的复杂性。

③可以帮助我们简化问题。

启发式搜索由启发式方法和启发式搜索算法两部分构成。利用启发式搜索可能得到一个次佳解，也可能一无所获。这也是启发式搜索固有的局限性。

启发式搜索的估价函数确定方法：

设有初始状态q，经过n次变换后得到目标状态p（见图2-12）。

图2-12　问题状态变化

在上述问题中，｛qq1q2…qn－1，p｝序列和｛r1r2r3…rn｝是成一一对应关系的。

在启发式搜索中，通常用所谓启发函数来表示启发性信息。启发函数是用来估计搜索树上节点n与目标节点Sg接近程度的一种函数，通常记为h（n）。

在问题求解的搜索图中，从节点与节点之间的关系来看有过去节点、当前节点、将来节点三种类型，如图2-13所示。

图2-13　三种节点之间的关系

把这三种类型节点的关系用一个评估函数表示为

式中：g（n）表示从初始节点到当前节点的代价；h（n）表示从当前节点到目标节点最佳路径的估计代价。

在f（n）=g（n）+h（n）中，若有g（n）≫h（n），则有

式（2）可以保证f（n）的完备性，但搜索效率较差；

式（3）有利于搜索效率的提高。

图2-14为搜索过程中付出的代价关系。

图2-14　搜索过程中付出的代价关系

广度优先：

深度优先：

有界深度：

在式（1）中：当g（n）≫h（n）时，

当h（n）＞g（n）时，

例：利用启发式搜索求解下列九宫问题（见图2-15）。

图2-15　九宫问题

解：评估函数f（n）=g（n）+h（n），其中h（n）表示格子中的数字和目标数字错位个数之和，如图2-15中初始状态的错位个数之和是h（1）=4。在搜索过程中，每次选择最有希望达到目标的状态（错位个数之和最小的节点）来扩展。求解过程的状态空间如图2-16所示。

图2-16　九宫问题的启发式求解

8.启发式搜索算法

1）局部优先搜索法

局部优先搜索法也称瞎子爬山法，只考虑当前节点与目标节点之间的关系，即启发式估价函数为

如图2-17所示，瞎子爬山法只找到局部的最优解，不一定能找到全局最优解。

在图中，D＞C＞B＞E＞A

若从1出发，爬到A停止；

若从2出发，爬到B停止；

若从3出发，爬到C停止；

若从4出发，爬到D停止；

若从5出发，爬到E停止；

若首先经过4，则可得最优解。

［例］　用瞎子爬山法求下列九宫问题（见图2-18）。

图2-17　瞎子爬山

图2-18　九宫问题

这时f（n）=h（n），其中h（n）表示格子中的数字和目标数字错位个数之和。如初始状态的错位数是h（1）=4。

其搜索过程的状态空间如图2-19所示。

2）最好优先搜索法

（1）最好优先搜索法原理：最好优先搜索法也使用两张表来记录节点信息，在Open表中保留所有已生成而未考察的节点；在Closed表中记录已访问过的节点。算法中有一步是根据某些启发信息，按节点距离目标状态的长度大小重排Open表中的节点，这样，循环中的每一步只考虑Open表中状态最好的节点，这就是最好优先搜索算法，又称有序搜索法，即：

（2）最好优先搜索算法描述：

图2-19　局部优先搜索法求解九宫问题

［例］　层次状态空间的最好优先搜索（见图2-20）。

图2-20　层次空间最好优先搜索算法搜索

（3）分析：最好优先搜索算法总是从Open表中选取最“好”的状态进行扩展。但是，由于启发信息有时可能出错，故算法并不丢弃其他的状态而把它们保留在Open表中。当某一个启发信息将搜索导向错误路径时，算法可以从Open表中检索先前产生的“次最好”状态，并且考虑方向转向空间的另一部分。

图2-21中以包围的区域出错，则返回到未包围的区域。

（4）小结：f（n）=g（n）+h（n）中，g（n）保证了宽度优先搜索的性质，h（n）保证了有最好的路径。因此，最好优先搜索方法为我们提供了启发式搜索的一般原则，总结起来有：

根据产生式规则和一些其他的操作，生成当前考察节点的子状态。

检查每个子状态以前是否已经考察过（已在Open表或Closed表中），以防止循环。

每个状态都以f（n）值为依据进行搜索。

Open表中的状态按f（n）值排序。

通过设计Open表和Closed表的存储方式，可以提高算法的效率。

图2-21　启发式搜索空间

上面介绍了多种搜索方法，图搜索算法简单地说就是，每次从Open表中取出第一个节点进行扩展，生成的新节点放到Open表中，然后按照某种原则对Open表进行排序。不同的排序原则构成了不同的图搜索算法。值得注意的是，算法成功结束的判断方法，是当从Open表中取出一个节点后，再判断该节点是否是目标节点，而不是在扩展节点/生成新节点时判断。这一点一定要注意，这是构成某些最优算法的关键所在。