正在阅读:经验分享:闲谈C++算法封装之穷举法经验分享:闲谈C++算法封装之穷举法

2004-03-26 10:05 出处:CSDN 作者:Kusk 责任编辑:linjixiong

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

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

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

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

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

    (3) 状态跳转:根据当前得到的苹果,按一定的“遍历算法”取得下一个苹果;这个算法保证不重不漏地取遍苹果堆中的所有苹果,只要所取的第一个苹果也是按算法定义给出的

    很显然,对于不同的穷举任务,都会有不同的遍历算法,所以这样一来我们就得将其实现下放给调用我们“穷举算法库”的用户们了。不过考虑到这的确是由于问题的多样性所决定的,因而这个要求应当是合理的。

    嗯啊,现在我们已经有了苹果源,目标苹果,乃至遍历苹果的方案(用户提供),接下来还差一个判断标准,这个倒简单了:

    (4) 判断标准:当前苹果是否为蓝色的苹果

    下一步,我们就可以考虑“the class of 穷举算法”的具体实现了。我们把这个class的名字定义为WalkThrough.

    首先,让我们注意到,“状态”是一个很重要的概念:不同的穷举问题都有彼此不同的状态,在苹果问题中,“状态”是苹果,它包含了苹果颜色或者更多的信息;而在星球搜索计划中,“状态”则是星球,它可能包含该星球的体积、平均密度、温度、是否有大气、是否探测到水、星表活动状况等一系列丰富得惊人的信息。因此,不同状态(state)对应不同的数据类型,要让WalkThrough能处理它们,有必要使用模板,于是我们的最初定义如下:

  template <class State>


 

察看评论详细内容 我要发表评论
作者笔名简短内容 发表时间
:

键盘也能翻页,试试“← →”键
302 Found

302 Found


Powered by Tengine
tengine