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

2019-11-17 05:12:48

字体：大中小

来源：转载

供稿：网友

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

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

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

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

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

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

　　嗯啊，现在我们已经有了苹果源，目标苹果，乃至遍历苹果的方案（用户提供），接下来还差一个判定标准，这个倒简单了：

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

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

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

　　template

　　class WalkThrough

　　;

　　万事开头难，但现在我们显然已经开了一个不错的头，嗯，继续。在考虑具体实现之前，先幻想一下我们的WalkThrough能为用户提供怎样的服务——当然，它的本职工作是找到并返回可行状态，因此它似乎应该有一个类似于getFilter()的成员函数。问题是，假如可行状态不止一个时，getFilter()应当返回一个可行状态还是所有的可行状态？不难想象，返回所有可行状态的作法并不太现实，因为：1.有时候用户只需要一个，或者少数几个可行状态，此时把所有的可行状态都穷举出来显然是低效而不必要的；2.甚至，有些问题的可行状态数量是无限的，如穷举素数，此时返回所有状态当然不可能。同时考虑到用户要求的仍有可能是不止一个可行解，我们现在知道，应当提供一个getNextFilter()而不是getFilter()的函数：第一次调用它时，将返回从初始状态开始，依序遍历到的第一个可行状态；而此后的调用都将以上次调用为起点继续向前遍历，返回下一个可行状态。需要注重的是，假如已经遍历完了状态全集，显然再调用此函数是没有意义的，所以它应当返回一个标志，反馈给用户是否遍历已经完成。我们将这个函数定义为bool，假如调用有效，则返回true，反之假如已经完成遍历，则返回false.显然，我们相应需要一个私有的State对象变量curState，它用于存储当前的状态值。

　　我们是否应当给getNextFilter加上一个State引用参数，以向用户返回每次穷举到的可行状态？在这里我们并没有这样做。试想，可能用户会想获得第5个遍历到的可行状态，那么他当然就要调用5次getNextFilter()，但前4次他并不要求得到所搜索到的可行状态。所以，我们将“找到下一个可行状态”与“获得当前找到的可行状态”分离开来，新增加一个getState()成员函数，它返回一个State对象，注重到getState()操作并不影响WalkThrough对象的内部状态，所以它同时应被声明为const成员函数。

　　相应地，我们需要一个setState()成员函数，它用于改变当前的状态值，例如设置初始状态的时候都有可能用到。它带一个constState&类型的参数，用以指定所要设定的State值，由于State可能是一个较大的类型，所以使用引用传递能保证效率，同时加上const限制则保证该函数不会更改所传入的引用对象本身的值。

　　同时用户可能需要知道，对于一个穷举对象，是否已经完成穷举，当然他可以调用getNextFilter()并检查返回值，但假如遍历没有完成，则getNextFilter()除了最后返回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，否则继续跳转，重复上述步骤。另一方面，假如已经完成了遍历而还没有找到可行状态，则将overFlag设为false并且返回false.

　　我们将跳转操作、判定是否为可行状态操作下放给用户实现：用户相应提供两个函数，然后向WalkThrough对象传入函数指针，供getNextFileter()调用。那么这两个函数应该采用什么样的接口形式比较合适呢？先看看跳转函数，一个很直观的实现是传入一个State对象（或其const引用），然后返回“下一个”State对象，不过至少在返回的时候，值传递会产生State对象的复制操作（诸如NRV优化之类的语言标准外的特定编译器实现不在讨论之列），当State对象比较大的时候，开销是不值得的。我们应当考虑传入State对象的引用，然后“全权委托”跳转函数进行直接修改——把它“变”成下一个状态。可能会有人质疑这样做是否违反了封装原则，但即使摒弃效率方面的权衡，这样做也是合情合理的。跳转函数——不妨视为负责“状态转化”函数，就像一个炼丹炉——有权利、甚至有义务这样做，它的职责是“转化状态”而非“获得状态”。唔……我都觉得自己在语言上过于细究了。嗯，除了转化状态，跳转函数在发现遍历完成之后也应当及时告知调用它的getNextFilter()，否则下放了大部分权力的getNextFilter()是无从知晓的。于是我们的跳转函数接口为：接受一个State的引用，返回一个bool值。假如遍历没有完成，那么函数执行完毕之后State引用将变为它的后继状态，且函数返回true；否则State不变，函数返回false.

　　判定是否为可行状态的函数接口则很好定义了：它接受一个constState型引用作为待判定的状态，返回bool值，其中true表示该状态为可行状态，false表示该状态不是可行状态。

　　我们将跳转函数以及判定函数的函数指针类型分别定义为StateJumper及Matcher，由于用户可能也会用到这些函数指针类型，我们将定义加到public域中：

　　public:

　　typedef bool (*StateJumper)(State&);

　　typedef bool (*Matcher)(const State&);

　　// others...

　　并且，在private域中相应加上StateJumper和Matcher的函数指针变量，存储用户提供的相应函数的地址：

　　private:

　　// others...

　　StateJumper Jumper;

　　Matcher IsMatch;

　　相应地，内联定义公有成员函数：

　　void setJumper(const StateJumper j) Jumper = j;

　　void setMatcher(const Matcher m) IsMatch = m;

　　分别用于设置Jumper和IsMatch的函数指针值。
　　现在所有的成员变量都已经浮出水面，我们可以定义构造函数和析够函数了，我们不打算对WalkThrough的创建与继续等方面作限制，因此它们都加在public域中。先看构造函数，有必要定义一个默认构造函数：

　　WalkThrough(): overFlag(false), Jumper(0), IsMatch(0)

　　这个构造函数不指定任何初始条件，包括当前状态。可以在需要的时候使用一系列的set成员函数定义。

　　接下来定义一个“全功能”的构造函数：

　　WalkThrough(const State& s, StateJumper j = 0, Matcher m=0)

　　: overFlag(false), curState(s), Jumper(j), IsMatch(m)

　　除了overFlag外，所有的属性都可以在这个构造函数中设定（当然，它答应缺省值）。由于没有进行任何穷举操作，将overFlag强制为false是合理的。

　　对于拷贝构造函数，由于我们这里没有涉及内存分配，没有“深拷贝”的需求，因此不作定义，使用默认的位拷贝可以有不错的效率。类似地，析构函数也没有什么事务需要处理，不过考虑到这个WalkThrough可能用于继续，且有可能出现delete基类指针来删除派生对象的情况，便定义一个空的虚析构函数，以免引起错误：

　　virtual ~WalkThrough()

　　最后，我们来实现唯一的一个非内联函数：getNextFilter()，在给出实现之前顺便给出完整的WalkThrough的定义：

　　template

　　class WalkThrough

　　public:

　　typedef bool (*StateJumper)(State&);

　　typedef bool (*Matcher)(const State&);

　　WalkThrough(): overFlag(false), Jumper(0), IsMatch(0)

　　WalkThrough(const State& s, StateJumper j = 0, Matcher m=0)

　　: overFlag(false), curState(s), Jumper(j), IsMatch(m)

　　virtual ~WalkThrough()

　　void setJumper(const StateJumper j) Jumper = j;

　　void setMatcher(const Matcher m) IsMatch = m;

　　void setState(const State& s) curState = s;

　　State getState() const return curState;

　　bool getNextFilter();

　　bool isOver() const return overFlag;

　　private:

　　State curState;

　　bool overFlag;

　　StateJumper Jumper;

　　Matcher IsMatch;

　　;

　　template

　　bool WalkThrough::getNextFilter()

　　if (overFlag) // 若已完成遍历，则直接返回

　　return false;

　　if (!Jumper!IsMatch) // 若用户未定义Jumper或IsMatch函数，则返回

　　overFlag = true; // 这里将没有定义Jumper或IsMatch的穷举视为遍历完成

　　return false; // 不过，假如你认为两者绝不能等同，也可以抛出异常

　　while (!(overFlag = !Jumper(curState))&&!IsMatch(curState))

　　; // 获取下一状态，直到找到可行状态或者遍历完成

　　if (overFlag) // 根据遍历完成情况决定返回值

　　return false;

　　else

　　return true;热门推荐：如何迅速成为java高手

　　呼……小功告成，总算可以小松一口气。不过假如到此就关闭计算机，就像直播球赛进行到高潮时然停电一样，太令人不爽。——弄了这么久，总该给个example试一试，来点成就感吧？

　　没问题。苹果问题太简单，于是我们选择的是一个传说中的“和是50”超级难题，什么是“和是50”超级难题？请听好了：所谓“和是50”超级难题，就是在0到99的整数组成的一个加法算式中，找出和是50的算式，考虑加数顺序，像0+50啊，1+49啊，……，49+1啊，50+0啊……（喂，我知道你可能想杀人，但请不要让与之匹配的眼光朝着我……）对于这样一个超级难题，我们经过研究，决定采用……穷举法来实现（哪来的这么多西红柿？）。

　　首先我们研究这个问题的状态是什么——两个加数，不是么，它们是有顺序的，并且可以取0到99的整数。于是乎，我们定义状态类如下（注：STL中有类似的东西，但作为完整的示例，我们亲自手工打造）：

　　class Pair

　　public:

　　Pair(int mx = 0, int my = 0): x(mx), y(my)

　　int x, y;

　　;

　　Pair虽然属于世界上最深奥的class之一，然而凭各位的聪明，我就不用多解释了。接着我们来看一下跳转函数的实现——当然，它应当符合WalkThrough中定义的StateJumper类型：

　　bool counter(Pair& pair)

　　if (pair.y < 99)

　　++pair.y;

　　else

　　if (pair.x < 99)

　　++pair.x;

　　pair.y = 0;

　　else

　　return false;

　　return true;

　　counter的作用是试图将pair.y增1，但假如pair.y已经到达上限99，则将pair.x加1，同时pair.y置0继续下一轮；但假如pair.x也到了99，那么，噢，说明遍历结束了。——嗯，这样的确是一种有效的遍历方式，对吧。它实际上类似于下面的二重循环：

　　for (; pair.x <= 99; ++pair.x)

　　for (pair.y = 0; pair.y <= 99; ++pair.y)

　　...

　　只不过循环要求在循环体内解决一切问题，而我们“解决一切问题”的重任担在了另一个函数里，counter不能越权，因而不能这样直接使用循环。

　　接下来是判定是否为有效状态的函数，它最简单了：

　　bool match(const Pair& pair)

　　return (pair.x + pair.y) == 50;

　　万事俱备，可以写main:

　　int main()

　　WalkThrough

　　sf50(Pair(0, -1), &counter, &match);

　　while (sf50.getNextFilter())

　　cout << sf50.getState().x << +

　　<< sf50.getState().y << = 50 << endl;

　　return 0;

　　请一定要注重，getNextFilter()中有一个Next，也就是说，假如把状态全集中的第一个状态作为构造的参数，——本题中就是Pair(0,0)——是可行状态的话，getNextFilter()将不会判定到，它直接判定“下一个”状态，就是Pair(0,1)去了。为了让它能够完整地判定，我们不能让Pair(0,0)作为第一个状态，而,是作为首次运行getNextFilter()后到达的状态。于是，在构造初始状态时我们就要用“前”一个状态Pair(0,-1)作为构造参数（虽然它根本不在本题的状态全集中），以使得getNextFilter()从Pair(0,0)开始判定。

　　嗯，好，在运行之前不要忘了#include ，不要忘了打开std名字空间（usingnamespacestd;），不要忘了粘上/包含上前面的WalkThrough的完整定义……编译，运行，好，这个超级难题被我们解决了。我的编译平台是Redhatlinux9， GNU C++ 3.2.2.

　　最后我们分析小结一下经过封装之后的穷举算法。首先看效率——是啦，我知道这个“和是50”超级难题所用的算法很糟糕——我是指在相同算法的前提下，使用我们封装好的穷举类进行实现时的效率损失：初始化以及一系列set/get函数基本不影响效率，主开销源自于getNextFilter()本身的调用及getNextFilter对两个用户提供函数的调用所产生的额外开销。试想假如用相同的算法，但仅用两层for来做穷举，则少了上万次的函数入栈、清栈操作。穷举法本身就不是一个高效的搜索思想，所以对内层代码的效率变化是最敏感的，这一点是我们所封装的穷举类的最大缺点。

　　不过总算还是有一点好处，比如，封装之后，就将设计穷举算法分解成了相对独立的设计状态类、状态跳转函数、状态判定函数三个部分，三者的耦合度相对降低。此外，这个设计的过程多少让我们又多了解了一点点基于对象编程的抽象能力，嗯，等等。噢……或许这是一个学术价值大于实用价值的设计吧，呵呵。　　作者：程序员之家

上一篇：C++/CLI中实现singleton模式

下一篇：WinForm中的ListBox组件编程(1)