組合搜索

在計算機科學和人工智能中，組合搜索研究的是解決一般認為很難的問題實例的搜索算法，方法是有效地探索這些實例的通常很大的解決空間。組合搜索算法通過減少搜索空間的有效大小或采用啟發式方法來實現這種效率。一些算法保證能找到最優解，而另一些算法可能只返回在所探索的狀態空間部分發現的最佳解。

這樣的問題被認為在一般情況下是無法有效解決的。然而，復雜性理論的各種近似值表明，這些問題的某些實例（例如小實例）可以被有效解決。事實的確如此，而且這些實例往往具有重要的實際影響。

解決組合搜索問題的常見算法包括。

阿爾法-貝塔修剪分支與約束最小值觀察期觀察期是組合搜索的一個重要組成部分，它大致上規定了代表問題的圖被探索的深度。

對這些圖進行天真的廣度優先搜索會迅速消耗任何現代計算機的所有內存。通過設置一個特定的超前限制，算法的時間可以被仔細控制；隨著超前限制的增加，其時間也會呈指數級增長。