组合搜索

在计算机科学和人工智能中，组合搜索研究的是解决一般认为很难的问题实例的搜索算法，方法是有效地探索这些实例的通常很大的解决空间。组合搜索算法通过减少搜索空间的有效大小或采用启发式方法来实现这种效率。一些算法保证能找到最优解，而另一些算法可能只返回在所探索的状态空间部分发现的最佳解。

这样的问题被认为在一般情况下是无法有效解决的。然而，复杂性理论的各种近似值表明，这些问题的某些实例（例如小实例）可以被有效解决。事实的确如此，而且这些实例往往具有重要的实际影响。

解决组合搜索问题的常见算法包括。

阿尔法-贝塔修剪分支与约束最小值观察期观察期是组合搜索的一个重要组成部分，它大致上规定了代表问题的图被探索的深度。

对这些图进行天真的广度优先搜索会迅速消耗任何现代计算机的所有内存。通过设置一个特定的超前限制，算法的时间可以被仔细控制；随着超前限制的增加，其时间也会呈指数级增长。