第二部分 表达和推理
第3章 状态和搜索
你看到过海岸上的螃蟹在寻找大西洋的过程中一直向后爬行，最终消失吗？人们也是同样的思考方式。
——H.L.Mencken (1880—1956)
前面一章讨论了Agent是如何理解和动作的，但是没有讲到它们的目标是如何影响动作的。一个Agent可以根据既定的目标集有规划的去动作，但是如果不能适应变化的目标，这样的Agent就是非智能的。或者，Agent能够根据自身能力和既定目标去推理，从而决定应该做什么。这一章介绍将Agent决定做什么的问题描述为在一个图中搜索发现一条路径的问题，它还给出了计算机解决此类问题的很多方法。就像Mencken 在上面说的，尽管不都能达成既定目标，人们还是想利用搜索的方法去解决问题。
3.1 用搜索进行问题求解
在Agent推理要做什么的最简单的例子中，Agent有一个基于状态的世界模型，没有不确定性，并具有要完成的目标。这个模型或者是扁平的（不分层的）表示，或者是单层结构。Agent能够通过对世界状态空间表示的搜索找到从当前状态到目标状态的一条路径，从而决定如何完成其目标。它能在其行动之前找到实现其目标的一个动作序列。
这个问题可以抽象为一个数学问题，在一个有向图中找到从起始节点到目标节点的一条路径。其他很多问题都可以映射成这类抽象，所以考虑这个层次上的抽象很有意义。71本章大部分内容研究了寻找这样路径的各种算法。
搜索的含义是指Agent内在的计算。它不同于必须要有动作的现实世界的搜索，例如，寻找钥匙、举起垫子等。它也不同于网络上的信息检索。这一章中所研究的搜索是在内部描述中找到一条到达目标的路径。
搜索的思路是明确的：Agent针对一个问题构造出一个可能的局部解的集合，可以检查它们是否是最终解或者可以导致最终解。搜索就是反复地选择局部解，直到找到一条通往目标的路径才停止，否则，就会在所有可能的方向增加一条弧来扩展局部解。
搜索是大部分人工智能领域的基础，当Agent遇到一个问题时，它只给定了可以识别解的描述，而不知道解决这个问题的具体算法，所以它必须搜索问题的解。在NP完全问题中，我们有有效的方法来识别答案，却没有有效的方法去找到答案。这说明，在许多情况下，搜索是解决问题的必要部分。
人们经常能够通过直觉一步就找到很难的问题的解。但是，人们不倾向于解决普遍问题，相反，他们会处理具体的问题，与可能的搜索空间相比，他们熟悉这些问题。有些问题中不存在结构，或者其中的结构与物理世界不相关，这样的问题人们很难解决。在公钥加密编码中，搜索空间清晰明了，解的验证方法也已给出，尽管如此，人类仍然无法破解，计算机也不能在现实的时间框架中破解，这就例证了搜索的困难性。
搜索的困难性及人类能够有效解决一些搜索问题的事实，表明计算机Agent应当从一些特例中拓展新知识来指引它们找到解。超出搜索空间以外的知识叫做启发性（式）知识（heuristic knowledge）。本章以评估从一个节点到一个目标的花费的形式讲述一种启发式知识。