边缘集
- 不管用什么搜索策略，边缘集本质上都是以优先队列的形式存储的，所使用的策略仅仅决定了优先级的设置方式。
- 针对特定算法的底层数据结构替换：
- 如果专注于 DFS ，可以用栈来实现。
- 如果专注于 BFS，可以用普通队列来实现。
- 虽然这种针对性的数据结构替换能略微提升运行效率，但会降低底层代码实现的统一性。
启发式搜索 (Informed Search)
- 之前提到的统一成本搜索会盲目地向各个方向均匀搜索。
- 为了提高效率，我们在搜索时加入“关于目标位置的额外信息”，即Informed Search，也被称为启发式方法 (Heuristics)。
- 之前都是构建一个搜索问题的抽象模型然后运行算法；而使用启发式方法，还需要额外加上一步——设计一个启发式函数。
Greedy Search
- 优先扩展你认为最接近目标状态的节点。
- 启发式方法在这里的作用，就是作为衡量每个状态到目标状态距离的评估工具。
A* Search
- 结合了 Uniform Cost Search 和 Greedy Search 的优势。
- 根据该节点的 g (实际回溯成本) + h (预估向前成本) 来判断优先级。
- 最优性条件 (Optimality)：要保证找到最优解，启发式必须是一个乐观的启发式 (Admissible Heuristic)，即估计的成本必须小于或等于实际成本。
- 对于吃豆人寻路，启发式可以是曼哈顿距离。
- 对于翻煎饼问题，启发式可以是最大错位煎饼的编号。
- 与 Uniform Cost 相比，A* 依然会在各个方向上有所扩展，但会优先朝向目标方向推进。
- A* 算法通常是首选的规划算法，被广泛应用于电子游戏 (Video games)、路由规划 (Routing)、语音识别解码 (Decoding in speech recognition) 以及机器翻译 (Machine translation) 等领域。
搜索终止的核心原则
- 无论使用哪种搜索算法，极其重要的一点是只有在目标节点出队时才停止，而不是在目标节点刚被发现（入队）时停止。
Graph Search
- 图搜索会记录一个已扩展的节点列表，并避免重复扩展它们。
- 用 A* 实现图搜索并保证最优解，要求启发式不仅要是乐观的，还必须是一致的 (Consistent)。
小结
- A* 算法同时运用了回溯成本和向前成本。
- 启发式函数的设计是提升整个算法性能的关键因素。