Louis Aeilot's Blog
·
CS188 搜索讲义 II
内容提要
本文介绍了UC Berkeley CS188课程第三讲，重点讨论启发式搜索方法，包括贪婪搜索和A*搜索。启发式用于估计到达目标的距离，贪婪搜索选择启发值最低的节点，而A*搜索选择总成本最低的节点。A*搜索在启发式满足可接受性时是最优的。文中还涉及图搜索、启发式的主导性和一致性等概念。
关键要点
-
启发式搜索用于估计到达目标状态的距离。
-
贪婪搜索选择启发值最低的节点进行扩展，但不保证找到目标状态，也不一定是最优的。
-
A*搜索选择总成本最低的节点进行扩展，且在启发式满足可接受性时是完整且最优的。
-
可接受性是A*树搜索的最优性条件，要求启发式函数不超过真实最优前向成本。
-
图搜索通过跟踪已扩展的状态，避免重复扩展，提高效率。
-
主导性指一个启发式在所有节点上估计的目标距离优于另一个启发式。
-
一致性是指启发式的估计始终小于或等于到邻接节点的实际距离加上邻接节点的启发式估计。
延伸解读
启发式搜索的实用性
启发式搜索在解决复杂问题时具有重要的实用性。通过估计到达目标的距离，启发式可以帮助智能体更有效地选择扩展节点，从而提高搜索效率。理解启发式的设计和应用，可以帮助开发者在实际项目中优化算法性能。
贪婪搜索与A*搜索的比较
贪婪搜索虽然简单，但并不保证找到最优解，适合对时间要求较高的场景。而A*搜索在启发式满足可接受性时，能够保证找到最优解，适合对结果精度要求较高的应用。选择合适的搜索策略需根据具体问题的需求进行权衡。
启发式的主导性与一致性
启发式的主导性和一致性是评估其有效性的关键指标。主导性确保某一启发式在所有节点上都优于另一启发式，而一致性则保证启发式估计的合理性。理解这些概念有助于选择和设计更有效的启发式函数，提升搜索算法的整体表现。
延伸问答
什么是启发式搜索？
启发式搜索是用于估计到达目标状态的距离的方法，通常通过解决放宽约束的问题来实现。
贪婪搜索和A*搜索有什么区别？
贪婪搜索选择启发值最低的节点进行扩展，但不保证找到目标状态；而A*搜索选择总成本最低的节点，且在启发式满足可接受性时是完整且最优的。
A*搜索的可接受性条件是什么？
A*搜索的可接受性条件要求启发式函数不超过真实最优前向成本，以确保其最优性。
什么是图搜索？
图搜索是一种优化的搜索方法，通过跟踪已扩展的状态，避免重复扩展，从而提高效率。
启发式的主导性是什么意思？
启发式的主导性指一个启发式在所有节点上估计的目标距离优于另一个启发式，意味着前者在估计上更准确。
一致性在启发式搜索中有什么重要性？
一致性确保启发式的估计始终小于或等于到邻接节点的实际距离加上邻接节点的启发式估计，从而保证搜索的有效性。
