知识卡片
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*搜索是值得的。使用八数