组合爆炸

简明解释

组合爆炸（combinatorial explosion）是候选数量随深度、动作数或变量数反复相乘而急剧增长的现象。若每步约有 $b$ 个选择，深度 $d$ 的路径数可达到 $b^d$ 量级。重复检测、剪枝和启发能减少实际工作，却不自动消除最坏情形；它也不表示每个小实例都难。[1, Ch. 3, Complexity discussion]

别和什么混淆

“状态很多”不等于每个状态都必须访问，也不等于固定大小实例具有某个渐近复杂度类别。

在本书中

见第 5 章：搜索——在可能性空间里找路。