人工智能：5.1    搜索原理概述

5.1.1        
搜索的概念

现实世界中的大部分问题都是结构不良或非结构 
化的问题，对这样的问题一般没有成熟的现成的求解算法可供利用，而只能是利用已有的知识一步步地摸索
着前进。在这一过程中，存在着如何寻找可用知识的问题，即如何确定推理路线， 使其付出的代价尽可能的少，而问题又能得到较好的解决。另外，可能存在多条 路线都可实现对问题的求解，即一个问题可能有多个 解( 路径)
，这就存在按哪一

・87 ・

人工智能技术与方法

条路线进行求解以获得较高的运行效率的问题。像这样根据问题的实际情况不断寻找可利用的知识，从而构造一条代价较少的推理路线，使问题得到圆满解决的过程称为搜索。

在人工智能中，即使是结构性能较好，理论上有算法可 依的问题，由于问题本身的复杂性以及计算机在时间 、空间上的局限性 ，有时也需要通过搜索来求解。例如，在数字魔方问题中，要将数字
1~N ²填入 N×N
的方阵中，使其每行或每列的和相等，显然，找到这样的算法(
比如穷举法) 并不困难，但计算机却要付出惊人的时间或空间代价。

5.1.2        
搜索方法的分类

搜索问题是 人工智能的 核心理论问题之一。一般一个问题可以用好几种搜索技术解决。选择何种搜索技术对解决问题的效率影响很大，甚至关系到所求解的问题有没有解。从处理方法上来看，搜索可分为盲目搜索和启发式搜索两种 ； 从问题性质上来看，可 分为一般搜索和博弈搜索两种。

通常搜索策略的主要任务是确定如何选取规则的方式。盲目搜索，一般统称为无信息引导的搜索，它在系统搜索之前，根据事先确定好的某种固定排序，依 次调用规则或随机调用规则按预定的控制策略进行搜索，在搜索过程中获得的中间信息不用来改进控制策略。由于搜索总是按预先规定的路线进行的，没有考虑到问题本身的特性，所以这种搜索具有盲目性，效率不高，不便于复杂问题的求解。启发式搜索也称为有信息引导的搜索，它在搜索中加入了与问题有关的启发性信息，根据这些启发性信息动态地确定规则的排序，优先调用较合适的规 则， 用以指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。显
然，启发式搜索优于盲目搜索。但启发式搜索需要具有与问题本身特性有关的信息，而这并非对每一类问题都可方便地抽取出来，即启发信息的获取可能较为困难，因此盲目搜索仍不失为一种应用较多的搜索策略。到目前为止，人工智能领域中已提出许多具体的搜索方法，概括起来有如下几种。

(1)      求任一解路径的搜索策略，常见的有回溯法(Backtracking) 、爬山法(Hill

Climbing)
、宽度优先法(Breadth-first)
、深度优先法(Depth-first)
；

(2)      求最佳解路径的搜索策略，常见的有分支界限法(Branch and Bound) 、动

・88 ・

态规划法(Dynamic Programming) 、最佳图搜索法(
A^* )；

第 5 章   搜索原理

(3)      求与或关系解图的搜索法，常见的有一般与或图搜索法( AO^*
) 、极小极大

法(Minimax)
、剪枝法(Alpha
-beta Pruning) 、启发式剪枝法(Heuristic Pruning) 。

也可将其分为一般搜索( 即一人走) 和博弈搜索( 二人走，要考虑另一个人的走法)  。其中，一般搜索又可分为盲目搜索和启发式搜索。深度搜索、宽度搜索是常见的盲目搜索 ，A 算法和 A^* 算法是常见的启发式搜索 。常见的博弈搜索包括一般与或图搜索法( AO ^* ) 、极大极小搜索、a –� 剪枝法 、启发式剪枝法等。从另一个角度看，搜索策略( 控制策略) 又分为不可撤回的控制策略和试探性控制策略、回溯式和图搜索式。和图搜索式比较，回溯式策略实际上比较容易实现，而且要求 较小的存储空间 。而对一般搜索而言 ，当问题的 信息少或启发式的知识了解得少， 就要盲目搜索。

5.1.3        
状态空间、搜索空间和解路径

状态空间图是一个有向图，其节点可表示问题的各种状态( 综合数据库) ，节点之间的弧线代表一些操作( 产生式规则) ，它们可把一种状态导向另一种状态。这样建立起来的状态空间图，描述了问题所有可能出现的状态及状态和状态之间的关系( 称为规则或操作，某状态可在一可用规则的作用下成为另一状态) 。实际上只有问题空间规模较小的问题才可能做出状态空间图。在状态空间图中，从初始节点到目标节点的一条路径称为解路径。某一问题的解路径可能不止一条，有 时 需要的是任一条解路径，有时需要的是最优解路径，有时需要的是在有限时空范围内的局部最优解路径( 即满意解) ，这要视需求而定。为找到解路径而搜索的空间称为搜索空间。显然，搜索空间越小，说明搜索的代价越小，相应搜索算法的效率越高。图 5.1 给出 状态空间、 搜索空间和解路径的关系。

・89 ・

人工智能技术与方法

图 5.1 状态空间、搜索空间和解路径

5.1.4        
搜索成本

搜索成本即在搜索过程中所花费的费用。 
可以把这些费用分为以下两类。一类是规则控制费用，即为决定选取可用规则
费用。一个完全无启发信息的控制系统几乎不需要或只需要很少的控制费用，因  为选取规则是在 搜索之前事先安排好的，因 而不需要花费多少控制计算费用。相反，一个具有较多启发信息的控制系统则需要较多的控制费用，因为选取规则是在 搜索过程之中动态地决定的。启发信息越强，这种成本通常就会越高。另一类是规则应用费用，即使用规则 所花费的费用。在 一个完全无启发信息的控制系统中，通常需要较多的规则应用费用， 因为这种系统通常需要经过较多地使用规则( 搜索空间较大) 后才会找到解 。相反， 在 一个具有较多启发信息的控制系统中，则需要较少的规则应用费用，这是因为在这种系统通常能够较直接地、经过较少地使用规则( 搜索空间 较小) 后就会找到解，并且，启发信息越强，其规则应用费用越低( 搜索空间也越小) 。图 5.2 粗略地表示这两种费用及其总费用的变化趋势。人工智能系统全部计算费用是规则应
用费用和控制策略费用的总和。设计高效率的人工智能系统的一部分技巧就是如 何平衡这两部分费用。

・90 ・

第 5 章   搜索原理

启发信息量

图 5.2   搜索成本

搜索方法好的标准一般有两 个：一是搜索时间少，搜索空间小；二是解最佳。不同的问题对解的要求可能是不一样的，通常有以下三种情况。

(1)      问题有几条不同代价的解路径，需要的是其中代价最小
的那条。这种问题，可以使用后面介绍的 A^* 算法求解。

(2)      与第一种情况类似，但在试图找到最佳解路径之前，搜索过程已经超过

了可以容忍的时间或者空间范围，因此，对于这种问题，只能得到在一定时空限制下的满意解(
而不是最优解) ，并且研究满意解与理论上存在的最优解之间的关系( 比如评价这两种解的差距) 。我们不得不在最优解与时空限制条件之间作一个折中。如果有更多的时间与空间，则有机会得到更好的解，如果有足够多的或无限的时间与空间，则可以得到最优解。这类问题的例子很多，一个经典的
问题就是推销员旅行问题。若问题规模较大，则只能在可以容忍的时空范围内，指望得到一个足够好的解。