人工智能 第三版 第三章 知情搜索

知情搜索（informed search，也称有信息搜索）：利用启发式方法，通过限定搜索的深度或宽度来缩小问题空间。

启发式方法

启发式方法的目的是大幅度减少到达目标状态所要考虑的节点数目，它们非常适合解决那些组合复杂度（combinatorial complexity）快速增长的问题。通过知识、信息、规则、见解、类比和简化，再加上一系列其他的技术，启发式方法旨在减少必须检查的对象数目。好的启发式方法不能保证一定获得解，但是它们经常有助于人们找到到达解的路径。

找到任一解

爬山法

找到一个比当前节点更好的节点就前进

最陡爬山法

从更好的节点中选择最好的节点前进

最佳优先搜索

最佳优先搜索（best-first search）是一个为到达目标而考虑探索哪些节点以及探索多少个节点的智能搜索算法。

它维护着与深度优先搜索及广度优先搜索一样的开放节点及封闭节点列表。开放节点是搜索边缘（fringe）上的节点，后面可能会进一步探索到。而封闭节点是那些不再探索的节点，它们将构成解的基础。在开放列表中，节点按照它们接近目标状态的启发式估计值大小进行排列。因此，每次迭代搜索时，都会考虑开放列表中最有希望的节点，从而将最佳状态放在开放列表的前端。重复状态（例如，可以通过多条路径到达的状态，但是具有不同的开销）不会被保留。相反，开销最低、最有希望以及在启发式方法下最接近重复节点的目标状态的节点则被保留。

注意，最佳优先搜索的效率取决于所使用的启发式度量方法的有效性。

集束搜索

在搜索树中的每一层只扩展最好的W个节点，如同形成一种薄的、聚焦的“光束”

• 在集束搜索中，探索通过搜索树逐层扩展，但是每层只有最好的W个节点才会得到扩展。W被称为集束宽度（beam width）。

• 通过将搜索树深度的指数级内存开销降低到线性开销，集束搜索是对广度优先搜索的一种尝试改进方法

• 过程：每一层切片（宽度为W）的数目被限制为1。当集束搜索扩展一层时，生成当前层状态的所有后继节点，将它们按照启发值递增的顺序（从左到右）排序，并将它们切分为多个切片（每个切片最多包含W个状态），然后只存储第一个切片，并扩展节点。当生成目标状态或内存不足（如前所述）时，集束搜索终止

搜索算法的其他指标

经过节点n到G的路径的精确开销f (n)= g(n) + h*(n)

对于所有的节点n，必须有估计值h(n)≤精确值h*(n)。在这种情况下，h(n)被称为可接受的启发值（admissible heuristic）

找到最优解

分支定界法

这种算法在文献中通常被称为统一开销搜索或统一代价搜索（uniform-cost search）。该算法会按照递增的开销—更精确地说，是按照非递减的开销来寻找路径。

这里用的路径开销估计方法很简单：f (n) = g(n)，并不采用基于剩余距离的启发式搜索。

也可以采用一种等价的说法，即h(n)的估计值处处为0。这种方法与广度优先搜索的相似性显而易见，即首先访问最靠近起始节点的节点。

BFS与分支定界法之间的区别是，BFS努力找到通往目标的某条路径，而分支定界法努力找到一条最优路径。

高级搜索算法

约束满足搜素

在对更大或更复杂的问题进行求解时，可以识别出其中更小的可处理的子问题，这些子问题通过较少的步骤就可以解决。

与或树

这里的目标是，通过应用以下规则，在给定的树中找到解的路径。如果满足以下条件，那么节点是可解的。（1）它是一个终止节点（一个基元问题）。

（2）它是一个非终止节点，并且其后继节点都是可解的与（AND）节点。或者

（3）它是一个非终止节点，后继节点是或（OR）节点，在这些或节点中，至少有一个可解。

类似地，在下列条件下，节点是不可解的。

（1）它是一个没有后继节点的非终止节点（没有运算符可应用的非基元问题）。

（2）它是一个非终止节点，后继节点是与（AND）节点，在这些与节点中，至少有一个不可解。或者

（3）它是一个非终止节点，后继节点是或（OR）节点，并且这些或节点都是不可解的。

双向搜索

双向搜索（bidirectional search）的想法是在向前搜索目标状态的同时，从已知的目标状态向后搜索到起始状态，以找到解的路径。