# 穷举法

> 穷举法，亦称作分类证明、分类分析证明、完全归纳法或暴力法，是一种数学证明方法, 它将所求证的命题分为有限种情形或是等价情形的集合，接著依每种类型分别检验该命题是否成立，此乃一种直接证明法。 穷举法证明包括两阶段： 证明分类是完全的, 也就是说每一个待证的个例皆符合（至少）一类情形的条件； 分别对每一类情形给出证明。 计算机（電腦）的普及大大提升了穷举法的易用性，计算机专家系统可用窮舉法解答許多问题。理论上而言，穷举法适用于任何有限情形，然而因数学的大部分集合是无限的，此法鲜少能够用以导出一般的数学结论。 在柯里-霍华德同构（Curry–Howard correspondence）中，穷举法与…

- ID: m11376
- 分类: structure
- 领域: 逻辑学

## 定义

系统性地遍历所有可能选项，逐一检验，确保不遗漏。涵盖变体：穷举剔除法脚手架作用：最笨也最可靠。当问题空间可穷尽时，穷举保证找到答案（如果存在的话）。

## 机制

当解空间有限且可枚举时，逐一检验所有候选能保证不遗漏，若存在解必能找到。代价是随规模指数增长，宜用于空间可控的问题。

## 练习

第一步，界定完整且有限的候选空间。第二步，设计无重复的遍历顺序。第三步，逐一检验终止条件。第四步，空间过大时改用剪枝或启发式。

## 脚手架用法

最笨也最可靠。当问题空间可穷尽时，穷举保证找到答案（如果存在的话）。

[阅读网页](https://thinkingmodels.site/entries/detail/m11376)