第9章启发式搜索.ppt

1、第九章使用启发式搜索、第二部分状态空间搜索和评估函数，下文描述的搜索过程有点类似于广度优先搜索，不同之处在于它们没有从开始节点一起扩展搜索过程，但是不同之处在于它们沿着启发性的并且具有特定信息的节点优先搜索。 此过程称为“最佳”(best-first )或启发式搜索。 其基本思想：1)假设有启发式(评估)函数，有助于确定下一个要扩展的最佳节点。 我们采用的值较小的规则表示找到了好的节点(此函数基于指定问题域的信息，是状态描述的实值函数)。 2 )下一个扩展节点n是具有最小值的节点(假设节点扩展产生一个节点的所有后续行)。 3 )如果下一个要扩展的节点是目标节点，则结束该处理。 最佳搜索通常可以

2、指定适当的评估函数。 例如，在8位的数字问题中，可以将不在正确位置的数字的个数用作状态描述的好坏的尺度：位置不正确的数字的个数(与目标相比)，在搜索过程中使用该启发式函数会生成如下图所示的图表，各节点的数值是该节点的值中的组合图层性质变更选项。 此示例说明在搜索过程中，搜索应该偏重于有助于追溯到初始路径的搜索。 因此，将图中节点n的“深度”估计(即，从起始节点到n的最短路径长度)与节点n的启动或评估“深度系数”相加。 如上所述，=不正确位置的数字个数(与目标相比)，搜索图中节点n的深度，可以得到下图：2个重要问题：第一，如何确定最佳搜索的评价函数？ 第二，最佳搜索的特性是什么？ 你能找到到目标

3、节点的好路径吗？ 后面讨论上述两个问题，这里主要讨论最优搜索的形式表示。 中的组合图层性质变更选项。 GRAPHSEARCH 1)生成仅包含起始节点N0的搜索树Tr。 将N0放入名为OPEN的有序列表中。 2 )产生初始值为空的列表CLOSED。 如果OPEN为空，则失败并终止。 4 )选择open的第一个节点，将其从open中删除并进行CLOSED，将该节点称为n。 5 )如果n是目标节点，则当已经沿着Tr中的圆弧从n向上游找到n-0条路径并得到解决方案时，正常终止(在步骤6中产生圆弧)。 6 )扩展节点n以产生n的后续节点集合m (对于OPEN而言)。 通过在Tr中为每个成员创建从n到m的

4、弧，生成n的后续弧。 7 )按任意模式或启发式排序列表OPEN。 8 )继续步骤3。 的双曲馀弦值。 该算法可以用于执行最优搜索、广度优先搜索或深度优先搜索。 在广度优先搜索中，新节点只要位于OPEN的末尾即可(先进先出、FIFO )，节点不需要进行重新排序。 在深度优先搜索中，将新节点置于OPEN的开始(后向先出和LIFO )。 在最佳(也称为启发式)搜索中，按照节点的启发式方法对OPEN进行排序。 用算法A*、最佳搜索算法详细说明GRAPHSEARCH。 最优搜索算法根据函数的增量对OPEN的节点进行排序(在步骤7中)。 GRAPHSEACH的这种算法称为算法A*。 设置h(n )节点n和

5、目标节点(所有可能的目标节点和从n到它们的所有可能路径)之间的最小成本路径的实际成本。 g(n )是从开始节点n0到节点n的最小成本路径的成本。 因此，f(n)=g(n) h(n )是从n0到目标节点并且经过节点n的最小成本路径的成本。 请注意，f(n0)h(n0)是从n0到目标节点的最低成本路径的成本(不限制)。 对于每个节点n，(启发因子)设为h(n )的估计，并且(深度因子)设为去往在A*中发现的节点n的最小成本路径的成本。 在演算法A*中，我们使用。 如果算法A*的常数为0，则搜索成本相同。如果要搜索的隐式图不是一个树(一个或多个操作序列可以从起始状态到达相同的环境状态)，会怎么样呢？

6、深层问题：将第6步的GRAPHSEARCH改为扩展节点n，并生成后续集合(进入OPEN )。 n的父母不能在里面。 通过在Tr中创建从n到中的每个成员的圆弧，生成n的后续。 考虑到更长的循环，步骤6被改变为： 6以扩展节点n，产生后续的集合(进入OPEN )。 n的祖先不能在里面。 通过在Tr中创建从n到中的每个成员的圆弧，生成n的后续。算法A*: 1 )生成只包含开始节点n0的探索曲线图g，将n0放置于OPEN的列表中。 2 )生成初始值为空的列表CLOSED。 如果OPEN为空，则退出失败。 4 )选择open上的第一个节点，将其从open移动到CLOSED，将该节点称为n。 5 )如果n

7、是目标节点，则从n到n-0的指针沿着g找到路径，得到一个解决方案，成功结束(该指针定义了搜索树，在步骤7中建立)。 6 )扩展节点n并产生随后的节点集合m，且在g中，n的祖先不用于m。 在g中放置m的成员，让他们成为n的接班人。 7 )创建指向m中不在g中的每个成员到n的指针(例如，既不在OPEN中也不在CLOSED中)。 将m的这些成员添加到OPEN中。 如果对于已经存在于m的每个OPEN或CLOSED中的成员m，到目前为止所找到的m的最佳路径经过n，则使指针指向n。 对于已经封闭的每个m成员，重定向g成员的继承人，使其沿着到目前为止发现的最佳路径指向祖先。 按增量值对OPEN排序(相同的最

8、小值可以根据搜索树中最深的节点进行解析)。 9 )转到步骤3。 中的组合图层性质变更选项。 在步骤7中，如果发现搜索过程中一条路径到达一个节点的成本低于现有路径成本，则将指向该节点的指针重定向。 CLOSED的节点子孙重定向存储后续搜索结果，但可能需要指数修正成本。 因此，步骤7往往没有实现。 随着搜索的进行，某些指针最终会被重定向。 A*的可接受性确保通过添加图和一些条件，应用于图的算法A*始终找到最小成本路径。 1 )图中每个节点的后续行为是有限的(如果有的话)；及2 )图中所有圆弧的成本大于正数。 的条件是： (3)对于搜索图表中的所有节点n，(n)h(n )。 也就是说，绝对不超过实际

9、值h的估计。 (这种函数有时被称为最优估计功能)，如果具有上述稳定性条件(如定理9.1图)并且存在从起始节点n-0至目标节点的有限成本路径，则算法A*确保在到达目标的最小成本路径处终止。 辅助命题9.1a*结束前的每个步骤总是有一个节点n*。 OPEN具有1)n*位于达到目标的最佳路径上的特性。 2)A*找到了通向n*的最佳路径。 3 )确保找到达目标的最佳路径的算法被接受。 如果A*的两个版本A1*和A2*对于所有非目标节点都不同，则A1*可能比A2*更灵通。 如果定理9.2A2*早于A1*，那么对于具有从n0到目标节点的路径的图表，搜索时由a2*扩展的每个节点也由A1*扩展。 可以看出，A

10、1*扩展的节点至少与A2*一样多，这种更灵活的算法A2*也更有效。 因此，寻找尽可能接近真函数h的函数(为了搜索效率)，并且不能超过它们(为了可接受性)。 最早的算法是h、一致性(或单调)条件，考虑到一对节点(ni，nj )，nj是ni的继承者。 在搜索图表中，假设满足这样的节点对全部是从ni到nj的成本这一条件。 上式也写着：那么，说h遵循一致性条件。 中的组合图层性质变更选项。 此条件表明，沿着搜索图中的任意路径，达到目标的最佳(剩馀)成本评估值的减少不大于该路径圆弧成本。也就是说，考虑到一个弧的已知成本，启发式函数局部匹配。 这种一致性条件可以表示为如图所示的三角不等式。 一致性函数还暗

11、示了当搜索树中的节点的值远离开始节点时，该值不会单调递减。 因此，一致性条件(对)通常也被称为单调条件(对)。 如果满足定理9.3上的一致性条件，则当A*扩展节点n时，找到通往节点n的最佳路径。 在满足一致性条件时，可以对A*的可接受性提供简单直观的论证。 这意味着1 )的单调性，搜索沿着值变大的边缘向外扩展。 2 )因此，所选择的第一目标节点是具有最小值的目标节点。 3 )对于任何目标节点ng (在此，使用了只要函数一致，就不会比真正的h函数大的事实。 4 )因此，第一个选定的目标节点将成为具有最小值的目标节点。 5 )定理9.3的一个结论是，每当一个目标节点ng被选择性地扩展时，我们找到了

12、通向该目标节点的最佳路径。 即。 6 )因此，第一个选定的目标节点将成为算法检测到的最佳路径的目标节点。迭代加深的A*，宽度优先搜索的存储需求随着搜索空间中目标深度的增加而指数增加。 好的启发式搜索减少了分支因子，但启发式搜索具有上述缺点。 深入第8章介绍的重复搜索不仅可以找到最低成本路径，而且存储需求会随着深度的增加而线性增加。 反复深化A*(ID* )方法可以得到与启发式搜索相似的优点。 通过使用了IDA*的并行实现，可以得到更高的效率。 中的组合图层性质变更选项。 此方法类似于常规迭代深化方法，执行一系列深度优先搜索。 第一次搜索将截止成本设置为等于n0是起始节点。 我们知道，到目标的最

13、佳路径成本可能等于此截断值(如果上述句子是肯定的)。 因为不可能很小)。 我们以深度优先方式扩展节点，随时只要扩展节点的后续值超过截断值，就进行倒回。 显然，如果深度优先搜索在目标节点结束，则找到了到达目标的最小成本路径。 否则，最佳路径的成本将大于此截断值。 因此，增大截止值，再次开始深度优先搜索。递归最优搜索和递归最优搜索(RBFS )方法略多于IDA*所使用的存储，但少于IDA*生成的节点。 当扩展一个节点n时，RBFS纠正n的后续值并且重新纠正搜索树的n和n的祖先值。 这个再修正计算的过程称为值的回溯(backing up )。 另外，闪回是指刚扩展的节点的后续闪回值为后续值。 继搜索

14、树之后具有mi的节点m的背轨值，其中(mi )为节点mi的背轨值。 中的组合图层性质变更选项。 如果刚刚扩展的节点n的后续一个在所有OPEN点都具有最小值，则依次扩展。 但是，如果OPEN中的其他节点n不是n的后继者，则有最小值。 此时，算法追溯到节点n和n的最低共同祖先节点k。将节点kn作为通向节点n的路径上的节点k的后继。 因为RBFS删除以kn为根的子树，所以kn是具有与它的背景值相等的值的OPEN节点，并且继续在具有最低值的OPEN节点下进行搜索。 启发式函数和搜索效率在决定A*效率时启发式函数的选择很重要。 虽然可接受性得到保证，但由于搜索成本相同，效率不高。 与上述低约束的最大可能

15、值相等，不仅可以扩展较少的节点，还可以维持可接受性。 在选择函数时，必须考虑修正算法本身的修正量。 在正确的函数与其修正计算成本之间往往取得折衷。 通常使用一些非低约束函数以牺牲可接受性的方式交换搜索效率。也就是说，非最佳路径比最佳路径更容易找到，而非低约束函数比低约束函数更容易修正。 在这种情况下，扩展节点减少(以容忍为代价)且校正量也减少，因而效率可能加倍。 中的组合图层性质变更选项。 另一种可能性是更改评估函数之和的权重。 也就是说，w是正数。 非常大的w值过于强调启发式的部分，非常小的w强调搜索的宽度优先特性。 实验结果表明，如果w值与搜索树上的节点深度成反比，则搜索效率大多会提高。

16、对于浅的深度，搜索主要取决于启发式的部分，但是搜索逐渐以广度优先级为主，使得随着深度的增加，找到最终到达目标的路径。 搜索效率的测定值为有效分枝因子b，表示搜索过程向目标前进的激烈程度。 假设搜索找到一个长d的路径并且创建了n个节点，则b是具有以下属性的树上每个节点的后续数目：树中的每个非叶节点有b个后续项： 树中叶节点的深度都是d。 树中的节点总数为n。 b和路径长度d以及所生成的节点的总数目n之间存在如下关系： B B2 BdN，总而言之，该三个重要因素影响算法A*的效率：所发现的路径的成本(长度)； 检测路径中扩展的节点的计算量。 选择适当的启发式函数可以平衡这些因素以最大化搜索效率。 至今讨论的所有搜索方法都包括启发式