Louis Aeilot's Blog
·
CS188 搜索讲座笔记 II
内容提要
UC伯克利CS188讲座笔记介绍了启发式搜索方法。启发式用于估计到达目标的距离，贪婪搜索选择启发式值最低的节点，但不保证最优解。A*搜索结合总成本估计，若启发式可接受，则保证完整性和最优性。启发式的支配性和一致性是优化搜索的关键条件。
关键要点
-
启发式搜索用于估计到达目标状态的距离，通常是放宽约束后的问题解决方案。
-
贪婪搜索选择启发式值最低的节点进行扩展，但不保证找到目标状态或最优解。
-
A*搜索结合了总成本估计，若启发式可接受，则保证完整性和最优性。
-
可接受性是A*树搜索获得最优解的条件，需满足启发式函数的约束。
-
图搜索通过跟踪已扩展的状态，避免重复扩展，提高搜索效率。
-
启发式的支配性意味着一个启发式在所有节点上对目标距离的估计优于另一个启发式。
-
一致性启发式的估计总是小于或等于到邻接节点的实际距离加上邻接节点的估计距离，确保A*搜索的最优路径。
延伸解读
启发式搜索的应用场景
启发式搜索在解决复杂问题时非常有效，尤其是在约束条件较多的情况下。通过放宽约束，启发式可以帮助快速找到可行解，适用于路径规划、游戏AI等领域。理解启发式的选择对搜索效率至关重要。
贪婪搜索的局限性
尽管贪婪搜索简单易实现，但其不保证找到最优解的特性使其在某些情况下不够可靠。特别是在启发式函数不佳时，可能导致搜索陷入局部最优。因此，在选择搜索策略时需谨慎评估启发式的质量。
A*搜索的优势与条件
A*搜索结合了启发式和成本估计，能够保证找到最优解，但前提是启发式函数必须是可接受的。理解可接受性和一致性对优化搜索过程至关重要，确保搜索的完整性和效率。
延伸问答
什么是启发式搜索？
启发式搜索是用于估计到达目标状态的距离，通常是放宽约束后的问题解决方案。
贪婪搜索有什么特点？
贪婪搜索选择启发式值最低的节点进行扩展，但不保证找到目标状态或最优解。
A*搜索如何保证最优性？
A*搜索结合总成本估计，若启发式可接受，则保证完整性和最优性。
什么是启发式的支配性？
启发式的支配性意味着一个启发式在所有节点上对目标距离的估计优于另一个启发式。
一致性启发式的特点是什么？
一致性启发式的估计总是小于或等于到邻接节点的实际距离加上邻接节点的估计距离。
图搜索与树搜索有什么不同？
图搜索通过跟踪已扩展的状态，避免重复扩展，提高搜索效率，而树搜索不进行此优化。
