知识卡片

普通读书笔记卡 · 5654.d.1.f.4.n.4 · 生成模型:未记录

A星按已走成本加启发式排序

理解等级:中级

对待扩展状态使用 f(n)=g(n)+h(n),其中g是当前已知路径的实际累计成本,h估计到目标的剩余成本;从开放集中取f最小的状态扩展。不同边代价时g不能简单用深度代替。f小表示估计总成本较小,不等于该状态几何上更接近目标。

在非负边权、目标启发式为0、h不高估真实剩余成本等标准条件下,正确处理更优路径并在目标以最小优先级出队时终止,可得到最优解;若启发式不一致,图搜索通常需在发现更优g时重新开放状态。

195称估计接近就得到最优,这不充分:轻微高估也可能改变搜索顺序并得到次优解。需要结合不高估、目标值、代价模型及重复状态处理证明。

196的03341–03343展示两种评估函数在同一八数码例子中访问不同数量状态;更少扩展不自动证明最优或所有输入上更快。评估函数本身的计算成本也须计入。

198列举三种八数码评价函数与不同搜索规模。h=0时A星退化为统一代价搜索,只有等步长代价时才与BFS按成本层相对应。负启发值不一定破坏可采纳性,但目标通常需h=0,且具体最优性证明还依赖其他条件。

200的03349–03352展示不同十五数码状态:一个实例较快找到解,另一个耗尽给定内存。启发式不一定总能减少搜索空间;扩展数、计算成本、重复状态和内存都需结合目标工作负载评估。

203的03353–03356比较八数码实验,记录平均搜索规模、路径长度及限深失败次数。特定启发式与输入下A星扩展较少不代表所有实例均如此;经验拟合不能替代理论复杂度,随机移动次数也不一定等于最短解深度。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 6 处

    • · 查看原书依据

      A*搜索 广度优先搜索能够找到一个最优解(如果存在),但是可能需要访问大量的节点,因为我们可以看到,它并没有尝试对候选走法进行排序。相反,深度优先搜索却是尽可能多地向前探测路径,不过,深度优先搜索的搜索深度必须得到限制,要不然它很有可能会在没有任何结果的路径上花费大量的时间。A*搜索在搜索时能够利用

    • · 查看原书依据

      相差不远,那么A*搜索得到的是开销最小的解。 [1]注意g*(n)可能≥g(n),因为事实上可能有更少的走法达到目标。

    • · 查看原书依据

      GoodEvaluatorf*(n)函数。图7-12的搜索树使用的是同样由Nilsson提出的WeakEvaluator f*(n)函数。浅灰色的棋面状态表示达到目标状态时开放集合的元素。GoodEvaluator和WeakEvaluator都能够得到同样的解,但是使用GoodEvaluator函数

    • · 查看原书依据

      启发函数h*(n)性能可以接受,那么这时候我们就可以使用A*搜索。如果,那么表示启发式函数是可以接受的。这种限制需要满足两个方面的条件,如果h*(n)返回一个负数(表示有时候棋面状态n越过了目标状态),那么g*(n)的效果就会被抵消掉。如果h*(n)>h(n),那么A*搜索可能找不到最优解。寻找到一

    • · 查看原书依据

      十五数码问题,八数码问题的一个扩展,使用八数码问题的GoodEvaluator函数扩展时,目标状态如下: 初始状态如下: A*搜索在处理39个棋面状态之后,快速找到了一个15步的解,这个时候开放集合中还有43个棋面状态,如图7-13所示。 图 7-13 十五数码问题的A*搜索树 由于有着15步的限制

    • · 查看原书依据

      比较 广度优先搜索能够保证找到步数最少的解,但是它可能需要评价规模相当大的移动序列。深度优先搜索试着在每次搜索时能够前进更多步,它可能能够快速得到一个解,但是它也可能在搜索树的某个部分浪费大量的时间,尽管看起来这个部分不可能得到解。 我们认为比较深度优先搜索,广度优先搜索和A*搜索是值得的。使用八数

    参考来源

    - 位置:《算法技术手册》第7章《A*搜索》(spine1602;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1565.html;u194-ch07-005)。 - 结论依据:194全文及03340伪代码实读;最优性条件按标准图搜索表达。 - 原始内容:A*搜索 广度优先搜索能够找到一个最优解(如果存在),但是可能需要访问大量的节点,因为我们可以看到,它并没有尝试对候选走法进行排序。相反,深度优先搜索却是尽可能多地向前探测路径,不过,深度优先搜索的搜索深度必须得到限制,要不然它很有可能会在没有任何结果的路径上花费大量的时间。A*搜索在搜索时能够利用 - 位置:《算法技术手册》第7章《输入/输出》(spine1602;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1565.html;u195-ch07-005)。 - 结论依据:195称估计接近就得到最优,这不充分:轻微高估也可能改变搜索顺序并得到次优解。需要结合不高估、目标值、代价模型及重复状态处理证明。 - 原始内容:相差不远,那么A*搜索得到的是开销最小的解。 [1]注意g*(n)可能≥g(n),因为事实上可能有更少的走法达到目标。 - 位置:《算法技术手册》第7章《使用环境》(spine1603;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1566.html;u196-ch07-005)。 - 结论依据:196的03341–03343展示两种评估函数在同一八数码例子中访问不同数量状态;更少扩展不自动证明最优或所有输入上更快。评估函数本身的计算成本也须计入。 - 原始内容:GoodEvaluatorf*(n)函数。图7-12的搜索树使用的是同样由Nilsson提出的WeakEvaluator f*(n)函数。浅灰色的棋面状态表示达到目标状态时开放集合的元素。GoodEvaluator和WeakEvaluator都能够得到同样的解,但是使用GoodEvaluator函数 - 位置:《算法技术手册》第7章《结论》(spine1605;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1568.html;u198-ch07-005)。 - 结论依据:198列举三种八数码评价函数与不同搜索规模。h=0时A星退化为统一代价搜索,只有等步长代价时才与BFS按成本层相对应。负启发值不一定破坏可采纳性,但目标通常需h=0,且具体最优性证明还依赖其他条件。 - 原始内容:启发函数h*(n)性能可以接受,那么这时候我们就可以使用A*搜索。如果,那么表示启发式函数是可以接受的。这种限制需要满足两个方面的条件,如果h*(n)返回一个负数(表示有时候棋面状态n越过了目标状态),那么g*(n)的效果就会被抵消掉。如果h*(n)>h(n),那么A*搜索可能找不到最优解。寻找到一 - 位置:《算法技术手册》第7章《分析》(spine1607;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1570.html;u200-ch07-005)。 - 结论依据:200的03349–03352展示不同十五数码状态:一个实例较快找到解,另一个耗尽给定内存。启发式不一定总能减少搜索空间;扩展数、计算成本、重复状态和内存都需结合目标工作负载评估。 - 原始内容:十五数码问题,八数码问题的一个扩展,使用八数码问题的GoodEvaluator函数扩展时,目标状态如下: 初始状态如下: A*搜索在处理39个棋面状态之后,快速找到了一个15步的解,这个时候开放集合中还有43个棋面状态,如图7-13所示。 图 7-13 十五数码问题的A*搜索树 由于有着15步的限制 - 位置:《算法技术手册》第7章《比较》(spine1610;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1573.html;u203-ch07-005)。 - 结论依据:203的03353–03356比较八数码实验,记录平均搜索规模、路径长度及限深失败次数。特定启发式与输入下A星扩展较少不代表所有实例均如此;经验拟合不能替代理论复杂度,随机移动次数也不一定等于最短解深度。 - 原始内容:比较 广度优先搜索能够保证找到步数最少的解,但是它可能需要评价规模相当大的移动序列。深度优先搜索试着在每次搜索时能够前进更多步,它可能能够快速得到一个解,但是它也可能在搜索树的某个部分浪费大量的时间,尽管看起来这个部分不可能得到解。 我们认为比较深度优先搜索,广度优先搜索和A*搜索是值得的。使用八数