当前位置：首页 > news >正文

搜索策略的基本概念

news 来源：原创 2025/7/16 1:44:47

搜索是人工智能中的一个基本问题，是推理不可分割的一部分，它直接关系到智能系统的性能与运行效率，因而尼尔逊把它列为人工智能研究中的四个核心问题之一。在过去40多年中，人工智能界已对搜索技术开展了大量研究，取得了丰硕的成果，目前正在为提高搜索效率以及搜索复杂性理论的研究开展进一步的工作。

一、什么是搜索

（一）定义与核心目标

搜索是人工智能中通过系统地探索问题空间，寻找从初始状态到目标状态的可行路径或解决方案的过程。其核心目标是在有限的计算资源下，高效地找到满足问题约束的最优或可行解。搜索过程可视为在状态空间或与/或树中进行路径探索，通过状态转移和条件判断逐步逼近目标。

（二）分类与应用场景

1.按搜索策略分类

（1）盲目搜索（如 BFS、DFS）：不利用启发式信息，按固定顺序扩展节点，适用于小规模问题；

（2）启发式搜索（如 A*、AO*）：利用领域知识指导搜索方向，显著减少搜索空间，适用于复杂问题。

显然，启发式搜索优于盲目搜索。但由于启发式搜索需要具有与问题本身特性有关的信息，而这并非对每一类问题都可方便地抽取出来，因此盲目搜索仍不失为一种应用较多的搜索策略。

2.按问题表示分类

（1）状态空间搜索：适用于可表示为状态转移的问题（如八数码、路径规划）；

（2）与/或树搜索：适用于可分解为子问题的问题（如数学证明、任务调度）。

二、状态空间表示法

状态空间表示法是用“状态”和“算符”来表示问题的一种方法。其中，“状态”用以描述问题求解过程中不同时刻的状况；“算符”表示对状态的操作，算符的每一次使用就使问题由一种状态变换为另一种状态。当到达目标状态时，由初始状态到目标状态所用算符的序列就是问题的一个解。

（一）基本思想与定义

1. 核心思想

将问题抽象为状态空间图，其中节点表示问题状态，边表示状态转移的操作（算符）。通过搜索图中的路径，找到从初始状态到目标状态的解。

2. 形式化定义

状态空间是一个三元组 (S, F, G)，其中：

S：初始状态集合；

F：算符集合，定义状态转移规则；

G：目标状态集合。

（二）表示形式与实现过程

1. 状态（State）

定义：描述问题在某一时刻的完整信息，通常用向量或数据结构表示。当给每一个分量以确定的值时，就得到了一个具体的状态。

示例：八数码问题的状态可表示为 (x_0, x_1, ..., x_8)，其中 x_i 为方格内的数字（0表示空格）。

2. 算符（Operator）

引起状态中某些分量发生变化，从而使问题由一个状态变为另一个状态的操作称为算符。在产生式系统中，每一条产生式规则就是一个算符。

定义：将一个状态转换为另一个状态的操作，描述状态间的关系。

示例：八数码问题的算符包括空格的上、下、左、右移动，每个移动生成一个新状态。

3. 状态空间（State Space）

由问题的全部状态及一切可用算符所构成的集合称为问题的状态空间，一般用一个三元组表示：(S,F,G)，其中S是问题的所有初始状态构成的集合；F是算符的集合；G是目标状态的集合。

定义：所有可能状态及其转移关系的集合，可用有向图表示。

显式与隐式状态空间：

（1）显式：预先构建所有状态和转移（适用于小规模问题）；

（2）隐式：按需动态生成状态（如八数码问题，状态数为 9! = 362880，无法显式存储）。

（三）算法描述

1. 广度优先搜索（BFS）

步骤：

（1）将初始状态加入队列；

（2）取出队列首节点，若为目标状态则返回路径；

（3）生成所有合法后继状态，未访问过的加入队列；

（4）重复直至找到目标或队列为空。

复杂度：时间 O(b^d)，空间 O(b^d)，其中 b 为分支因子，d 为解的深度。

2. 深度优先搜索（DFS）

步骤：

（1）将初始状态压入栈；

（2）弹出栈顶节点，若为目标状态则返回路径；

（3）生成所有合法后继状态，未访问过的压入栈；

（4）重复直至找到目标或栈为空。

复杂度：时间 O(b^m)，空间 O(m)，其中 m 为搜索深度。

**3. 启发式搜索（A * 算法）**

估价函数：f(n) = g(n) + h(n)，其中 g(n) 为当前路径代价，h(n) 为启发式估计值（如曼哈顿距离）。

步骤：

（1）将初始状态加入优先队列（按 f(n) 排序）；

（2）取出队列首节点，若为目标状态则返回路径；

（3）生成所有合法后继状态，计算 f(n) 并更新队列；

（4）重复直至找到目标或队列为空。

性质：若 h(n) 是可采纳的（不高估实际代价），则 A *算法是最优的210。

（四）具体示例：八数码问题

1. 问题描述

初始状态：

目标状态：

2. 状态空间生成

状态表示：使用9维向量 (2,8,3,1,6,4,7,0,5) 表示初始状态。

算符：空格的4种移动方向，生成新状态。

3. BFS 搜索流程

（1）初始队列：[S_0]

（2）扩展 S_0，生成 4 个后继状态（空格上、下、左、右移动）；

（3）检查每个后继是否为 S_g，若否，加入队列；

（4）重复直至找到目标状态，记录路径。

**4. A * 算法优化**

启发式函数：曼哈顿距离，计算每个数字到目标位置的横向和纵向距离之和。

效率提升：通过优先扩展 f(n) 最小的节点，减少无效搜索。

（五）具体示例：二阶梵塔问题

设有三根钢针，在1号钢针上穿有A，B两个金片，A小于B，A位于B的上面。要求把这两个金片全部移到另一根钢针上，而且规定每次只能移动一片，任何时刻都不能使B位于A的上面。

设用S_k=（S_k0，S_k1)表示问题的状态，S_k0表示金片A所在的钢针号，S_k1表示金片B所在的钢针号，全部可能的状态有九种：

S0 = (1, 1), S1 = (1, 2), S2 = (1,3)

S3 = (2, 1), S4 = (2, 2), S5 = (2,3)

S6 = (3, 1), S7 = (3, 2), S8 = (3,3)

如图1所示。

图1 二阶梵塔的状态

问题的初始状态集合为S={S0}，目标状态集合为G={S4, S8}。算符分别用A(i, j)及B(i, j)表示。A(i, j)表示把金片A从第i号针移到第j号针上；B(i, j)表示把金片B从第i号针移到第j号针上。共有12个算符，它们分别是：

A(1,2)，A(1,3)，A(2,1)，A(2,3)，A(3,1)，A(3,2)

B(1,2)，B(1,3)，B(2,1)，B(2,3)，B(3,1)，B(3,2)

根据9种可能的状态和12种算符，可构成二阶梵塔问题的状态空间图，如图2所示。

图2 二阶梵塔的状态空间图

在图2所示的状态空间图中，从初始节点(1, 1)到目标节点(2, 2)及(3, 3)的任何一条通路都是问题的一个解，其中最短的路径长度是3,它由3个算符组成，例如A(1,3)，B(1,2)，A(3,2)。由此例可以看出：

（1）用状态空间方法表示问题时，首先必须定义状态的描述形式，通过使用这种描述形式可把问题的一切状态都表示出来。其次，还要定义一组算符，通过使用算符可把问题由一种状态转变为另一种状态。

（2）问题的求解过程是一个不断把算符作用于状态的过程。如果在使用某个算符后得到的新状态是目标状态，就得到了问题的一个解。这个解是从初始状态到目标状态所用算符构成的序列。

（3）算符的一次使用，就使问题由一种状态转变为另一种状态。可能有多个算符序列都可使问题从初始状态变到目标状态，这就得到了多个解。其中有的使用算符较少，有的较多，我们把使用算符最少的解称为最优解。例如在上例中，使用3个算符的解是最优解。这只是从解中算符的个数来评价解的优劣，今后将会看到评价解的优劣不仅要看使用算符的数量，还要看使用算符时所付出的代价，只有总代价最小的解才是最优解。

（4）对任何一个状态，可使用的算符可能不止一个，这样由一个状态所生成的后继状态就可能有多个。当对这些后继状态使用算符生成更进一步的状态时，首先应对哪一个状态进行操作呢？这取决于搜索策略，不同搜索策略的操作顺序是不相同的，这正是本问要讨论的问题。