浅谈 C++算法封装——穷举法
关键字:穷举算法 状态全集 跳转函数 非内联函数
摘录:穷举法作为最简单的搜索方法,在练习编程的时候可以
作为一项重要内容来进行练习,这对于初学者来说尤其重要,本文
结合一个简单的例子来谈谈本人初学 C++时的一些体会。
将算法独立抽象出来,在 C++中算不上新鲜:STL 中就封装了不少高效、
强大、灵活的泛型组件及对应的基础算法。这里不打算(作为一个初学者也
暂没有能力打算)以 STL 这样的工业级要求来谈论算法封装,就以自己学习
的过程中的一些体会选择了最简易的穷举算法,参考一些实际例子,对自己
的学习做一汇报。
众所周知,穷举法可视为最简单的搜索:即是在一个可能存在可行状态
(可行解)的状态全集中依次遍历所有的元素,并且判断是否为可行状态。
例如,要设计一个“从一堆苹果中找出蓝色的苹果”这样的穷举算法,则定
义:
(1)状态全集:一堆苹果
(2) 可行状态:蓝色的苹果
我们现在已经抽取了两个基本概念,迫不及待要开始穷举了,但……
怎么做呢?穷举的关键是“依次遍历”,即做到不重、不漏。我们可以给苹果
们排成一行,并且编号以后放在“苹果数组”中,然后呢,我们就可以按照 0
号苹果、1 号苹果、2 号苹果、…、n 号苹果这样的顺序成功遍历。我们解决
了遍历苹果的问题……,我们现在是设计一个算法的抽象模型,如果一切待
穷举的对象都已经活生生地摆在那里,就有可能把它们全部收集起来并排队,
但如果开始的时候我们并不知道所有要穷举的对象,比如我们或许要通过一
台安装在探测飞船内的计算机在全宇宙范围内穷举出除地球以外有生命的星
球,那么我们的计算机可能是随着飞船的前行方能不断地得到新星球的信息,
而不是停在地球的时候就获得全宇宙的星球信息(就算可能,内存或许也装
不下如此大的数据量——哪怕宇宙真的是有限“大”的)。所以我们不应当要
求穷举进行之前就能获得状态全集中的所有状态,这样一来,我们的“苹果
数组”计划就受到局限了。现在再看看我们激动人心的星球搜索计划:它并
没有把所有星球收罗排队,那么它成功的关键在哪里?在于飞船能否以适当
的路径“光顾”完所有的星球;我们把这个条件加强一下:飞船每次到达一
个星球,都会看到星球上立着一个方向标,标示下一个星球的方位;而假定
这样的标示保证飞船能够不重不漏地飞临宇宙中的所有星球。我承认本文讨