对解的搜索

3.3 对解的搜索

在对一些问题形式化之后，我们现在开始考虑如何对它们求解。这是通过在状态空间中的搜索完成的。本章讨论的搜索技术使用显式的搜索树，搜索树是由初始状态和后继函数共同产生的，同时也定义了状态空间。一般来说，当同一个状态可以从多条路径达到时，我们会得到一个搜索图而不是搜索树。我们把这个重要因素放在后面的第3.5节考虑。

图 3.6 中显示了为寻找从 Arad 到 Bucharest 的路径对搜索树进行的某些扩展。搜索树的根节点是一个对应于初始状态 In(Arad)的搜索节点。第一步是检测该节点是否为目标状态。显然它不是目标状态，但是检测是很重要的，因为这样的一步可以解决像“从 Arad 出发，到达 Arad”这样有欺骗性的问题。因为这不是目标状态，我们需要考虑一些其它状态。这是通过扩展当前状态完成的；就是说，把后继函数应用于当前状态，因而生成一个新的状态集。在这种情况下，我们得到三个新的状态：In(Sibiu)，In(Timisoara)和In(Zerind)。现在我们必须从这三种可能性中选择其一继续考虑。

图3.6 寻找从Arad到Bucharest的路径中的部分搜索树。已被扩展过的节点用阴影表示；已经生成但是还未扩展的节点用粗实轮廓线表示；尚未生成的节点用浅色虚线表示

这是搜索的基本做法——先追随一个选择，把其它的暂且放在一边，等到以后万一发现第一个选择不能通向问题的解的时候再考虑。假设我们首先选择 Sibiu。我们检查它是否为目标状态（不是），然后扩展它得到四个状态：In(Arad)，In(Fagaras)，In(Oradea)和In(RimnicuVilcea)。之后我们可以选择这四个状态之一，或者返回并选择Timisoara或Zerind。我们继续选择、测试并且扩展，直到找到解或者再也没有可扩展的状态。对要被扩展的状态的选择是由搜索策略决定的。在图 3.7 中给出了一般的树搜索算法的非形式化描述。

图3.7 一般的生成搜索树算法的非形式化描述

区分清楚状态空间和搜索树是很重要的。对于寻径问题，在状态空间中只有20个状态，每个状态对应一个城市。但是在这个状态空间中有无数条路径，所以搜索树有无穷个节点。例如，Arad-Sibiu， Arad-Sibiu-Arad，Arad-Sibiu-Arad-Sibiu 是一个无限的路径序列中的前三条。（显然，一个好的算法应该避免追随这样的重复性路径；第3.5节将说明如何避免。）

节点的表示有很多方式，不过我们假设节点是一个包含五个元素的数据结构：

• STATE：状态空间中与该节点相对应的状态；

• PARENT-NODE：搜索树中产生该节点的节点（即父节点）；

• ACTION：由父节点产生该节点所用的行动；

• PATH-COST：从初始状态到达该节点的路径消耗，传统上记为g(n)，路径由父指针表示；

• DEPTH：从初始状态到达该节点所经路径上的步数。记住节点和状态的差别是很重要的。节点是用来表示搜索树的记录型数据结构。状态对应于世界的格局。因此，节点处于由 PARENT-NODE 指针所定义的特定的路径上，而状态则不是。此外，如果一个状态可以通过两条不同的路径生成，两个不同的节点就可能包含同一个世界状态。图 3.8 描述了节点的数据结构。

图3.8 节点是构造搜索树的数据结构。每个节点都具有父节点、状态和各种记录域。图中箭头由子节点指向父节点

我们同时也需要表示已经生成出来但还未被扩展的节点集合——这个集合被称为边缘。边缘的每个元素都是叶节点，即在搜索树中没有后继的节点。在图 3.6 中，每棵搜索树的边缘由粗轮廓线表示的节点组成。边缘最简单的表示就是一个节点集合。搜索策略则是从这个集合中选择下一个被扩展的节点的函数。虽然这种表示方法在概念上很直接，但计算代价可能是昂贵的，因为策略函数不得不考虑集合中的每一个元素才能选择出最好的一个进行扩展。因此，我们假设这个节点集合用一个队列来实现。下面是对于队列的一些操作：

• MAKE-QUEUE(element,…) 用给定的元素创建一个队列。

• EMPTY?(queue) 当且仅当队列中没有元素时返回为真。

• FIRST(queue) 返回队列中的第一个元素。

• REMOVE-FIRST(queue) 返回FIRST(queue)并将它从队列中删除。

• INSERT(element, queue) 在队列中插入一个元素并返回结果队列。（我们将看到在不同类型的队列中插入新元素的顺序是不同的。）

• INSERT-ALL(elements,queue) 在队列中插入一个元素集合并返回结果队列。

通过以上定义，我们可以写一个更加形式化的一般的树搜索算法，如图3.9所示。

图3.9 一般的树搜索算法。（注意fringe参数开始必须是个空的队列，队列的类型也将影响搜索的顺序。）函数SOLUTION返回通过从父指针回溯到根节点而获得的行动序列

3.3.1 度量问题求解的性能

问题求解算法的输出不是failure（失败）就是解。（一些算法可能陷入无限循环而永远不会返回输出。）我们将通过以下四种途径来评价一个算法的性能：

完备性：当问题有解时，这个算法是否能保证找到一个解？

最优性：这个搜索策略是否能找到最优解？最优解的定义见第3.1.1节。

时间复杂度：找到一个解需要花费多长时间？

空间复杂度：在执行搜索的过程中需要多少内存？

时间和空间的复杂度往往要与问题难度的某种度量一起考虑。在理论计算机科学中，一个典型的度量是状态空间图的大小。因为状态空间图被视为要输入到搜索程序的显式的数据结构。（罗马尼亚地图就是一个例子。）在AI领域，状态空间图是由初始状态和后继函数隐含地表示的，经常是无限的，它的复杂度根据下列三个值来表达：b，分支因子，或者说任何节点的后继的最大个数；d，最浅的目标节点的深度；m，状态空间中任何路径的最大长度。

时间复杂度常常根据搜索过程中产生的节点数目来度量[5]，而空间复杂度则根据在内存中储存的最大节点数来度量。

在评价一个搜索算法的有效性的时候，我们可以只考虑搜索耗散——它通常取决于时间复杂度，不过也可以包括内存的使用情况——或者我们可以使用总耗散，它把找到的解的搜索耗散和路径耗散结合起来。对于寻找从Arad到Bucharest的路径的问题，搜索耗散是搜索花费的时间，而解耗散是路径总长度的公里数。因此，要计算总消耗，我们不得不把公里数和毫秒数相加。在这两者之间没有“官方兑换率”，但是在这种情况下利用对汽车平均速度的估计把公里数转换为毫秒数（因为该智能体关心的是时间）是合理的。这使得智能体能够找到一个最优的折中点，从而使寻找最短路径的进一步计算成为无用功。更一般的不同利益之间的折中问题将在第十六章中讨论。