将算法独立抽象出来,在C++中算不上新鲜:STL中就封装了不少高效、健壮、灵活的泛型组件及对应的基础算法,工艺之高、适用性之强,非寻常我辈所轻易能及。这里不打算(也暂没有能力打算)以STL这样的工业级要求来谈论算法封装,只因最近尝翻大师名著,阅者水平有限,仅嗅触至皮毛,理智薄弱,感情却蓬勃发展:也欲尝试“封装”的味道。选择了最简易的穷举算法,抽其骨架,炮制成class,套上一实际例子,观之run之,抽象程度颇低,效率损失弥彰;然却也自觉有可爱之处,遂作此文以记之。诚惶诚恐,便于名目之前加“闲谈”二字,倘果因技术问题招致痛骂,则试以此二字为护文符,聊且一挡。
众所周知,穷举法可视为最简单的搜索:即是在一个可能存在可行状态(可行解)的状态全集中依次遍历所有的元素,并判断是否为可行状态。例如,要设计一个“从一堆苹果中找出蓝色的苹果”这样的穷举算法,则定义:
(1) 状态全集:一堆苹果
(2) 可行状态:蓝色的苹果
噢,好,我们现在已经抽取了两个基本概念,迫不及待要开始穷举了,但……怎么做呢?穷举的关键是“依次遍历”,即做到不重、不漏。呃,我们可以让听话的苹果们排成一行,放在“苹果数组”中,然后呢,我们就可以按照0号苹果...[ 查看全文 ]