10.1 枚举法

10.1 枚举法

问题求解中常用的一种算法设计方法是枚举策略。给定问题 P，如果知道 P 的可能解构 成一个有限集合 S = {s1, s2, ..., sn}，则可以逐一列举每个 si，检验它是否确实是 P 的解，这 就是枚举法。枚举法简单而直接，算法容易设计实现，但当可能解集合 S 很大时，枚举策 略的效率很差。实际使用枚举法时，经常利用各种已知条件来从 S 中排除掉一部分不可能 情形，从而优化枚举过程。下面通过几个例子来说明枚举策略在设计算法中的应用。

线性搜索

首先看一个程序设计中常见的问题——搜索（或称查找）问题：给定数据集合 D，在 D 中查找指定数据 x。

搜索问题看上去很容易解决，一个显而易见的做法是：反复从 D 中读取下一个数据， 看看它是否 x，搜索结果是要么找到 x，要么发现 D 中没有 x。然而，这个“算法”是有问 题的，因为它需要一个关键操作——“读取取下一个数据”，而“下一个”未必是良定义的。 打个比方，如果一群人站成一排，当我们要从中找出张三时，可以采取按排队次序逐个询问 的策略。但如果这群人散乱无规则地站在一起，我们该如何循着一个有条理的过程找出张三 来呢？如何决定“下一个”要询问的人？

可见，要想在一个数据集合中找到指定数据，就必须能够按某种系统化的方式逐个列举 集合元素，并与指定数据进行比较。这就是枚举策略在搜索问题中的应用。

如果将大量数据存储在一个列表中，则使用枚举策略很合适，因为列表是通过位置索引 来访问其中数据成员的，“读取下一个数据”是良定义的操作，只要将当前位置索引加 1 即 可得下一个数据的索引。下面定义的函数 find()实现了这种搜索策略：给定数据列表 list 和 需要查找的数据 x，逐个取出 list 的成员并与 x 进行比较。如果某个成员就是 x，则返回该 成员在列表中的位置索引；如果 list 中没有 x 则返回-1。

>>> def find(list,x):
for i in range(len(list)): if list[i] == x:
return i return -1
>>> find([2,4,6,8],6) 2
>>> find([2,4,6,8],7)
-1

find()函数对列表 list 从头到尾进行扫描，扫描过程中检验每一个成员是否 x，这个算法 称为线性搜索（linear search）算法。线性搜索算法很容易设计实现，而且当数据量不太大时，算法的性能也还可以。更重要的是，由于线性搜索是枚举每一个数据成员，因此适用于 无序数据集合，即数据没有按特定的大小次序排列。

然而，当数据量很大时，逐个枚举集合中的数据就变得非常低效。这时只能通过更好地 组织数据，利用额外信息来提高搜索效率，尽量避免逐个检查所有数据。例如，假设列表数 据从小到大有序排列，那么在枚举过程中一旦发现当前取出的数据大于 x，就不必再继续搜 索了，可以直接下结论说找不到 x。这种改进可以提高线性搜索算法的性能，但改善得很有 限。事实上，在数据有序的情况下，存在比线性搜索算法好得多的算法（见 10.2）。

线性搜索算法只适用于“一维”搜索空间，即所有数据排列成一排的情形。考虑在如下 矩阵中查找某个数据的问题：

这时显然无法直接采用线性搜索算法。在类似矩阵这样的“二维”搜索空间中，如何枚举每 一个数据呢？这个问题其实在第 3 章中介绍循环语句时就讨论过，为了遍历（即枚举）这样 的二维空间，可以采用嵌套的循环语句。例如下面这个 find2D()函数实现了在 row 行、col 列的矩阵 matrix 中查找数据 x 的枚举算法：

>>> def find2D(matrix,row,col,x): 
    for i in range(row):
        for j in range(col):
            if matrix[i][j] == x: 
                return (i+1,j+1)
        return -1
>>> find2D([[1,2,3],[4,5,6]],2,3,6) (2, 3)
>>> find2D([[1,2,3],[4,5,6]],2,3,7)
-1

显然，这个做法可以扩展到更多维的搜索空间，利用 n 层嵌套循环即可枚举 n 维搜索空 间中的数据。

求解不定方程

有时问题的所有可能解并没有像上例那样明确地存储在某个具体集合（如列表）中，而 是构成一个无形的搜索空间，那该如何枚举可能解呢？这需要具体问题具体分析，根据问题 的特点设计枚举方式。下面是一个典型的例子。

中国古代数学著作中有一道“百钱买百鸡”问题：假设公鸡每只 5 元钱，母鸡每只 3

元钱，鸡雏每三只 1 元钱，用一百元钱买了一百只鸡，问公鸡、母鸡和鸡雏各买了几只？具 备初等代数知识的人都不难列出如下方程组来求解这个问题：

x + y + z = 100
5x + 3y + z/3 = 100

其中 x、y、z 分别表示公鸡、母鸡和鸡雏的个数。 此方程组有三个未知数却只有两个方程式，属于数学中所称的不定方程。人工求解不定

方程通常会利用方程变形、未知数代换以及分析各种约束条件等技巧，而绝不会采用枚举所 有可能解进行检验的方法，因为可能解构成的空间通常非常庞大。然而，计算机的优点恰恰 在于能够高速地、机械地执行大量的检验任务，因此采用枚举策略来解不定方程是简单而直 接的做法。问题是如何枚举各种可能解呢？对于百钱买百鸡问题，显然只需为三个未知数做 各种可能的赋值，然后检查是否满足上述两个方程式即可。各未知数的可能值都在 100 之内（因为只买了 100 只鸡），所以利用枚举法很容易得到下列程序：

>>> for x in range(100): 
        for y in range(100):
            for z in range(100): 
                t = x + y + z
        m = 5*x + 3*y + z/3
        if t == 100 and m == 100:
            print "x=",x,",y=",y,",z=",z
x=  0  ,y=  25  ,z=  75 
x=  3  ,y=  20  ,z=  77 
x=  4  ,y=  18  ,z=  78 
x=  7  ,y=  13  ,z=  80 
x=  8  ,y=  11  ,z=  81 
x=  11  ,y=  6  ,z=  83
x=  12  ,y=  4  ,z=  84

采用枚举策略时应当尽量减小可能解集合，以便提高枚举效率。上面这个程序的效率显 然太差，因为三重嵌套循环实际上要枚举 100×100×100 种 x、y、z 组合。其实稍加思考就 能找到减小需要检验的可能解的数目的方法。首先，不需要三层嵌套循环，因为当 x 和 y 的值给定，z 的值就确定了（即 100–x–y），没有必要再去枚举 z；其次，x 的可能值不超 过 20（否则钱不够），同理 y 的可能值不超过 33；最后，依题意每种鸡应当都至少买 1 只， 没有必要考虑等于 0 的情形。将这些分析落实到编程中，即可得效率更高的代码：

>>> for x in range(1,20): 
        for y in range(1,33):
            z = 100 - x - y
            m = 5*x + 3*y + z/3 
            if m == 100:
                print "x=",x,",y=",y,",z=",z
x=  3  ,y=  20  ,z=  77 
x=  4  ,y=  18  ,z=  78 
x=  7  ,y=  13  ,z=  80 
x=  8  ,y=  11  ,z=  81 
x=  11 ,y=  6   ,z=  83
x=  12 ,y=  4   ,z=  84

利用问题中的各种约束条件往往可以减少搜索空间或者优化枚举过程。例如，假设为 “百钱买百鸡”问题附加一个条件“尽量多买公鸡”，那么可以这样优化算法：最外层对 x 的循环中改用 range(20,0,-1)，以便尽快找到满足条件的值，得到第一个解之后就可以 终止程序，不必再找其他解了。

通过以上例子，我们看到枚举算法的核心思想是对问题的每一个可能解进行检验，看看 是否满足特定条件，这个枚举过程在编程时是通过循环语句和条件语句实现的。对于一些复 杂问题，如果嵌套循环的层数不确定或者层数太多，直接使用循环语句和条件语句实现枚举 检验是不合适甚至不可能的，这时可以考虑采用递归技术（见 10.2）。

当问题规模较大时，可能解的空间也很大，采用枚举策略会导致效率很差。但是，鉴于 枚举算法设计简单，调试也容易，对于规模较小的问题是很好的策略。即使对于大规模的复 杂问题，枚举策略也可以作为整体求解算法的子算法出现。

最后总结一下采用枚举策略设计算法的一般步骤：

(1) 确定枚举对象、枚举范围和判定条件；

(2) 枚举各可能解，逐一验证是否所需的问题解。

(3) 尽量减小枚举范围，提高算法效率。