Louis Aeilot's Blog
·
CS188 搜索讲义 II
💡
原文英文，约800词，阅读约需3分钟。
📝
内容提要
本文介绍了UC Berkeley CS188课程第三讲，重点讨论启发式搜索方法，包括贪婪搜索和A*搜索。启发式用于估计到达目标的距离，贪婪搜索选择启发值最低的节点，而A*搜索选择总成本最低的节点。A*搜索在启发式满足可接受性时是最优的。文中还涉及图搜索、启发式的主导性和一致性等概念。
🎯
关键要点
- 启发式搜索用于估计到达目标状态的距离。
- 贪婪搜索选择启发值最低的节点进行扩展，但不保证找到目标状态，也不一定是最优的。
- A*搜索选择总成本最低的节点进行扩展，且在启发式满足可接受性时是完整且最优的。
- 可接受性是A*树搜索的最优性条件，要求启发式函数不超过真实最优前向成本。
- 图搜索通过跟踪已扩展的状态，避免重复扩展，提高效率。
- 主导性指一个启发式在所有节点上估计的目标距离优于另一个启发式。
- 一致性是指启发式的估计始终小于或等于到邻接节点的实际距离加上邻接节点的启发式估计。
❓
延伸问答
什么是启发式搜索？
启发式搜索是用于估计到达目标状态的距离的方法，通常通过解决放宽约束的问题来实现。
贪婪搜索和A*搜索有什么区别？
贪婪搜索选择启发值最低的节点进行扩展，但不保证找到目标状态；而A*搜索选择总成本最低的节点，且在启发式满足可接受性时是完整且最优的。
A*搜索的可接受性条件是什么？
A*搜索的可接受性条件要求启发式函数不超过真实最优前向成本，以确保其最优性。
什么是图搜索？
图搜索是一种优化的搜索方法，通过跟踪已扩展的状态，避免重复扩展，从而提高效率。
启发式的主导性是什么意思？
启发式的主导性指一个启发式在所有节点上估计的目标距离优于另一个启发式，意味着前者在估计上更准确。
一致性在启发式搜索中有什么重要性？
一致性确保启发式的估计始终小于或等于到邻接节点的实际距离加上邻接节点的启发式估计，从而保证搜索的有效性。
➡️
