穷举法

定义

穷举法的核心做法是从问题全部可能解的集合中依次取出元素，用题目给定的约束条件判断其取舍，能够使命题成立者即为问题的解^[2]。在数学与计算机科学的理论表述中，对一个集合的枚举，就是列出某个有穷序列集全部成员的过程，或者对某一类特定对象进行计数^[1]。使用这种方法通常需要两个前提：候选答案的个数能够事先确定，候选答案的取值范围在求解之前已有一个明确的集合^[5]。

按照答案的数据形式，列举方式可分为三类：答案与自然数直接对应时按顺序列举；答案是一组数的排列时作排列列举；答案是若干元素的组合时作组合列举，组合不考虑元素次序^[2]。以古代百鸡问题为例，公鸡数量只能在 0 至 20 之间、母鸡数量只能在 0 至 33 之间取值，逐个试算这些整数组合即可筛出符合条件的方案，该题在现代常被视为求不定方程整数解的典型例子^[2][6]。

原理

采用穷举法求解的一般思路分两步：先确定枚举对象、枚举范围和判定条件，再把可能的解逐个列举出来并验证其是否为问题的解^[1]。程序上，它一般表现为循环与判断语句的组合，循环负责产生候选状态，判断语句负责筛选^[1]。

更一般地，穷举过程可以拆成四类操作：生成当前实例的第一个候选解、由当前候选解生成下一个、检验候选解是否满足要求、输出被确认的解；当不再有候选解时循环结束^[4]。其时间开销可表示为 $T = M \times C$，其中 $M$ 是状态总数、$C$ 是考察单个状态所需的耗时^[1]。

解空间的结构可能是线性表、集合、树或者图，不同结构需要搭配相应的搜索策略，例如线性解空间可以用线性搜索，树状或图状解空间可以用广度优先搜索、深度优先搜索^[7]。如果搜索过程中能借助已知信息跳过明显不可能的状态，就属于启发式搜索，其收敛速度通常快于机械式遍历^[7]。

flowchart TD

A[确定枚举对象、范围与判定条件] --> B[生成一个候选解]

B --> C{满足判定条件?}

C -- 是 --> D[记录该解]

C -- 否 --> E[尝试下一个候选解]

D --> E

E --> F{还有候选解?}

F -- 是 --> B

F -- 否 --> G[输出结果]

发展历程

中国古代已经出现依靠逐一列举求解的问题。约成书于公元 5 至 6 世纪的《张邱建算经》，卷下第 38 题为百鸡问题，原书只给出若干组答案而没有记录解法^[8][9]。该题后来成为循环结构与穷举思想的编程教学案例^[6]。

19 世纪，分类列举的思路也被用于四色定理的证明。1879 年肯普发表了一个把地图着色情形分开考察的证明，1890 年赫伍德指出其中存在错误，四色问题随之重新成为猜想^[10][11]。由于必须考察的情形数量庞大，仅靠人工已经无法完成逐一判定^[11]。

1976 年，阿佩尔与哈肯把这项工作交给计算机完成：他们先论证所有可能的地图必然包含一个由 1936 种构型组成的不可避免集合，再用程序逐一验证每种构型都可以归约^[11][10]。该验证累计占用约 1200 小时机器时间、执行上百亿次逻辑判断，证明于 1977 年正式发表^[11]。这是第一个主要依赖计算机验证的重大数学定理，也因计算过程难以人工复核而一度引起争论^[10]。

此后四色定理的机器证明不断被精简：1997 年罗伯逊等人把所需配置数缩减到 633 个，2000 年前后又有研究者用 Coq 证明辅助工具对该证明作了形式化验证^[10]。

应用

在数学领域，穷举法用于求解不定方程以及处理计数问题；排列组合的两大计数原理和排列数公式，在推导时就依赖逐一列举各种情形^[12]。在计算机领域，它常用于查找、搜索以及规模不大的组合优化问题^[7]。

密码分析是穷举法最主要的应用场景之一。蛮力攻击又称穷举攻击、暴力破解，其做法是用程序不断尝试各种可能的口令，直到找出正确的一个；对一个已知由四位数字组成的口令，最多尝试 9999 次即可命中^[13]。为压缩尝试范围，还出现了字典攻击，即利用英文单词、生日数字、常见口令等预置清单来猜测^[13]。为提高速度，一些机构制造了专用计算机，例如用于破解 DES 的「深译」以及 IBM 为纽约大学和美国军方研制的「WindsorGreen」^[13]。

在信息学竞赛与程序设计中，当题目规模有限、能够在规定的时间与空间限制内得出结果时，枚举法由于思路简单、编写和调试方便而常被优先选用^[3]。它还可以充当基准方法，用来核对其他算法或启发式算法的结果是否可靠^[4]。

局限

穷举法的主要代价是运算量。问题规模变大时，嵌套循环的层数随之增加，程序的执行速度会明显下降^[1]。当候选解数量随输入规模呈指数或阶乘式增长，即出现组合爆炸时，穷举在时间和存储两方面都会变得不可行^[4]。

这种增长可以用具体例子说明。若要求出一个十进制数的全部约数，候选数就有该数本身那么多：当它是 16 位十进制数时，搜索至少需要执行 10^15 条计算机指令，在普通计算机上要花几天；若它是任意的 64 位自然数（平均 19 位十进制），搜索时间约需十年^[4]。

在口令破译中，问题更为突出。一个使用数字与大小写字母共 62 种字符、长度为 10 位的口令，组合数约为 8.39×10^17，并且每增加一位，组合数就成倍上升^[13]。因此在密码学的评价中，穷举一般不被看作有效的破解途径^[13]。

为减轻负担，实践中常采取若干措施：用剪枝提前放弃不可能产生最优解的分支，减少枚举变量及其取值范围，避免重复计算，把原问题化为更小的子问题，或者引入其他算法配合^[1][7]。这些改进虽然能显著提速，但已经不再是单纯意义上的穷举^[7]。

参见

• 回溯法 —— 在枚举解空间的过程中及时舍弃不可能的分支，可视为对穷举的改造。

• 动态规划 —— 通过保存子问题的结果避免重复枚举，常用来替代代价过高的穷举。

• 分支限界法 —— 在穷举搜索中借助估值与界限剪除劣解分支的求解范式。

• 启发式算法 —— 不保证最优，但在穷举不可行的规模上仍能给出可用解。

• 词典攻击 —— 用预置清单缩小尝试范围的穷举变体，常用于口令破解。

• 计算复杂性 —— 衡量穷举等算法的耗时随问题规模增长快慢的理论工具。