CS188 Note3 学习笔记

更好的阅读体验Informed Search(启发式搜索)原文解释If we have some notion of the direction in which we should focus our search, we can significantly improve performance and “hone in” on a goal much more quickly. This is exactly the focus of informed search.Heuristics定义估计从当前状态到目标状态的距离的函数。输入state输出估计值estimate特性通常要求是低估lower bound保证 A* 的最优性。常通过“relaxed problem放宽约束的问题”得到例如忽略迷宫墙壁。例子Pacman 问题中常用Manhattan distanceManhattan(x1, y1, x2, y2) |x1 − x2| |y1 − y2|用于估计从当前位置到目标位置的距离忽略障碍。来源Relaxed Problem放宽约束得到的确切代价常见做法把原问题的一些限制移除例如去掉障碍物、允许穿墙、忽略某些约束在放宽的问题上计算真实最短代价这个代价即为对原问题的启发式估计。Example网格路径问题且只能上下左右把墙移除 → Manhattan distance 就是放松问题的真实代价。Admissibility vs. Consistency原文解释Admissibility vs. Consistency: Remember, heuristics are just functions that take search states and return numbers that estimate the cost to a nearest goal. More effective heuristics will return values closer to the actual goal costs. To beadmissible, the heuristic values must be lower bounds on the actual shortest path cost to the nearest goal (and non-negative). To beconsistent, it must additionally hold that if an action has cost c, then taking that action can only cause a drop in heuristic of at most c.两者关系所有的一致 ( consistent ) 启发式必然可采纳 ( admissible )可采纳 ( admissible ) 不一定一致 ( consistent )Admissibility可采纳性保证永远不高估真实代价Consistency一致性每走一步h的值最多只能下降这一步的costDominanceDominance 定义heuristic ha dominates hb iff ∀n: ha(n) ≥ hb(n)且二者都 admissible胜出的启发式在所有节点上都给出更高更接近真实估计 → 平均会扩展更少节点 → 更快合成技巧max(h1, h2, …)如果 h1, h2 都是 admissible或 consistent则 h max(h1, h2) 仍然是 admissible或 consistent。因为 max of numbers in [0, h*(n)] 仍在同一区间内。应用常把多种较弱启发式结合成一个更强的启发式例如 Manhattan linear conflict。