闲谈C++算法封装：穷举法

　　将算法独立抽象出来，在C++中算不上新鲜：STL中就封装了不少高效、健壮、灵活的泛型组件及对应的基础算法，工艺之高、适用性之强，非寻常我辈所轻易能及。这里不打算（也暂没有能力打算）以STL这样的工业级要求来谈论算法封装，只因最近尝翻大师名著，阅者水平有限，仅嗅触至皮毛，理智薄弱，感情却蓬勃发展：也欲尝试“封装”的味道。选择了最简易的穷举算法，抽其骨架，炮制成class，套上一实际例子，观之run之，抽象程度颇低，效率损失弥彰；然却也自觉有可爱之处，遂作此文以记之。诚惶诚恐，便于名目之前加“闲谈”二字，倘果因技术问题招致痛骂，则试以此二字为护文符，聊且一挡。

　　众所周知，穷举法可视为最简单的搜索：即是在一个可能存在可行状态（可行解）的状态全集中依次遍历所有的元素，并判断是否为可行状态。例如，要设计一个“从一堆苹果中找出蓝色的苹果”这样的穷举算法，则定义：

　　(1) 状态全集：一堆苹果

　　(2) 可行状态：蓝色的苹果

　　噢，好，我们现在已经抽取了两个基本概念，迫不及待要开始穷举了，但……怎么做呢？穷举的关键是“依次遍历”，即做到不重、不漏。呃，我们可以让听话的苹果们排成一行，放在“苹果数组”中，然后呢，我们就可以按照0号苹果、1号苹果、2号苹果、...、n号苹果这样的顺序成功遍历。好，我们解决了遍历苹果的问题……慢，我们现在是设计一个算法的抽象模型，如果一切待穷举的对象都已经活生生地摆在那里，当然有可能把它们全部收集起来并排队，但如果开始的时候我们并不知道所有要穷举的对象，比如我们或许要通过一台安装在探测飞船内的计算机在全宇宙范围内穷举出除地球以外有生命的星球，那么我们的计算机可能是随着飞船的前行方能不断地得到新星球的信息，而不是停在地球的时候就获得全宇宙的星球信息（就算可能，内存或许也装不下如此大的数据量——哪怕宇宙真的是有限“大”的）。所以我们不应当要求穷举进行之前就能获得状态全集中的所有状态，这样一来，我们的“苹果数组”计划就宣告流产了。现在再看看我们激动人心的星球搜索计划：它并没有把所有星球收罗排队，那么它成功的关键在哪里？在于飞船能否以适当的路径“光顾”完所有的星球；我们把这个条件加强一下：飞船每次到达一个星球，都会看到星球上立着一个方向标，标示下一个星球的方位；而假定这样的标示保证飞船能够不重不漏地飞临宇宙中的所有星球。啊喔……你是不是觉得我这是在异想天开？哦，没关系，大不了我们不搜索星球了，而除此之外的很多现实穷举问题都可以满足这个加强条件。嗯，我承认本文讨论的是满足这个加强条件的稍稍狭义的穷举：它必须保证在知道一个状态的前提下能获得一个新状态，并且这样的“状态链”刚好能遍历整个状态全集。我们称从当前状态获得并转到下一个状态的过程为“状态跳转”（我是想用“状态转移”的，嗨，可惜它会与动态规划算法的术语相混淆）：

热门推荐：
如何迅速成为Java高手  

编程高手的八大奥秘


javascript:window.open(this.src);" style="cursor: pointer;"/>