Louis Aeilot's Blog
·
CS188 搜索讲座笔记 II
💡
原文英文，约900词，阅读约需3分钟。
📝
内容提要
UC伯克利CS188讲座笔记介绍了启发式搜索方法。启发式用于估计到达目标的距离，贪婪搜索选择启发式值最低的节点，但不保证最优解。A*搜索结合总成本估计，若启发式可接受，则保证完整性和最优性。启发式的支配性和一致性是优化搜索的关键条件。
🎯
关键要点
- 启发式搜索用于估计到达目标状态的距离，通常是放宽约束后的问题解决方案。
- 贪婪搜索选择启发式值最低的节点进行扩展，但不保证找到目标状态或最优解。
- A*搜索结合了总成本估计，若启发式可接受，则保证完整性和最优性。
- 可接受性是A*树搜索获得最优解的条件，需满足启发式函数的约束。
- 图搜索通过跟踪已扩展的状态，避免重复扩展，提高搜索效率。
- 启发式的支配性意味着一个启发式在所有节点上对目标距离的估计优于另一个启发式。
- 一致性启发式的估计总是小于或等于到邻接节点的实际距离加上邻接节点的估计距离，确保A*搜索的最优路径。
❓
延伸问答
什么是启发式搜索？
启发式搜索是用于估计到达目标状态的距离，通常是放宽约束后的问题解决方案。
贪婪搜索有什么特点？
贪婪搜索选择启发式值最低的节点进行扩展，但不保证找到目标状态或最优解。
A*搜索如何保证最优性？
A*搜索结合总成本估计，若启发式可接受，则保证完整性和最优性。
什么是启发式的支配性？
启发式的支配性意味着一个启发式在所有节点上对目标距离的估计优于另一个启发式。
一致性启发式的特点是什么？
一致性启发式的估计总是小于或等于到邻接节点的实际距离加上邻接节点的估计距离。
图搜索与树搜索有什么不同？
图搜索通过跟踪已扩展的状态，避免重复扩展，提高搜索效率，而树搜索不进行此优化。
➡️
