用穷举测试是较现实的测试方法
-
穷举搜索法：
穷举
搜索法是编程中常用到的一种方法，
通常在找不到解决问题
的规
律时对可能是解的众多候选解按某种顺序进行逐一枚举和检验，
并从中找出那些符合要求
的候选解作为问题的解。
穷举测试：
穷举测试：
亦称完全测试，
即程序运行
的各个可能分支都应该调
试到。穷举法，
可视为最简单的搜索。
即是在一个可能存在可行状态
的状态全集中依次遍历所有的元素，并判断是否为可行状态
状态全集：一堆苹果
可行状态：蓝色的苹果
噢，好，我们
现在已经抽取了两个基本概念，迫不及待要开始穷
举了，但……怎么做呢？穷举的关键是
“依次遍历”，即做到不重、
不漏。
呃，
我们可以让听话的苹果们排成一行，
放在“苹果数组”中，
然
后呢，我们就可以按照
0
号苹果、
1<
/p>
号苹果、
2
号苹果、
...
、
n
号
苹果这样的顺序成功遍历。好，我们解决了遍历苹果的问题……慢，
我们现在是设计
一个算法的抽象模型，
如果一切待穷举的对象都已经
活生生地摆
在那里，
当然有可能把它们全部收集起来并排队，
但如果
开始的时候我们并不知道所有要穷举的对象，
比如我们或许要通过一<
/p>
台安装在探测飞船内的计算机在全宇宙范围内穷举出除地球以外有
生命的星球，
那么我们的计算机可能是随着飞船的前行方能不断地得
到新星球的信息，而不是停在地球的时候就获得全宇宙的星球信息
（就算可能，
内存或许也装不下如此大的数据量——哪怕宇宙真的是
有限“大”的）
。
< br>所以我们不应当要求穷举进行之前就能获得状态全
集中的所有状态，
这样一来，
我们的“苹果数组”计划就宣告流产了。
现在再看看我们激动人心的星球搜索计划：
它并没有把所有星球收罗
排队，那么它成功的关键在哪里？在于飞船能否以适当的路径“光
顾”完所有的星球
；
我们把这个条件加强一下：
飞船每次到达一个星
球，都会看到星球上立着一个方向标，标示下一个星球的方位；而假
定这样的
标示保证飞船能够不重不漏地飞临宇宙中的所有星球。啊
喔……你是不是觉得我这是在异
想天开？哦，没关系，大不了我们不
搜索星球了，
而除此之外的
很多现实穷举问题都可以满足这个加强条
件。嗯，我承认本文讨论的是满足这个加强条件
的稍稍狭义的穷举：
它必须保证在知道一个状态的前提下能获得一个新状态，
并且这样的
“状态链”刚好能遍历整个状态全集。
我们称从当前状态获得并转到
下一个状态的过程为“状态跳转”（我是想用“状态转移”
的，嗨，
可惜它会与动态规划算法的术语相混淆）：
状态跳转
：
根据当前得到的苹果，
按一定的“遍历算法”取得下一个苹果；
这个算法保证不重不漏地取遍苹果堆中的所有苹果，
只要所取的第一
个苹果也是按算法定义给出的
很显然，对于不同的穷举任
务，都会有不同的遍历算法，所以这
样一来我们就得将其实现下放给调用我们“穷举算法
库”的用户们
了。
不过考虑到这的确是由于问题的多样性所决定
的，
因而这个要求
应当是合理的。
嗯啊，现在我们已经有了苹果源，
目标苹果，乃至遍历苹果的方
案（用户提供），接下来还差一个判断标准，这个倒简单了
：
判断标准
：当前苹果是否为蓝色的苹果
下一步，我们就可以考虑“the classof
穷举算法”
的具体实现
了。我们把这个
class
的名字定义为
WalkThrough.
首先，让我们注意到
，“状态”是一个很重要的概念：不同的穷
举问题都有彼此不同的状态，在苹果问题中，
“状态”是苹果，它包
含了苹果颜色或者更多的信息；
而在星球
搜索计划中，
“状态”则是
星球，它可能包含该星球的体积、平
均密度、温度、是否有大气、是
否探测到水、星表活动状况等一系列丰富得惊人的信息。
因此，不同
状态
(state)
对应不
同的数据类型，要让
WalkThrough
能处理它们，
有必要使用模板，于是我们的最初定义如下：
template
class WalkThrough
;
万事开头难，
但现在我们显然已经
开了一个不错的头，
嗯，
继续。
在考虑
具体实现之前，
先幻想一下我们的
WalkThrough
能为用户提
供怎样的服务——当然，
它的本
职工作是找到并返回可行状态，
因此
它似乎应该有一个类似于<
/p>
getFilter()
的成员函数。问题是，如果可行
状态不止一个时，
getFilter()
应当
返回一个可行状态还是所有的可行
状态？不难想象，返回所有可行状态的作法并不太现实
，因为：
1.
有时候用户只需要一个，
或者少数几个可行状态，
此时把所
有的可行
状态都穷举出来显然是低效而不必要的；
2.
甚至，有些问题的可行状
态数量是无限的，如穷举素数，此时返回所有状
态当然不可能。同时
考虑到用户要求的仍有可能是不止一个可行解，
我们现在知道，
应当
提供一个
ge
tNextFilter()
而不是
getFilter()<
/p>
的函数：第一次调用它
时，将返回从初始状态开始，依序遍历到的
第一个可行状态；而此后
的调用都将以上次调用为起点继续向前遍历，返回下一个可行状
态。
需要注意的是，
如果已经遍历完了状态全集，
显然再调用此函数是没
有意义的，
所以它应当返回一
个标志，
反馈给用户是否遍历已经完成。
我们将这个函数定义为
bool
，如果调用有效，则返回
tr
ue
，反之如
果已经完成遍历，
则返回
false.
显然，
我们相应需要一个
私有的
State
对象变量
curSt
ate
，它用于存储当前的状态值。
我们是否应当给
getNextFilter
加上一个
State
引用参数，以向
用户返回每次穷举到
的可行状态？在这里我们并没有这样做。试想，
可能用户会想获得第
5
个遍历到的可行状态，
那么他当然就要调用
5
次
getNextFilter()
，但前
4
次他并不要求得到所搜索到的可行状态。<
/p>
所以，我们将“找到下一个可行状态”与“获得当前找到的可行状
态”分离开来，新增加一个
getState()
成员函数，它
返回一个
State
对象，
注意到
getState()
操作并不影响
Wal
kThrough
对象的内部状
态，所以它同时应被声明为
const
成员函数。
< br>同时用户可能需要知道，
对于一个穷举对象，
是否已经完
成穷举，
当然他可以调用
getNextFilter()
并检查返回值，但如果遍历没有完
成，
则
getNextFilter()<
/p>
除了最后返回
true
之外还会额外地进
行搜索，
并将当前状态改为下一个可行状态，
这份额外的工作可
能并不是用户
所期望需要的。
因此我们将增加一个成员函数
isOver()
，
它不带参数，
返回一个
bool
值：如果已经完成遍历，返回
true
，反之返回
false.
相应地，
我们需要一个私有
bool
变量
overFlag
，
它用于存储
isOver()
所需要的状态值。
至此，
WalkThrough
的定义如下：
template
class WalkThrough
public:
void setState(const State& s) curState
= s;
State getState() const return
curState;
bool getNextFilter();
bool isOver() const return overFlag;
private:
State curState;
bool overFlag;
;
我们把构造函数与析构函数置后，先考虑起关键作用的
getNextFilter()
的实现。首先，
getNextFileter()
由当前的状态跳转
为下一状态，然后判断新状态是否为可行，若可行，则停
止跳转并返
回
true
，否则继续跳转
，重复上述步骤。另一方面，如果已经完成