搜索启发式搜索1

下载 第9章 启发式搜索 9.1 使用评估函数 除了搜索过程不是从开始节点统一向外扩展外，本章描述的搜索过程有点像广度优先搜索， 不同的是，它会优先顺着有启发性和具有特定信息的节点搜索下去，这些节点可能是到达目标 的最好路径。我们称这个过程为最优（b e s t - f i r s t）或启发式搜索。下面是其基本思想： 1) 假定有一个启发式 (评估)函数 ，可以帮助确定下一个要扩展的最优节点 (给f加一个 “帽子”的原因后面就会清楚，称 为“f - h a t”)。我们采用一个约定，即 的值小表示 找到了好的节点。这个函数基于指定问域的信息，它是状态描述的一个实数值函数。 2) 下一个要扩展的节点 n是 (n)值最小的节点 (本章假定节点扩展产生一个节点的所有后 继)。 3) 当下一个要扩展的节点是目标节点时过程终止。 我们常常可以为最优搜索指定好的评估函数。如在 8数码问题中，可以用不正确位置的数 字个数作为状态描述好坏的一个度量： (n) = 位置不正确的数字个数(和目标相比) 在搜索过程中采用这个启发式函数将产生图 9 - 1所示的图，每个节点的数值是该节点的 值。 图9-1 一个启发式搜索过程的一个可能结果 这个例子表明，在搜索过程中我们需要偏向有利于回溯到早期路径的搜索 (为了避免由于过 分的优化试探而陷入“花园小径”)。因此我们加了一个“深度因子”给 : ， 是对图中节点n的“深度”估计 (即从开始节点到n的最短路径长度 )， (n)是对节点n的启发或 评估。像前面一样，如果 = 不正确位置的数字个数(和目标相比)， = 搜索图中节点n的 深度，我们可以得到图9 - 2。在这个图中，把 和 的值写在每个节点的旁边，在这种情况ˆ h (n)ˆ g (n) ˆ g (n)ˆ h (n) ˆ h ˆ g (n)ˆ f (n)=ˆ g (n)+ˆ h (n)ˆ f ˆ f ˆ f ˆ f ˆ f ˆ f ˆ f 到目标 到无结果的漫游 下，可以看到搜索相当直接地朝着目标进行 (除了用圆圈标注的节点外)。 这些例子提出了两个重要的问题。第一，我们如何为最优搜索决定评估函数？第二，最优 搜索的特性是什么？它能找到到达目标节点的好路径吗？本章的结尾将会提到关于评估函数选 择的一些指导，第1 0章将会解释关于自动学习评估函数的一些方法。本章主要讨论最优搜索的 形式表示。作为特殊的例子，我开发了一个包括最优搜索版本的一般图搜索算法（为了更详细 地了解启发式搜索，可以参考引用的文章和P e a r l写的[pearl 1984]）。 图9-2 使用 的启发式搜索 9.2 一个通用的图搜索算法 为了更准确地解释本章的启发式搜索过程，这里提出一个通用的图搜索算法，它允许各种 用户—偏爱启发式的或盲目的，进行定制。我把这个算法叫做图搜索（ G R A P H S E A R C H）。 下面是（第一个版本）它的定义。 G R A P H S E A C H 1) 生成一个仅包含开始节点n 0 的搜索树Tr。把n 0 放在一个称为O P E N的有序列表中。 2) 生成一个初始值为空的列表C L O S E D。 3) 如果O P E N为空，则失败并退出。 4) 选出O P E N中的第一个节点，并将它从O P E N中移出，放入C L O S E D中。称该节点为n。 5) 如果n是目标节点，顺着Tr中的弧从n回溯到n 0 找到一条路径，获得解决，则成功退 出（弧在第6步产生）。 6) 扩展节点n，生成n的后继节点集M。通过在Tr中建立从n到M中每个成员的弧生成n的后继。 7) 按照任意的模式或启发式方式对列表O P E N重新排序。 8) 返回步骤3 。 这个算法可用来执行最优搜索、广度优先搜索或深度优先搜索。在广度优先搜索中，新节 点只要放在O P E N的尾部即可（先进先出， F I F O），节点不用重排。在深度优先搜索中，新节 ˆ f (n)=ˆ g (n)+ˆ h (n) 第9章 启发式搜索计计85 下载 目标 点放在O P E N的开始（后进先出， L I F O）。在最优（也叫启发式）搜索中，按照节点的启发式 方式来重排O P E N。 9.2.1 算法A* 用最优搜索算法详细说明 G R A P H S E A R C H。最优搜索算法根据函数 的增加值，(在第7 步)重排O P E N中的节点，如8数码问题。把G R A P H S E A C H的这种算法称为算法A*。下面将会 看到，定义使A*执行广度搜索或相同代价搜索的函数 是可行的。为了确定要用的函数 族， 必须先介绍一些其他符号。 设h(n) =节点n和目标节点（遍及所有可能的目标节点以及从 n到它们的所有可能路径）之 间的最小代价路径的实际代价。 设g(n) = 从开始节点n 0 到节点n的一个最小代价路径的代价。 那么f(n) = g(n) + h(n)就是从n 0 到目标节点并且经过节点n的最小代价路径的代价。注意 f(n 0 ) = h(n 0 )是从n 0 到目标节点的一个（不受限的）最小代价路径的代价。 对每个节点n，设 (n)（启发因子）是h(n)的某个估计， (n)（深度因子）是由A*发现的到 节点n的最小代价路径的代价。在算法A*中，我们用 。注意，如果算法A*中的 恒等于 0，就成为相同代价搜索。这些定义示例在图9 - 3中。 图9-3 启发式搜索符号 图9 - 2所示的8数码搜索过程是A*应用的一个例子。在这里，我们假定了单位弧代价，因此 g(n)就是图中节点n的深度。尽管稍微有一点复杂，但在算法A*的定义中忽略了它们。如果要搜 索的隐式图不是一棵树会怎样呢？也就是说，假如有超过一个动作序列能从开始状态到达相同 的环境状态。例如，8数码隐式图显然就不是一棵树，因为动作是可逆的—即任何节点n的每 一个后继都可以使n作为它的一个后继。在建立8数码搜索树中忽略了这些循环。在那种情况下， ˆ h ˆ f =ˆ h +ˆ g ˆ g ˆ h ˆ f ˆ f ˆ f 86计计第二部分 状态空间搜索 下载 开始节点 到达一个目标的最低代价(最优)路径的代价 一条弧的代价 到达一个目标的最低代价路径的代价 从节点n到一个目标的优化路径的代价 分别是对f, g, k 的估计 —仅通过节点n 从n 0 到n的最佳路径的代价(本例中为8) 它们容易被忽略，只要在节点的后继中不包括它的双亲就行了。把G R A P H S E A R C H中的第6步 改为： 6) 扩展节点n，生成后继集合 ，n的双亲不能在 中。通过在Tr中建立从n到 中每个成 员的弧生成n的后继。 考虑到更长的循环，我们把6改为： 6) 扩展节点n，生成后继集合 ，n的祖先不能在 中。通过在Tr中建立从n到 中每个 成员的弧生成n的后继。 当然，为了检查这些更长的循环，我们要检查标识节点 n的祖先的数据结构。对复杂的数 据结构，这一步增加了算法的复杂度。 修改第6步的算法在搜索目标路径时避免了再循环，但是仍有可能通过不同的路径到达相 同的环境状态。解决这种问题的一个方法就是简单地忽略它。也就是说，算法不检查 中的一 个节点是否已经在O P E N或C L O S E D中。因此算法对那种可能性就健忘了，以致它可能通过不 同的路径到达相同的节点。这个“相同节点”在 Tr中重复多次，重复的次数是算法发现到达该 节点的不同路径数目。如果Tr中的两个节点被同样的数据结构标识，那么在它们下面有相同的 子树。也就是说，算法会重复搜索结果。后面我们将看到，对 施加适当的条件，当A*首次 扩展Tr中的节点n时，它已经找到了到达节点n并且有最小值 的一条路径。 为了防止在前述条件不成立下 的重复搜索，需要对算法 A*进行一些修改。因为搜索可 以顺着不同的路径到达相同的节点，因此算法 A*会产生一个搜索图G。G是A*扩展开始节点、 开始节点的后继等等而产生的节点和弧的结构。 A*也包含一个搜索树Tr。Tr是G的一个子图， 它是到达搜索图中所有节点的最优（最小代价）路径生成树。图 9 - 4显示了一个单位弧代价的 图。图9 - 4 a表示一个早期搜索阶段，搜索图的搜索树部分用黑色的弧表示，灰色的弧不在搜索 树中。注意图9 - 4 a中的节点4有两条路径可以到达；两条路径都在搜索图中，但只有一条在搜 索树中。我们保留搜索图是因为后面的搜索过程可能会发现更短的路径，这些路径使用了在早 期搜索图中、但不在早期搜索树中的弧。例如图 9 - 4 b，扩展节点1会发现到达节点2和它的子孙 （包括节点4）的一条更短路径，因此搜索树会相应地改变。 图9-4 搜索图和搜索过程产生的树 为了完整起见，阐述一下包含搜索图的 A*算法。然而，应该注意，很少需要这个算法， 因为我们常常对 施加一定的条件以保证当算法 A*扩展一个节点时，它已经发现了到达该节ˆ f ˆ f ˆ f ˆ f 第9章 启发式搜索计计87 下载 算法A *： 1) 生成一个只包含开始节点n 0 的搜索图G，把n 0 放在一个叫O P E N的列表上。 2) 生成一个列表C L O S E D，它的初始值为空。 3) 如果O P E N为空，则失败退出。 4) 选择O P E N上的第一个节点，把它从O P E N中移入C L O S E D，称该节点为n。 5) 如果n是目标节点，顺着G中，从n到n 0 的指针找到一条路径，获得解决方案，成功退出 （该指针定义了一个搜索树，在第7步建立）。 6) 扩展节点n，生成其后继节点集 ，在G中，n的祖先不能在 中。在G中安置 的成 员，使它们成为n的后继。 7) 从 的每一个不在G中的成员建立一个指向 n的指针（例如，既不在 O P E N中，也不在 C L O S E D中）。把 的这些成员加到O P E N中。对 的每一个已在OPEN 中或C L O S E D 中的成员m，如果到目前为止找到的到达 m的最好路径通过n，就把它的指针指向n。对 已在C L O S E中的 的每一个成员，重定向它在G中的每一个后继，以使它们顺着到目前 为止发现的最好路径指向它们的祖先。 8) 按递增 值，重排O P E N（相同最小 值可根据搜索树中的最深节点来解决）。 9) 返回第3步。 在第7步中，如果搜索过程发现一条路径到达一个节点的代价比现存的路径代价低， 我们就要重定向指向该节点的指针。已经在 C L O S E D中的节点子孙的重定向保存了后面 的搜索结果，但是可能需要指数级的计算代价。因此，第 7步常常不会实现。随着搜索 的向前推进，其中有些指针最终将会被重定向。 9.2.2 A*的可接纳性 对图和 施加一些条件可以保证应用到图的算法A*总能找到最小代价路径。图的条件是： 1) 图中每个节点的后继是有限的（如果有的话）； 2) 图中所有弧的代价都大于某个正数 ˛ 。 的条件是： 3) 对搜索图中的所有节点n， ≤ h(n)。也就是说， 决不会超过实际值h的估计。（这 样的 函数有时被称为优化概算机） 一般来说，找到满足这个低约束条件的 并不困难。例如，在城市路由问题中，从城市 n 到目标的直线距离就是从n到目标节点的最佳路径距离的一个最低约束。在 8数码问题中，不在 正确位置的数码个数就是到达目标步数的一个最小约束。 用这三个约束条件，只要存在到达目标的路径，算法 A*可以保证找到一条到达目标的最 佳路径。把这个结果作为一个定理（下面给出该定理的一个新版证明，原始证明参见 [ H a r t， N i l s s o n，& Raphael 1968]。 定理9.1 如果图和 具有上述的稳定条件，而且从开始节点n 0 到目标节点有一条有限代价 的路径，那么算法A*保证终止于到达目标的一条最小代价路径。 证明：证明的主要部分是下面的重要引理。为了获得关于 A*为什么能保证发现最优路径 ˆ h ˆ h ˆ h ˆ h ˆ h (n) ˆ h ˆ h ˆ f ˆ f 88计计第二部分 状态空间搜索 下载 的直觉知识，完全理解这个引理是重要的。 引理9 . 1 在A*终止前的每一步，总是有一个节点n*，它O P E N上有下面的特性： 1)n*在到达目标的一条最佳路径上。 2)A*已经发现了到达n*的一条最佳路径。 3) (n*) ≤ f (n 0 ) 引理证明：为了证明 A*每一步保证引理结论，只要证明（ 1）在算法开始时结论正确； （2）如果一个节点扩展前结论正确，那么节点扩展后结论继续正确。我们称这种证明方法为数 学归纳法。下面是证明过程： 基本条件：在搜索开始时（当节点n 0 准备扩展时），n 0 在O P E N上，它是到达目标的一条最 佳路径，A*已经发现了这条路径，而且，因为 (n 0 ) = (n 0 ) ≤ f (n 0 )，故 (n 0 ) ≤ f (n 0 )。 因此，在该阶段，节点n 0 可以是引理中的节点n*。 归纳步骤：假设在节点m(m≥0 )扩展时引理的结论是正确的，（用这个假设）证明在节点 m+ 1扩展时引理是正确的。参考图9 - 5将有助于我们证明归纳步骤。 设n*是m个节点扩展后，A*发现的一个最佳路径上的假设节点，它在 O P E N上。如果在第 （m+ 1）步，n*没有被选择扩展（图9 - 5 a），n*的属性和以前相同，因此证明了归纳步骤。如果 n*被选为扩展点（图9 - 5 b），它的所有新后继将被放在O P E N上，它们中至少有一个n p ，将会在 到达目标的最优路径上（由于假定一个最优路径通过 n*，它必须继续通过它的一个后继）。故 A*找到了到达n p 的一条最佳路径，因为如果有到达 n p 的一条更好路径，那么这条路径也是到达 目标的更好路径（这和我们的假设没有比通过 n*到达目标的路径更好的路径相矛盾）。这样， 让n p 成为第(m+ 1 )步的新n*，除了 (n*) ≤ f (n 0 )外，我们已经证明了归纳步骤。 图9-5 当第(m+ 1 )个节点要扩展时的情况 现在证明 (n*) ≤ f (n 0 )。对在一条最佳路径上的节点n*，A *已经找到了一条到达n*的最 佳路径，我们有： (n) = (n) + (n)，根据定义 ≤ g (n*) + h (n* ) 因为 (n*) =g (n* )， (n*) ≤ h (n* ) ≤ f (n* ) 根据定义g (n*) + h (n*) = f (n* ) ≤ f (n 0 ) 由于n*在一条最佳路径上，故f (n*) = f (n 0 ) ˆ h ˆ g ˆ h ˆ g ˆ f ˆ f ˆ f ˆ f ˆ h ˆ f ˆ f 第9章 启发式搜索计计89 下载 优化路径 目标, ng1 目标, n g2 目标, n g1 目标, n g2 优化路径 开始 a) A* 选择节点n 1 作为要扩展的第(m+1)个节点 b) A* 选择节点n*作为要扩展的第(m+1)个节点 开始 这就完成了引理的证明。 继续证明定理，我们首先证明如果存在可以到达的目标， A*必须终止，然后证明 A*终止 于找到一条到达目标的最佳路径。 • A*必须终止：假如它不会终止。在这种情况下， A*始终不断地扩展O P E N上的节点，最 终它将在搜索树上扩展比任何预设的深度约束更深的节点，因为我们已经假设正在搜索 的图有有限个分枝因子。由于每个弧的代价都比 Î > 0大，故在O P E N中的所有节点的 (因此 )值将最终超过f(n 0 )。这将和引理产生矛盾。 • A*终止于一条最优路径：A*只能在第3步（O P E N为空）或第5步（在一个目标节点）终 止。一个第3步的终止只能出现在不包含任何目标节点的有限图中， 只要有一个目标节 点，定理都声称找到到达目标的一条最佳路径。因此， A*终止于找到一个目标节点。假 如它终止于发现了一个非最佳目标n g2 ，f(n g2 ) > f(n 0 )， 当有一个最佳目标n g1 时，n g1 ≠ n g2 ， f (n g1 ) =f (n 0 )（见图9 - 5）。在n g2 终止时， （n g2 ）≥ f(n g2 ) > f (n 0 )。但是在A*选择n g2 进行 扩展之前，根据引理在O P E N上有一个节点n*，它在最优路径上，且 (n*) ≤ f (n 0 )。因 此，A*不可能选择n g2 进行扩展，因为A*总是选择有最小 值的节点进行扩展，而 (n* ) ≤ f (n 0 ) < f (n g2 )。 定理到此完全证明完毕。我们称任何保证能找到一条到达目标的最佳路径的算法是可接纳 的。因此，在定理的三个条件下， A*是可接纳的。延伸开来，任何没有高过 h的函数 都是可 接纳的。从现在起，当谈到关于A*的应用时，都假设定理的三个条件是满足的。 如果A*的两个版本A 1 *和A 2 *，其差别在于对所有的非目标节点， 1 < 2 ，那么我们就说 A 1 *比A 2 *更灵通 (i n f o r m e d)。在叙述下面的结果时没有进行证明（参见 [ H a r t，N i l s s o n，& Raphael 1968， H a r t，N i l s s o n，& Raphael 1972， Nilsson 1980]）。 定理9.2 如果A 2 *比A 1 *更灵通， 那么对任何有从n 0 到目标节点的一条路径的图，在搜索终止 时，被A 2 *扩展过的每一个节点也被A 1 *扩展过。 可以得出A 1 *扩展的节点至少和 A 2 *的一样 多，这个更灵通的算法 A 2 *也就更有效。因此， 我们要寻找尽可能接近真实函数 h的函数 （为了搜索效率），同时又不能超过它们（为了 可接纳性）。当然，在衡量总的搜索效率时， 也应当考虑计算 的代价。最灵通的算法是 ≡h，但是典型地讲，这样的 只能在很高的 代价下，通过完成我们正在尝试的每一个搜索 才能得到。 图9 - 6概括了我们已经讨论过的一些搜索算 法的关系。当对所有的节点 ≡0时，我们得 到相同代价算法（搜索顺着相同代价的边沿向 外扩展）。当 (n)= (n) =深度（n）时，我们 得到广度优先搜索法，它顺着相同深度的边沿 向外扩展。相同代价和广度优先算法都是 A* ≡0 )的特殊情况，故它们也都是可接纳的。 ˆ h ˆ g ˆ f ˆ h ˆ f ˆ h ˆ h ˆ h ˆ h ˆ h ˆ h ˆ f ˆ f ˆ f ˆ f ˆ f ˆ g 90计计第二部分 状态空间搜索 下载 图9-6 搜索算法之间的关系 深度优先 排序 =深度 广度优先 ˆ f 相同代价 最佳优先搜索 一般的图搜索算法 9.2.3 一致性（或单调）条件 考虑一对节点（n i 、n j ），n j 是n i 的一个后继。如果在搜索图中所有的这种节点对都满足下述 条件： (n i )－ (n j ) ≤ c(n i ，n j ) 其中c(n i ，n j )是从n i 到n j 的代价。 上式也写作： (n i ) ≤ (n j ) + c(n i ，n j ) 和 (n j ) ≥ (n i ) － c(n i ，n j ) 那么我们就说h服从一致性条件。这个条件陈述了顺着搜索图中的任何路径，到达目标的 最优（剩余）代价的估价的减少不会大于该路径弧代价。也就是说，在考虑了一个弧的已知代 价后，启发式函数在局部是一致的 。这种一致性条件可以表示为如图9 - 7所示的三角不等式。 一致性函数也暗示了当搜索树中结点的值远离开始节点时，它是单调非递减的。设n i 和n j 是 由A *在搜索树上产生的两个节点，n j 是n i 的后继。如果满足一致性条件，就有 (n j )≥ (n i )。为 了证明这个事实，我们从一致性条件开始： (n j )≥ (n i )-c(n i ，n j ) 给上式两边都加上 (n j ），有： (n j ) + (n j ) ≥ (n i ) + (n j ) －c(n i ，n j ) 但是 (n j ) = (n i ) + c(n i n j ) (我们可能会担心 (n j ）会比这个值小，因为我们可能会顺着其 他的比通过n i 点代价更低的路径到达n j 。但这样一来，在搜索树上n j 就不是n i 的后继了)。 因此， (n j ) ≥ (n i ) ; 因为这个原因，一致性条件（对 ）也常被称为单调条件（对 ）。下面是一个涉及到一 致性条件的重要定理（[ H a r t，Nilsson & Raphael 1968])。 定理9 . 3 如果 上的一致性条件被满足，那么当A *扩展节点n时，它已经找到了到达节点 n的一条最优路径。 证明：假设A *在隐式图G中正在搜索从开始节点n 0 到目标节点的一条最佳路径，它准备扩 展一个打开的节点n。设 x =（n 0 ，n 1 ，. . .，n l ，n l+ 1 ，. . .，n = n k ）是图G中从n 0 到n的一条最佳路径 的节点序列，n 1 是 x 上被A*扩展的最后一个节点（参见图 9 - 8）。因为n l 是 x 上最后一个没打开的 ˆ h ˆ f ˆ h ˆ f ˆ f ˆ g ˆ g ˆ g ˆ g ˆ h ˆ g ˆ h ˆ g ˆ h ˆ h ˆ f ˆ f ˆ h ˆ h ˆ h ˆ h ˆ h ˆ h 第9章 启发式搜索计计91 下载 图9-7 一致性条件 图9-8 用于证明定理9 . 3的图 闭合的 打开的 优化路径上的前 一个闭合节点 A* 是关于扩展节 点n的算法，可能 由其他路径到达 到达节点n 的优化路径 Pearl [Pearl 1984, pp.82-83] 定义了一个启发式函数的全局一致性概念，并证明它等同于我们关于局部一致性的定义。 节点，因此n l + 1 在O P E N上是一个扩展候选者。 对任何节点n i 和它的后继节点n i+ 1 ，在 x 中（到达n的一条最优路径），我们有 g (n i+ 1 ) + (n i+ 1 ) = g (n i ) + c(n i ，n i+ 1 ) + (n i+ 1 ) ≥g (n i ) + (n i ) ; 当一致性条件满足时，由≥关系的传递性可以得到 g (n j ) + (n j ) ≥ g(n i ) + (n i ) （对 x 上的任何n i 和n j (i计划

项目进度计划表范例计划下载计划下载计划下载课程教学计划下载