指数爆炸Combinatorial Explosion

当多个选择可以自由搭配，每增加一项决策，候选方案就成倍增长。

再快的计算机，也无法把国际象棋的所有后续走法逐一看完。1997 年，纽约，卡斯帕罗夫与 IBM 的“深蓝”交锋，最终以 2.5 比 3.5 输掉六局比赛。深蓝每秒能评估约两亿个棋局，却仍须选择搜索哪些分支、舍弃哪些分支。一种走法后面接着对手的多种回应，每种回应又接着新的选择。多往后看几步，待检查的棋局就成倍增加。赢棋靠的既有算力，也有让算力集中到值得检查的走法上。

为什么成立

新选择会乘上旧组合

十个开关各有开、关两种状态，合起来就有 1,024 种配置。加到二十个，配置超过一百万种；加到三十个，就超过十亿种。新增一个开关，会把已有的每种配置都复制成两个版本。

当每一步都有 $b$ 个选择，且所有搭配都允许时，连续做 $n$ 步选择，候选数就是：

$N = b^{n}$

白话说，选择数要连乘：每多一步，已有候选数就再乘一次 $b$ 。选项之间若有约束，实际候选会减少；若每一步可选的数量不同，就把各步的数量相乘。

加快检查只能买到有限的规模

穷举的耗时等于候选数乘以每次检查的耗时。六十个二选一开关有约 $1.15 \times 1 0^{18}$ 种配置。即使每秒检查十亿种，全部查完仍需约三十六年。把机器提速 1,024 倍，在二选一问题里也只够多处理十个开关。

先排除整批方案才有大收益

减少一个维度，能同时删掉大量候选。先用预算、交期、合法性等硬条件排除方案，再检查剩余组合；搜索途中若能证明某条分支无论怎样延伸都不达标，就整条剪掉。排列也会爆炸：十件事的全部先后顺序有 $10!$ 种，即 3,628,800 种；阶乘增长甚至比固定底数的指数更快。

出处

这一现象来自组合数学，在计算机搜索中成为核心难题，并无公认的单一提出者。1950 年，克劳德·香农在《计算机下棋的程序设计》中估计，典型国际象棋对局的走法序列数量约为 $1 0^{120}$ ，说明逐一穷举为何行不通。

换个领域看

商业物流

送货顺序太多

配送员要送的地址一多，逐一比较全部路线就失去可行性。UPS 于 2013 年开始推广 ORION 路线优化系统，用算法安排配送顺序。仅十个不同地址就有 3,628,800 种访问顺序。地址继续增加，还叠加收货时间等限制；ORION 用启发式搜索寻找更好的路线，避免逐一检查全部访问顺序。

投资

持仓组合翻倍

投资者若从二十只股票里任意选择持有或不持有，候选组合已超过一百万种。从三十只里选，就超过十亿种，仓位比例还没算进去。实际筛选时，先剔除读不懂业务或财务不达标的股票，再限定持仓数量，能大幅缩小候选范围。逐个回测所有组合，预算会先耗在枚举上。

个人生活

装修搭配失控

一对夫妻在装修展厅挑材料，给地板、墙漆、橱柜等八项各留三个备选，回家便有 6,561 套搭配可比。若只按总体效果逐套比较，每套看一分钟，就要花一百多个小时。先按总预算与尺寸排除不合格搭配，再固定已经满意的几项，比不断添备选更接近能落地的方案。

遇事时问自己

我面对的是一张选项清单，还是必须把各项搭配起来评估的组合？
增加一个选项或决策步骤，会让候选总数增加多少？
按每个方案的检查成本，全部查完要花多少时间或钱？
哪些硬条件能在详细评估前排除整批方案？
这件事必须证明全局最优，还是找到满足明确要求的方案就够了？

边界与误用

候选很多，只有在必须逐个检查时，才会直接变成计算负担。若各项得分可以相加、彼此没有约束，逐项选最高分就能得到整体最优；组合再多也不必全查。硬约束也能让大量搭配根本不成立。常见误用是看到几个因素就宣称“指数爆炸”： $n$ 项之间的两两关系只有 $n (n - 1) /2$ 个，属于平方增长。另一个误用是把穷举困难说成无解；结构清楚的问题仍可用算法高效求解。若任务要求证明最优，凭经验删分支会丢失这个保证。

练一练

视频剪辑软件的测试负责人要检查滤镜组合。旧版有16个滤镜，每个可独立开启或关闭，所有搭配都允许，每种配置的检查成本相同。新版增加了4个同样的滤镜，测试设备每秒能检查的配置数也翻了一倍。发布前仍须测完全部配置。

新版完整测试的耗时会怎样变化？

准备支付大学学费的家长，把存款分成8笔，每笔金额和到期日已经固定。每笔都有3款到期日合适的定期存款可选，利息已知，没有额外费用、额度限制或搭配优惠。各笔选择互不影响，家长只想让到期收到的总利息最高。

哪种判断最站得住？

准备七天露营的徒步者，要为每天选一份晚餐，每天有4种合格餐包可选。餐包的价格和个人喜好评分已列好，总评分按天相加，目标是在500元内选出评分最高的七天菜单。所有价格都为正，没有满减或搭配折扣，程序按天尝试各种菜单。

哪一步既能减少搜索，又保留找到最高总评分的保证？