上课日期：第三周 2020.9.27 3-4节（补第五周周三的课），西校区工程中心204

出勤统计：应到41/实到41/迟到人0

在上一次的讲课中，我们通过介绍几种常见的“盲目搜索”策略，已经了解了智能体在“树搜索”和“图搜索”过程中，如何保持理性。

本讲我们重点介绍“知情搜索”中比较经典的搜索策略。

知情搜素（Informed search）又称为启发式搜素（Heuristic search），这类算法在搜素策略中运用了若干与问题形式化（Problem formulation）本身之外的、被认可的知识（Knowledge）或经验（Experience），从而加速算法计算和目标收敛。

我们要介绍的一个知情搜索策略是，贪婪最佳优先搜索。它在搜索策略上，总是试图扩展离目标最近的结点，理由是这样可能可以很快找到解。因此，它将启发式函数，完全取代了节点的合理性评价函数。

回忆我们之前介绍过的“罗马尼亚导航”智能体设计问题，贪婪最佳优先搜索将当前节点到目标节点的直线距离，作为启发信息，从而服务在开集中选择扩展节点的决策。

作为搜索树的根节点，也就是状态空间图的初始状态，Arad离目标节点的直线距离为366km；当Arad进入探索集中后，开集中有三个节点，分别为Sibiu，Timisoara和Zerind。贪婪最佳优先搜索会首先Sibiu，应为它离目标节点的直线距离最近。

值得同学们注意的是，知情搜索中的贪心算法与盲目搜索策略中的贪心算法（如Dijistra）不同。如果说盲目搜索中的贪心算法是“边走边向后看，生怕上当受骗”，知情搜索中的贪心算法就是“边走边向前看、紧盯目标不放松”。

遗憾的是，虽然贪心优先算法的搜索速度快，但是它的完备性和最优性均得不到保障。

接下来，我们第二个知情搜索策略，即A*算法。

为此解决贪心优先算法存在的弊端，人工智能科学家提出了A*算法。A*算法也属于最佳优先搜索策略，但它的节点合理性评价函数综合考虑了距离目标的启发式信息，也考虑了距离初始阶段的实际代价信息。因此，它兼具一致代价搜索算法的“小心翼翼”特点，也具备贪心优先算法的“雄心勃勃”特点。

上面这张图清晰地显示了A*算法的合理性。

最后，我们来分析A*算法的最优性。

A*算法的完备性没有问题，但是它的最优性由它使用的启发函数的性质所决定。对于树搜索（tree-search）问题，启发函数必须乐观且实事求是，这种特性我们称之为“可达性(admissibility)”，也就是说，在任意状态下，智能体对到达目标状态的估计代价（estimated cost）不超过实际所需代价（true cost）。

仍然以“罗马尼亚导航”智能体设计问题为例，采用直线距离作为任何城市到目的城市的估计距离是合适的，因为两点之间直线最短,所以用直线距离肯定不会高估。因此，在树搜索问题中，A*算法能够确保最优性。

下面，我们来看一个反例。

S为起始状态，G为目标状态。现在问题的最优解为S-A-G，但是A节点到目标节点的启发式信息不满足可达性，导致智能体在搜索的第二步，在开集中选择了G，从而获得了次优解。

如果，我们需要在图搜索中使用A*算法，我们需要引入一致性约束条件。它略强于在树搜索中使用的可达性条件。启发式函数式是一致的，是指如果对于每个结点n和通过任一行动a生成的n的每个后继结点n'，从结点n到达目标的估计代价，不大于从n到n'的单步代价与从n'到达目标的估计代价之和。

如上图所示，一致性约束条件是一个非常有趣的性质，它满足一般的三角不等式，保证了三角形中任何一条边的长度不大于另两条边之和。这里的三角形是由n，n'和离n最近的目标结点G构成的。

我们看上面这张图，为了满足一致性约束条件，你能告诉我节点A的启发式函数的值应该是多少吗？

如上图所示，满足一致性约束条件的A*算法还有一个有趣的性质，A*算法的搜索路径存在明显的等高线，而且等高线呈椭圆形，长轴的端点分别接近为起始状态和目标状态。

在结束本讲之前，同学们需要知道，知情搜索算法的性能取决于启发式函数的质量。好的启发式函数有时可以通过将问题进行理想化处理，也就是松弛化问题的定义，或者通过从经验中学习得到。

This course mainly discusses about informed search or heuristic search, which may have access to a heuristic function h(n) that estimates the cost of a solution from a given state. We introduced two algorithms, including greedy-first search and A* search.

First, greedy best-first search expands nodes with minimal heuristic information. It is not optimal but is often efficient.

Second, A∗ search expands nodes with minimal evaluation information. A∗ is complete and optimal, provided that h(n) is admissible (for TREE-SEARCH) or consistent (for GRAPH-SEARCH). The space complexity of A∗ is still prohibitive.