ch2_search1

6.034 笔记：2.1部分幻灯片2.1.1搜索在人工智能中占有关键作用。

这些算法为几乎每一个有系统地探索选择项的方法提供概念的骨干。

我们以一些背景知识、术语和一些基本的实施策略开始，然后进行四节课的搜索算法学习，研究算法的区别可以从两维展开：首先根据无信息的（盲目的）搜索和有信息的（所谓的启发式）搜索。

有信息的搜索是有特定任务的信息可以使搜索过程更加有效率。

另一不同是任意路径搜索和最优搜索。

最优搜索是寻找最有可能的路径而任意路径搜索仅仅是找到一些解。

幻灯片2.1.2 连接（边）节点（顶点）末端（叶）树根B 是C 是A 是C 是我们所采用的搜索方法依据树和图定义，因此我们聚焦于这些结构的一些专业术语。

·一棵树是有节点和连接组成（圈和线）,相连没有回路（循环）。

节点有时被看作是顶点而连接被看作边（这在图中是很常见的）·一棵树有根节点（是一棵树的开始处）。

除根节点外，每个节点都有唯一一个父节点（又名直接祖先）。

更一般地，祖先节点可以由节点重复的返回父节点而到达。

每一个节点（除末端（又名叶）节点）都有一个或多个孩子（又名直接子孙）节点）。

通常来说，一个子孙节点可以通过重复地连接至子节点而到达。

幻灯片2.1.3 图也可以是有通过连接把节点连起来构成的，但是这里可以有回路并且一个节点可以有多个父母。

我们要处理两种图：有向图，即它的连接是有向（类似于单行道）的。

连接（边）节点（顶点）末端（叶）树B 是根C 是A 是C 是有向图（单向道）幻灯片2.1.4 连接（边）节点（顶点）末端（叶）树根B 是C 是A 是C 是有向图（单向道）无向图（双向道）而无向图即连接的方向是双向的。

你可以把无向图理解为一个有向图的简化，它的连接节点可以是双向连接的。

幻灯片2.1.5 任何地方都有图，例如，公路网或者航空路线网还有电脑互联网。

在所有的这些情况中，我们也许对找到图中满足某种特性的一条路径感兴趣。

他可能是其中的任何一条，也许我们只对其中的有最小“跳”的那条有兴趣，或者一条在假定每跳不全相等的最小代价的路径。

幻灯片2.1.6图的例子行动计划（自然界可能状态的图）把C 放A 上把C 放B 上把C 放A 上把B 放C 上把A 放B 上然而，图有更多种描述方法。

考虑图的定义还有如下定义的图：每一个节点描述可比作自然界的一个状态，例如，在方块图上哪些个方块块在哪些方块块的上面，它的连接链路表示了从一个状态到另一个状态的变化。

在这样的图中的一个路径（从起始节点到目标节点）就是“行动计划”是为了完成从某个已知的状态到某个想要到达的目标状态。

这种类型的图在人工智能中是比较有趣的。

幻灯片2.1.7 在人工智能中解决问题的常用方法就是简化需要解决的问题使其成为搜索图的一种。

使用这种方法时，我们必须明确什么状态、行动及目标测试。

假定要完成一种状态，既是，要表示出所有与这个要解决的问题相关的问题。

因此，例如，当我们做一次最便宜的环球飞行计划，我们不需要知道机场的地址，知道飞机的班次已经足够了。

然而，在计划怎么从宾馆到达机场的时候，机场的地址也将会很重要。

注意，一般的，计划航线的时候，我们不仅需要知道城市，也要知道机场，因为在一个城市里可能有多个机场。

我们假设这个计划已经确定，既是我们精确的知道状态在行动之后发生。

假设行动是不连续的，因此我们就不用表示当这个行动发生时发生了什么。

例如，假设飞机到达了预计的地点，但是在飞行过程中发生了什么并不重要(至少是在计划的航线中)。

注意到我们已经指出需要一个目标测试，不仅仅是需要一个明确的目标状态。

因此，例如，我们也许会对德国的任何一个城市都有兴趣，而不是已确定的法兰克福。

或者，当我们证明一个定理，我们所关心的是目前我们数据库中的其中一个事实。

任何最终情况的集合包含了预料事实是一个论证。

幻灯片2.1.8注意到树是有向图中的一种（即使在连接中没有标示箭头）。

树没有回路并且只有一个父节点（或根结点）。

循环会对搜索不利，很显然你不想绕来绕去却不知道在哪。

当要求搜索一个图时，我们可以通过两步构建成等价的搜索树：把无向连接转化为双向连接；更重要的是，要确定没有选择循环路径，而且最好不要访问同一个节点两次。

幻灯片2.1.9你可以参考这个从图转化为树的例子。

假设我们从S开始搜索，试着找出一条到达G的路径，然后我们沿着图，把每一个节点与和它连接的节点相连这将不会形成循环（一旦遇到G就停止）。

注意到对于以S开头的图中的每一条不循环路径，这棵树都有叶节点。

然而还要注意的是，即使我们避免使其循环，但是树中的一些节点还是重复了（彩色标记的），即是它们被以不同的非循环路径到达。

这意味着这棵树的完整搜索可能要做额外工作。

怎么做才能避免出现回路和访问节点时避免做额外工作是非常重要的。

当我们讨论完各种算法后将重新访问。

幻灯片2.1.10一个重要的区别将会使我们对状态和搜索节点一目了然。

状态是对真实世界的安排（或者至少是模型）。

我们假设正在搜索的潜在“真实”的状态图（也许它并不在计算机里被明确的表示；他也许含蓄地被行为定义）。

假设你可以通过不同的路径，以不同的方式到达真实世界的同一个地点。

另一方面，一个搜索节点是搜索算法中的一个数据结构，当搜索时就构建了明确的树的节点。

每个节点指示一些状态，但不是唯一的。

注意到这个节点通常与从起始状态到和节点相连的状态的路径相对应。

这也是按照搜索算法产生树的事实。

因此，当我们返回一个节点，也就重复了路径。

6.034 笔记：2.2部分幻灯片2.2.1因此，让我们看看我们所要探究的不同类型的搜索算法。

最简单的是非信息的、任意路径的算法。

特别是，我们要研究深度优先查询和广度优先查询。

这两种算法最基本的就是要找出一种明确（与目标独立）的顺序搜索树的所有节点，并且在找到第一条到达目标状态的路径时停止。

幻灯片2.2.2下一个类型是有信息的、任意路径算法。

这种方法的关键思路就是要找出一条有效地、完善的方法，要尽快的找到目标节点或是找出更满意的目标状态。

幻灯片2.2.3下面我们来研究无信息，最优的算法。

这种方法保证找到最优路径（通过计算图的边的权重来测量）但是不能使用超出图的定义范围的信息。

幻灯片2.2.4最后，我们看看无信息、最优的算法，这也会保证找到最优路径但是使用启发式找到最优路径会比无信息的算法快得多。

幻灯片2.2.5这里表示的几种搜索策略是一般搜索算法中的几个例子。

基本思想是制作一个节点（既是，部分路径）链表（Q ），然后从Q 中选出一个点，看它是否能到达目标节点，否则扩展这条路径到它的相邻节点，把节点加入Q 的后面。

除了一些细节，大致就是这样。

顺便说一句，记录下我们已经到达（访问）状态的路径并且不要重复记录同一个节点。

这当然可以防止我们陷入回路中，不管潜在的图已经连接，因此我们只能一次到达某个状态。

等一会我们会讨论研究这种方法的意义。

幻灯片2.2.6当然，关键问题是，怎么从Q 中选出哪个元素，怎么样才能精确地把新路径加入Q 的后面。

操作中的不同的选择将会产生不同的搜索策略。

幻灯片2.2.7 对于这一点，我们已经看到了一种特殊的搜索。

例如，深度优先搜索总是从搜索树中最深的节点开始，我们可以采取以下步骤实现： ·找出Q 的第一个元素作为测试节点并扩展·把新路径（被扩展）加入到Q 的前端，这样下一条被检测的路径会成为目前这条路径的扩展之一，并成为那个节点的子孙之一。

深度优先搜索的一个优点是Q 不会很大。

我们将会在以后研究其细节，但是会很容易看到Q 的大小主要是依据搜索树的深度而不是宽度。

幻灯片2.2.8广度优先搜索是另一种无信息的搜索方法。

这种基本方法是从Q 中再次选出第一个节点去验证BUT ，这次我们把扩展路径加入到Q 后面。

这也就意味着从Q 中选出的下一条路径将不是目前节点的子孙，但是这棵树的同一层。

注意到在广度优先搜索中，Q 将会很大，我们在后来看到更长的路径（到达下一层）一直到我们完成同一层上的所有路径。

我们将着眼于怎么去实现其他的搜索策略。

但是，首先，让我们看看这些实现办法中更多的细微差别。

幻灯片2.2.9这个微妙之处就是算法测试的成功之处（即目标测试）。

有两个精彩之处：第一个就是路径的扩展和到达的目标，另一点是从Q中读取路径时。

我们选择了后者（在算法的第三步测试）因为它将最接近最优搜索。

然而测试的扩展路径是正确的并且将会节省任意路径搜索的工作量。

幻灯片2.2.10在这点上，我们要同意术语将会在讨论其余的四种搜索方式上占有重要地位这个观点。

让我们以Visited及它的相关词Expanded开始，当一条路径到达节状态（即，节点就是指这个状态）并加入到Q中时，我们说这个节点被访问。

因此，如果这个状态是Q中的任意一个节点，已经被访问过。

注意到即使没有路径到达从Q中取出状态，这也是正确的。

幻灯片2.2.11当到达状态的路径从Q中取出就称状态M被扩展。

在这点上，,M的子孙被访问过。

到达其子孙的路径被加入到Q。

幻灯片2.2.12请明确这些区别，这将会降低你学习的难度。

幻灯片2.2.13在我们对这些简单搜索算法的描述中，我们使用了搜索列表。

列表中的所有状态对应了已经增加到Q中的任意节点。

就像我们先前提到的，回避了表中的一些点就会避免陷入循环，即使图中有循环。

注意，这种方法要比在局部的避免每条路径循环要好得多；这是所有路径的整体机制。

事实上，这比检测每条路经更普遍，因为定义了一条路径将会导致多次访问同一个节点。

但是，为了避免循环，访问列表也意味着我们的查询不能重复扩展同一个节点。

这个基本的思想是不需要为一个路径从任意一个状态到目标搜寻超过一次。

如果我们第一次没能找到路径，那么第二次也不会找出。

这会节省有可能是巨大的工作量，不要再看第二次了。

以后将会讲解更多。

幻灯片2.2.14实现的关键点：尽管我们讲“访问列表”，用列表记录访问状态的路径并不是好主意，因为我们要不断检测在列表里是否有一些特殊的状态，这就需要浏览列表。

然而，我们想要使用大致的连续时间的方法。

如果这些状态有一个数据结构，可以使用一个标志位来指示某个状态是否被访问过。

一般地，可以使用一个混编的表，数据结构可以使我们检测在大致连续的时间里状态是否被访问过，这与表的类型无关。

然而，不管我们的访问速度有多快，这个表仍然需要额外的存储空间。

以后我们就可以看到使用访问列表解决大型问题时的代价是受限制的。

幻灯片2.2.15另一个需要明确的重要的概念就是状态的启发式值。

“启发式”这个单词通常是指“经验法则”。

有些是很有用的但不能保证有效。

幻灯片2.2.16启发式函数有类似的含义。

是指一个函数（定义一个点而并不是路径）引导搜索时是很有用的，但并不能保证能得到希望的结果。

启发式搜索不能保证最短路径或最优（甚至对于最优优先）。