软件开发>杂文>11

共享软件开发的点滴心得

[中文][English][日本語

 

An approach for compile time searching

交换青蛙

刘新宇

200610

 

黄梅时节家家雨,青草池塘处处蛙。有约不来过夜半,闲敲棋子落灯花

――赵师秀《约客》

 

问题

 

收到网上传来的一个智力游戏,要求交换左右两侧青蛙的位置,最开始青蛙的位置如下:

 

任何一只青蛙可以跳跃到它面对石头上,例如:

 

也可以跳过它面前的另一只青蛙,落到空石头上,例如:

或者

 

其他行动,如后退,跳过两只以上的青蛙都是不允许的。这个游戏有点像小时候玩的跳棋,棋子可以跳,可以移动,但是不能后退。最后的结果是三只绿色的青蛙全部到了最右侧,而三只棕色的青蛙全部到了最左侧。

 

通过挑战了一会自己的“IQ”,我觉得这个宜智游戏交给计算机做更加合适。计算机并不比人更加聪明,但是比人更加有耐心。本文首先将给出的是通常的搜索解法,不过和教科书上的不同之处是加入了一点OO的风格,然后本文将尝试给出一个编译期的算法,利用C++的模板推导能力,让编译器来解决问题。

 

建模

 

建模是解决问题的第一步。计算机不懂得人类的语言,把人类世界的问题,翻译成人类很难看懂的机器世界语言并非“善之善者也”,能够把问题翻译成人类既能容易看懂,计算机也能明白才是“善之善者也”。

 

这个问题,可以认为要把7个数字:1,1,1,0,-1,-1,-1,按照一系列规则变化,最终实现左右交换,变成-1,-1,-1,0,1,1,1。经过这样的抽象,就获得了问题的起始状态和终止状态:

 

起始状态: 1,  1,  1, 0, -1, -1, -1

终止状态:-1, -1, -1, 0,  1,  1,  1

 

下一步再把青蛙跳跃的规则也变成数学模型。青蛙的跳跃,采用数字串的表达方式之后,等价于按照一定的规则移动0。可以移动的方向有两个,分别是左和右。在每个方向上,又有两种移动方式:移动一步或者跳跃一步。这样算下来,总共有4种移动方案,如下:

  1. 向左侧移动一步,例如1,1,1,0,-1,-1,-1 ==> 1,1,0,1,-1,-1,-1
  2. 向左侧跳跃一步,例如1,1,1,0,-1,-1,-1 ==> 1,0,1,1,-1,-1,-1
  3. 向右侧移动一步,例如1,1,1,0,-1,-1,-1 ==> 1,1,1,-1,0,-1,-1
  4. 向右侧跳跃一步,例如1,1,1,0,-1,-1,-1 ==> 1,1,1,-1,-1,0,-1

 

但是,并不是所有情况下,青蛙们都具有4种移动方案,例如当最右侧的石头已经为空石头时,第34号方案就不可行了。另外由于青蛙只能不断“向前,向前,向前……”,而不能后退,所以当0向左侧移动时,必须保证01交换位置,而不能和-1交换;同样,当0向右侧移动时,必须保证0-1交换位置,而不能和1交换。

 

粗略算法

 

经过上述建模后,就可以大致把算法的思路整理出来,该算法接受一个由数字组成的串,对其按照一定规则进行变化,当变化为终止状态时,算法结束。其描述如下:

 

<移动青蛙算法>

  1. 记录当前状态,判断当前状态是否已经等于结束状态,如果相等,则算法结束;
  2. 否则,尝试根据当前状态,利用规则产生一系列方案,并针对每种方案<移动青蛙>

 

从算法描述种的黑体部分,就可以看出这是一个递归算法,由于这到题目简单,运算量不大,采用递归更容易理解。并且也方便在后面将本算法利用C++编译期编程加以实现。

 

算法描述可以很容易地翻译为伪代码:

class MoveFrog{

public:

    bool run(FrogLine line){

        if(isOK(line))

            return true;     //成功,结束

        else{

            //找出所有能移动青蛙的方案,并加以尝试

            std::list<FrogLine> nextLines=moveIt(line);

                if(!nextLines.empty()){

                    for(std::list<FrogLine>::iterator

                            it=nextLines.begin();

                            it!=nextLines.end(); ++it){

                         if(run(*it))

                             return true//成功

                    }

                }

                //失败?

                return false;

        }

    }

};

 

现在需要把这段伪代码逐步细化,直到能够正确运行,求出移动青蛙的解。其中isOK()最容易写,就是比较line是否等于-1,-1,-1,0,1,1,1即可。FrogLine这个类型可以通过存放7个数字的整数数组来实现,为了将来解决更复杂的青蛙移动问题(例如左右各5只青蛙),这里采用向量(stlvector)代表青蛙的排列。定义如下:

 

typedef std::vector<int> FrogLine;

 

针对失败的处理还不是很明确,特别需要关注moveIt()函数,也就是从某个青蛙的排列line出发,应用4条规则,生成下一步移动的方案集。

 

4条规则翻译成伪代码,大体如下:

std::list<FrogLine> MoveFrog::moveIt(FrogLine& line){

     //根据当前的青蛙状态,产生下一步的移动方案(最多4种)

 

     //找出当前空石头所在的位置

     unsigned int pos;

     for(pos=0; pos<line.size(); ++pos)

          if(line[pos]==0) break;

 

     if(pos>0){

          //青蛙向右移动一步: -->

          if(line[pos-1]>0 )  //>0 保证没有青蛙后退

              交换位置(pos-1, pos);

 

          //青蛙向右跳跃一步: -->

          if(pos>=2 && line[pos-1]!=0 && line[pos-2]>0)

              交换位置(pos-2, pos);

     }

 

     if(pos<line.size()-1){

          //青蛙向左移动一步:<--

          if(line[pos+1]<0)  //<0 保证没有青蛙后退

              交换位置(pos, pos+1);

 

          //青蛙向左跳跃一步:<--

          if(pos+2<line.size() && line[pos+1]!=0 && line[pos+2]<0)

              交换位置(pos, pos+2);

     }

}

 

在寻找下一步可能移动的方案过程中,首先需要确定空石头,也就是0所在的位置。如果空石头的位置pos不在最左侧(>0),那么位于空石头更左侧的青蛙,就有可能向右移动(移动一步或者跳跃一步)。同样如果空石头不在最右侧(pos<line.size()-1),那么位于其更右侧的青蛙,就有可能向左侧移动。如果青蛙向右移动,那么它必须是原来左侧的青蛙,(因为它们不能后退),而左侧青蛙的特点,就是全部用1表示,也就是左侧的青蛙都>0;反之,当青蛙向左侧移动时,它必须是原来右侧的青蛙,也就是用-1表示的青蛙,所以可以用<0来保证这点。

 

逐步求精

 

如果稍微精化上面的算法,就直接运行,计算很可能会出问题——因为,如果某一步走错,造成后面钻进了死胡同(根据这一步产生的所有4套方案都行不通)时,程序没有任何办法从那走错的一步中恢复,重新试验其他的结果。

 

另一个必须解决的问题是,循环方案的问题。所谓循环方案,就是经过一系列移动,青蛙们又回到了原来的位置。于是计算机就会不厌其烦地再次寻找解决方案。其结果是又找到了同样的解。(本题不大会出现这种可能,因为青蛙们只退不进,解决类似走迷宫的题目时,就必须考虑这个问题。)

 

这两个问题的答案是一个,就是建立一个记录,记录下来每次变化后青蛙们的排列位置。每次产生新的变化后,都在这个记录中查找,看看是否以前出现过这种排列以避免重复。当根据某个青蛙的排列尝试进行下一步移动时,如果没有可行的方案,就可以根据这个记录,回退一步,然后再尝试其他方法(就像下棋悔棋)。越早先记录的移动步骤,越是最后被回退。所以这个记录是一个典型的stack数据结构。并且从算法一启动就开始记录,直到找到最终的解结束记录。为此,可以将这一记录作为类成员声明:

 

class MoveFrog{

public:

    //...

private:

    std::list<FrogLine> steps;

};

 

然后,在每次算法进行计算时,记录当前的青蛙排列状况到steps中去,当根据某个排列,进行的所有变化都不能达到目标时,就在steps中,删除上一步的青蛙排列,进而尝试其他可能。因此,加入steps后,MoveFrog::run()就改进为:

 

bool MoveFrog::run(FrogLine line){

     steps.push_back(line); //记录当前的青蛙排列

     if(isOK(line)){

//青蛙排列已经到达目标状态,打印steps中保存的整个移动青蛙的过程

          for(std::list<FrogLine>::iterator it=steps.begin();

it!=steps.end(); ++it)

              打印输出(*it);

          return true;

     }

     else{

          std::list<FrogLine> nextLines=moveIt(line);

          if(!nextLines.empty()){

              for(std::list<FrogLine>::iterator it=nextLines.begin();

    it!=nextLines.end(); ++it){

                   if(run(*it))

                        return true//成功!

              }

          }

 

          //失败!没有能够根据当前的青蛙排列找到到达目标的方法,回退一步

          if(!steps.empty())

              steps.pop_back();

 

          return false;

     }

}

 

并且,利用steps这个记录,可以把前面MoveFrog::moveIt(),进行细化了。当准备对pos1pos2交换位置时,首先到steps中查看交换后的青蛙排列以前是否出现过。如果没有出现过,就把这种新的排列加到结果集中去,否则就算一种重复状态,可以跳过不理。这一思路可以实现如下:

 

void MoveFrog::addNewLine(std::list<FrogLine>& res,

    FrogLine line, int pos1, int pos2){

     std::swap(line[pos1], line[pos2]);

     if(std::find(steps.begin(), steps.end(), line)==steps.end())

          res.push_back(line);

}

 

其中res代表根据当前青蛙排列,产生的可行移动方案的结果集。相应地,moveIt()更新为:

 

std::list<FrogLine> MoveFrog::moveIt(FrogLine& line){

     //根据当前的青蛙状态,不重复地产生下一步的移动方案(最多4种)

     std::list<FrogLine> res;     //下一步移动方案的结果集

 

//......

         

     if(pos>0){

          //青蛙向右移动一步: -->

          if(line[pos-1]>0 )

              addNewLine(res, line, pos-1, pos);

 

//......

 

     return res;   //将移动方案结果集返回

}

 

至此,算法中全部的关键问题,已经都被逐一解决了,读者剩下来还要写一个打印结果输出的小函数,这些留给读者作为练习自己完成。(附录的源代码提供了一个参考实现的答案)使用MoveFrog类,就可以看看计算机怎么解决移动青蛙问题了:

int main(int argc, char* argv[]){

     const int line0[]={1, 1, 1, 0, -1, -1, -1};

     const int line1[]={-1, -1, -1, 0, 1, 1, 1};

     FrogLine before(line0, line0+sizeof(line0)/sizeof(int));

     FrogLine after (line1, line1+sizeof(line1)/sizeof(int));

 

     MoveFrog runner(after);

     runner.run(before);

}

 

程序输出:

1, 1, 1, 0, -1, -1, -1,

1, 1, 0, 1, -1, -1, -1,

1, 1, -1, 1, 0, -1, -1,

1, 1, -1, 1, -1, 0, -1,

1, 1, -1, 0, -1, 1, -1,

1, 0, -1, 1, -1, 1, -1,

0, 1, -1, 1, -1, 1, -1,

-1, 1, 0, 1, -1, 1, -1,

-1, 1, -1, 1, 0, 1, -1,

-1, 1, -1, 1, -1, 1, 0,

-1, 1, -1, 1, -1, 0, 1,

-1, 1, -1, 0, -1, 1, 1,

-1, 0, -1, 1, -1, 1, 1,

-1, -1, 0, 1, -1, 1, 1,

-1, -1, -1, 1, 0, 1, 1,

-1, -1, -1, 0, 1, 1, 1,

 

如果读者好奇,可以从本网页下载这个移动青蛙的Flash游戏,并根据上面的程序输出赢得这个游戏的胜利。本程序的全部源代码也可下载

 

转向编译期

 

如果就此停止,那么读者得到的将只不过是一个有趣的小程序,其本质是一个采用回溯的递归算法,实现了深度优先的搜索功能[1]。这样的程序在任何一本教科书中都可以找到。为了增加趣味性,本文将给出一个利用C++ template meta programming实现同样功能的编译期编程实现。

 

进入编译期编程面临的一大问题就是不能定义任何变量。编译期提供了一个完备的函数式编程环境。

 

在以前几个月的文章中,作者已经尝试给出了一些编译期编程的例子[2][3]。特别地,逐渐积累出了一些具有递归特性的数字列表极工具。本文下面会利用这些已有的工具,来简化该程序的设计。

 

编译期建模

 

首先仍然是建模。最直接的想法是利用数字列表List,将青蛙的位置排列表示为:

 

List<-1,List<-1,List<-1,List<0,List<1,List<1,List<1,Empty>>>>>>>

 

其中,-1表示左侧的青蛙,1表示右侧的青蛙,0表示空石头。而List的定义为:

 

struct Empty;

 

template<long n, class T>

struct List{

     static const long First = n;

     typedef T Rest;

};

 

采用这种模型,当青蛙移动后,记录青蛙排列状态变化,就可以用列表的列表来表示,例如:

 

List<Step1, List<Step2, ...List<StepN, Empty>>...>

 

其中StepI,是前面给出的由3-1,1031组成列表。这种模型,实际上是一种2维列表,操作起来稍微有些麻烦。为此可以寻找更简化的模型。其中一个简化思路是:不使用列表,而使用一个长整数来代表青蛙的排列。例如:整数1112333,其中1代表左侧的青蛙,2代表空石头,3代表右侧的青蛙。记录青蛙排列变化步骤的列表就可以表示为:

 

List<1113323, List<1112333>, ..., List<3332111, Empty>>...>

 

这样2维列表就被简化为普通的1维列表,列表的每个元素为一个整数,整数的每1位代表青蛙或者空石头等意义。

 

这里再略微解释一下为什么,采用1,2,3表示青蛙的排列。首先由于排列是一个整数,而整数的各个位不能是-1,因此必须使用0-9中的数字来表示。如果采用0,例如1110222,这样会有一个潜在的问题,当空石头在最左侧时,该整数就变成了0111222,而计算时会把其认同为111222,这样就凭空丢失了一位。而采用1112333就可以完全避免这些问题。

 

采用这样的模型后,带来了一些小的需求,例如要得知某一个位置上究竟是原来左侧青蛙,右侧的青蛙还是空石头;再例如青蛙的移动或者跳跃本质上是交换整数中2个不同位上的数字,这都需要一系列的编译期操作,最基本的一些操作可以归纳如下:

  • 获得某个位置上的数字,例如:GetAt<1112333, 3>获得整数1112333第3位上的数字2
  • 设置某个位置上的数字,例如:SetAt<1112333, 3, 1>11123333个位置上的数字设置为1,从而将1112333变成1111333;
  • 查找某个特定的数字在哪个位置上,例如:Find<1112333, 2>将查找数字21112333中的位置,并返回结果3
  • 交换两个位置上的数字,例如:SwapAt<1112333, 3, 1>将交换1112333的第3位和第1位,从而得到新的青蛙排列:1113323。该交换本质上是对右侧青蛙向左侧跳跃的模拟。
  • 判断整数某位上的数字是否是期望的数字,例如IsEqualAt<1112333, 3, 2>将判断整数11123333位上的数字是否是2

 

这些需求必须以编译期编程的形式加以实现,为了进一步简化整数的操作,本文规定,整数的个位代表第0位,十位代表第1位,百位代表第2位……,也就是从右向左,计算位置。很明显,这些需求不是正交的,例如SwapAt就完全可以通过GetAtSetAt来实现。下面就是一个SwapAt的实现:

 

template<long line, int pos1, int pos2> struct SwapAt{

     static const long value = SetAt<

          SetAt<line, pos1, GetAt<line, pos2>::value>::value,

          pos2, GetAt<line, pos1>::value

>::value;

};

 

其思路就是,利用GetAt拿到整数linepos2上的数字,再利用SetAt将此数字设置回整数linepos1的位置,然后再用同样的方法,将原pos1上的数字设置到pos2上。

 

所以,作为最基本的需求,应该首先实现GetAtSetAt,下面是GetAt的实现:

template<long line, int i> struct GetAt{

     static const int value = GetAt<line/10, i-1>::value;

};

 

template<long line> struct GetAt<line, 0>{

     static const int value = line % 10;

};

 

这个实现的思路本质上是比较朴素的:如果要得到某个整数第i位上的数字(从右向左计),方法:

  • 简单情况平凡解:若i0,则返回整数最右侧的数字,也就是个位数字即可,个位数字可以通过将整数对10取模获得;
  • 普通情况,也就是i不为0的情况,可以将该整数最右侧去掉,然后查找去掉个位的整数的第i-1位上的数字并返回。

 

GetAt的使用方法如下:

assert(GetAt<1112333, 0>::value == 3);

assert(GetAt<1112333, 3>::value == 2);

assert(GetAt<1112333, 6>::value == 1);

assert(GetAt<1112333, 7>::value == 0);

 

SetAt的思路也是递归,如果要将某整数x的第i位上的数字设置为v,可以:

  • 简单情况平凡解:若i0,也就是要将某整数的个位数字替换为v,可以将此整数除10取整后再乘10,这样其个位就变成了0,然后再将此整数加上v即可。
  • 普通情况,若i不为0,可以将整数分成两个部分,个位(x10)和除去个位后的部分(x10),可以先将除去个位的部分的第i-1位设置为v,然后再和个位组合起来(组合的方法为:(除去个位的部分)*10+个位)

 

根据这个思路SetAt实现如下:

template<long line, int i, int v> struct SetAt{

     static const int value =

SetAt<line/10, i-1, v>::value*10 + (line % 10);

};

 

template<long line, int v> struct SetAt<line, 0, v>{

     static const int value = (line / 10)*10+v;

};

 

下面的测试代码给出了SetAt的使用方法:

assert(SetAt<1112333, 0, 4>::value == 1112334);

assert(SetAt<1112333, 3, 4>::value == 1114333);

assert(SetAt<1112333, 6, 4>::value == 4112333);

 

由于实现了GetAtSetAt,上面的SwapAt就可以使用了,下面的例子模拟了青蛙的移动和跳跃:

assert<SwapAt<1112333, 2, 3>::value == 1113233);

assert(SwapAt<1112333, 1, 3>::value == 1113323);

 

不同于SetAtGetAt,实现查找时会遇到比较复杂的情况。一种是找到的结果多于1个,一种是找不到结果。对于多1个的结果,Find将返回第一个符合的位置,对于找不到的情况,将返回一个很大的负数表示没有找到。Find实现如下:

 

template<long line, int v> struct Find{

     static const int value = ( line % 10 ) == v ?

0 : (1 + Find<line/10, v>::value);

};

 

template<int v> struct Find<0, v>{

     static const int value = ( v == 0) ? 0 : -1000; //error

};

 

当在某个整数中查找哪一位上的数字是v时,其思路为:

  • 首先判断个位是否为v,如果是,则返回0,告知用户找到了,结果为第0位(也就是个位)
  • 否则,首先在除去个位的剩余部分查找v,然后将查找结果加1(加上个位所占的位)即可。
  • 例外情况是,如果在整数0中查找哪一位是v,若v0,则结果为第0位,否则说明无法查找到v,此时返回一很大的负数表示出错。

 

下面的测试代码,给出了如何使用Find的例子:

assert(Find<1112333, 2>::value == 3);

assert(Find<1112333, 3>::value == 0);

assert(Find<1112333, 4>::value < 0 );

 

判断整数某位上的数字是否是给定数字v的程序,可以很方便的利用GetAt来实现,如下:

template<long line, int pos, int v> struct IsEqualAt{

     static const bool value = (GetAt<line, pos>::value == v);

};

 

产生新排列

 

有了上述的基本工具,就可以针对某一青蛙排列,通过青蛙的移动和跳跃,产生新的排列。如上面所述,产生新排列,本质上就是交换空石头和青蛙的位置。例如,通过让右侧的青蛙向左跳跃产生新排列的过程,可以叙述如下:

  • 首先要找到空石头的位置;
  • 判断从空石头起向右侧第2个石头上是否有青蛙。也就是说要求空石头的位置-2必须大于或等于0
  • 判断该青蛙是否面向左侧,由于青蛙不能后退,所以该青蛙必须面向左侧,因此代表该青蛙的数字必须是3。

 

如前面所讨论的,类似这样的过程一共有4种,分别是:StepLeft, JumpLeft, StepRightJumpRight,这样的过程本质上都可以抽象为下面的步骤:

  • 首先找到空石头的位置pos1;
  • 然后根据具体的动作,确定要和空石头交换的青蛙的位置pos2;
  • 判断pos2是否合理,(要在06之间),若不合理,则不能进行此动作;
  • 判断pos2上的青蛙的面向的方向是否合理,保证青蛙不能后退。

 

采用这种抽象后,四种动作就可以比较简洁的加以表示,例如下面是JumpLeft的实现:

template<long line, class Steps> struct JumpLeft{

     static const int pos = Find<line, 2>::value;

 

     typedef typename Move<

          CanMove<line, Greater, pos, 1, pos-2, 3>::value,

          line, pos, pos-2, Steps

     >::Result Result;

};

 

该实现中,程序接受两个参数,一个是当前的青蛙排列line,另一个Steps是其他移动后产生的结果。该程序首先通过Find工具,找到空石头的位置pos,由于向左侧跳跃,所以空石头应该和pos-2位置的青蛙交换,为此必须保证pos-2要大于等于0,也就是要求pos大于1;最后向左跳的青蛙,必须面向左,所以代表该青蛙的数字必须是3

 

这些因素综合起来,就是使用CanMove来判断能否移动,一旦能够移动,就调用Move来实际交换pospos-2位置上的数字,并将结果添加到Steps列表中;如果不能移动就不做任何动作,直接将Steps列表返回。

 

判断位置是否合理时,通常是利用某种比较操作(例如大于Greater,小于Less)来确定pos和某个值limit之间的关系,为了能够将比较操作参数化,可以将大于,小于抽象概括如下:

 

template<int x, int y> struct Less{

     static const bool value = (x<y);

};

 

template<int x, int y> struct Greater{

     static const bool value = (x>y);

};

 

有了抽象的比较运算定义,就可以进一步实现用于判断能否移动的程序CanMove,该程序接受一个青蛙的排列line,一个二元比较运算符Op(可以是Greater或者Less),用于比较的两个数字pos1limit。并且,为了判断青蛙面向的位置,还需要获得即将移动的青蛙所在的位置pos2以及该位置上青蛙应该面向的方向shouldBeCanMove的实现如下:

 

template<

     long line,

     template<int, int> class Op, int pos1, int limit,

     int pos2, int shouldBe

struct CanMove{

private:

     //

     // 判断位置pos是否合理

     //

     template< template<int, int> class Op, int pos, int limit>

struct IsPosOK{

          static const bool value = Op<pos, limit>::value;

     };

 

     //

     // 判断青蛙面向的方向是否合理,以保证青蛙不会后退

     //

     template<bool IsPosOK, long line, int pos, int v>

struct IsForwardAnd;

 

     template<long line, int pos, int v>

struct IsForwardAnd<true, line, pos, v>{

          static const bool value = (IsEqualAt<line, pos, v>::value);

     };

 

     template<long line, int pos, int v>

struct IsForwardAnd<false, line, pos, v>{

          static const bool value = false;

     };

 

public:

     static const bool value = IsForwardAnd<   

          IsPosOK<Op, pos1, limit>::value,

          line, pos2, shouldBe

     >::value;

};

 

CanMove的实现略微有些复杂,其本质是判断两个条件是否都为真。但是这两个条件不能简单的用(IsPosOK<...> && IsForward<...>)来加以判断。原因是在编译期,逻辑与不具备“短路”功能。编译器在计算出IsPosOK<...>为假后,并不会短路掉后面的ISForward。而是会耐心地特化IsForward<...>。而这时由于pos非法,所以在计算IsForward中的GetAt<line, pos>就会出现问题。为了避免这种情况,CanMove特地采用了两步模板偏特化来判断这两个条件。CanMove首先判断IsPosOK<...>的结果,若为假,则偏特化IsForwardAnd<false, ...>,其结果时直接返回false给用户,告知他该移动不能进行。反之如果IsPosOK<...>为真,也就是位置合理,就会进一步偏特化IsForwardAnd<true, ...>,这时,编译器会利用GetAt<>判断待交换位置上的青蛙的面向是否合理。

 

CanMove一旦返回OK,告知用户可以移动,就可以真正交换青蛙和空石头的位置,实现青蛙的移动或者跳跃,实现这个交换动作的Move程序如下:

 

template<

     bool canMove,

     long line, int pos1, int pos2,

     class Steps

>

struct Move{

     typedef List<SwapAt<line, pos1, pos2>::value, Steps> Result;

};

 

template<long line, int pos1, int pos2, class Steps>

struct Move<false, line, pos1, pos2, Steps>{

     typedef Steps Result;

};

 

Move也有两个特化版本,当CanMove告知不能移动时,Move不做任何事,直接返回;反之Move就会交换青蛙和空石头的位置,并将交换后的结果附加到总结果列表Steps的前面。

 

有了4种移动尝试的程序StepLeft, JumpLeft, StepRightJumpRight,就可以针对某一种青蛙排列,依次尝试这4种移动方案,并将尝试的结果列表返回。这段程序如下:

 

template<long line> struct ChangeIt{

private:

     struct Try{

          typedef

              typename JumpRight<

                   line,

                   typename StepRight<

                        line,

                        typename JumpLeft<

                             line,

                             typename StepLeft<line, Empty>::Result

                        >::Result

                   >::Result

              >::Result Result;

     };

 

public:

     //final result

     typedef typename Try::Result Result;

};

 

该程序的思路非常直观,首先初始化尝试结果为空Empty,然后尝试StepLeft,在此基础上再尝试JumpLeft,……直到尝试完所有4种方案后返回。

 

下面的测试代码,给出了如何使用ChangeIt的例子:

MoveFrogs::ChangeIt<1112333>::Result

如果利用以前文章[2]中给出的Print<>程序,就可以看出上述移动的结果,打印语句为:

Print<typename MoveFrogs::ChangeIt<1112333>::Result>::print();

程序会输出:

1211333, 1121333, 1113323, 1113233,

 

核心程序

现在万事具备,只欠东风。关键问题只剩下了实现核心程序。核心主程序将接受2个参数:一个是从最开始的起始状态,每次移动青蛙的步骤列表Steps,一个是已经尝试过的各种青蛙的排列记录Tried。程序开始时,列表Steps只有一个元素,也就是起始实状态1112333,随着程序运行,Steps逐渐扩充,最终当达到目标状态3332111时,程序结束。为了避免程序重复尝试以前已经试过的步骤,造成死循环。每当程序尝试出一种新的青蛙排列时,就将其记录入Tried列表。程序运行时,会检查Tried列表以避免重复尝试。

 

根据前面普通的C++程序,可以简略将核心程序MoveIt<Steps, Tried>叙述如下:

  • 简单情况平凡解:若Steps为空,则表示无解,返回false表示无解,解列表Result为空Empty
  • 否则,取出Steps列表中的最新的青蛙排列,判断其是否为目标状态;
    • 若已经达到目标状态,表明已经找到了解,程序返回true表示找到了解,其结果就是Steps列表;
    • 否则,在当前最新的青蛙排列基础上,调用TryMove进行尝试。并返回TryMove的结果。

 

根据这段叙述,MoveIt程序可以实现如下:

 

template<class Steps, class Tried> struct MoveIt{

     typedef TryMove<

          (Steps::First == 3332111),

          Steps, Tried

     > MoveResult;

     typedef typename MoveResult::Result Result;

     static const bool value = MoveResult::value;

};

 

template<class Tried> struct MoveIt<Empty, Tried>{

     static const bool value = false//无解

     typedef Empty Result;

};

 

核心程序MoveIt产生了一个新问题——实现TryMove程序。TryMove程序接受3个参数,一个是用于偏特化的标志OnTarget,如果OnTargettrue,表明已经找到了解,TryMove将不做任何进一步动作,直接返回。第2个参数和第3个参数是从MoveIt获得的StepsTried列表。TryMove程序会进行如下处理:

  • 利用ChangeIt,寻找能够继续变化出的所有可能排列作为候选排列。并且查找Tried列表,去除候选排列中的以前已经尝试过的重复情况。最终候选结果为Candidates
  • 调用TryIt<Candidates, Steps, Tried>针对所有候选结果进行尝试,看看有无可能找到解;
    • 若找到了解,则返回;
    • 否则,表明根据当前的青蛙排列无法找到解,需要回退一步。程序将调用BackTrack进行回溯。

 

根据这段叙述实现的TryMove程序如下:

template<bool OnTarget, class Steps, class Tried> struct TryMove;

 

// 已经到达了目标状态,找到了解

template<class Steps, class Tried> struct TryMove<true, Steps, Tried>{

     typedef Steps Result;

     static const bool value = true;

};

 

// 尚未达到目标状态,需要进一步进行尝试

template<class Steps, class Tried>

struct TryMove<false, Steps, Tried>{

     // 根据当前状态,进行变化,并尝试是否可以达到目标

     typedef TryIt<

          typename Unique<

              typename ChangeIt<Steps::First>::Result,

              Tried

          >::Result,

          Steps,

          Tried

     > TryFurtherStepsResult;

 

     // 根据尝试的结果,判断是否进一步需要回溯

     typedef BackTrack<

          TryFurtherStepsResult::value,

          typename TryFurtherStepsResult::Result,

          Steps,

          Tried

     > BackTrackResult;

     typedef typename BackTrackResult::Result Result;

     static const bool value = BackTrackResult::value;

};

 

其中程序中的Unique<List1, List2>子程序,会针对List1中的每个元素,在List2中查找是否已经存在,若存在,表明这是一个重复元素,会被剔除。结果是所有在List1中存在,但在List2中没有的独一无二的元素列表。其实现作为练习留给读者,读者也可以参考附录中的源代码下载全部源代码,查看Unique的实现。

 

BackTrack子程序就是回退一步,再进行其他尝试;所谓回退一步,就是从Steps中去除掉最新的青蛙排列,将此排列加到Tried中,表明已经尝试过了。然后调用MoveIt<剩余Steps,新Tried>求解。这段程序同样作为练习,留给读者完成。读者可以参考附录中的源代码(下载全部源代码)查看作者给出的参考实现答案。

 

程序TryIt<Candidates, Steps, Tried>会依次尝试Candidates中的所有候选青蛙排列,看看能否找到解。由于编译期算法没有循环功能,所以还必须借助递归来实现循环的功能,其思路为:

  • 普通情况的平凡解:若候选列表Candidates为空,则直接返回false表示无解,解为空;
  • 否则,取出Candidates中的第一个元素First,将First添加到StepsTried的最前面,然后调用MoveIt<Steps,新Tried>判断是否有解;
    • 若有解,则返回解;
    • 否则,针对Candidates中剩下的元素列表Rest,调用TryIt<Rest, Steps, Tried>,并返回结果。

 

根据这段叙述,TryIt实现如下:

template<class Candidates, class Steps, class Tried> struct TryIt{

     typedef MoveIt<

          List<Candidates::First, Steps>,

          List<Candidates::First, Tried>

     > Try1stResult;

 

     typedef TryOthers<

          Try1stResult::value,

          typename Try1stResult::Result,

          Candidates, Steps, Tried

     > TryOthersResult;

 

     static const bool value = TryOthersResult::value;

     typedef typename TryOthersResult::Result Result;

};

 

template<class Steps, class Tried> struct TryIt<Empty, Steps, Tried>{

     static const bool value = false;

     typedef Empty Result;

};

 

其中的TryOthers,会根据MoveIt<Steps, Tried>的结果,进行下一步动作。若MoveIt找到了解,TryOthers就不做任何动作,直接返回;否则它就调用TryIt<剩余Candidates, Steps, Tried>尝试其他的候选青蛙排列。TryOthers同样留给读者作为练习,读者可以参考附录(下载全部源代码)查看作者给出的参考答案。

 

打印输出

 

核心主程序完成后,还必须打印结果给用户,给出从青蛙排列到目标排列的移动过程。主程序MoveIt给出的答案Steps,其实是一个逆序过程。表中最前面的是目标状态,最后面的是起始状态。所以打印输出时需要先逆序再打印。实现一个列表逆序的程序,作者[3]中曾经给出过,这里不再赘述。读者可以参考附录(下载全部源代码)了解其详细实现。

 

Steps列表中存储的答案,都是用1,2,3表示的青蛙排列,看起来不是很直观,为此可以把数字1112333中的每一位拿出来减2后打印,这样打出来的就是-1, 0, 1这样的结果,和前面普通的C++程序一致了。这段打印程序代码如下:

 

template<class Steps> struct PrintSteps{

private:

     template<class ReverseSteps> struct ReversePrint{

          static void printDigit(long rawLine){

              if(rawLine < 10){

                   std::cout<<rawLine-2<<", ";

              }

              else{

                   printDigit(rawLine/10);

                   std::cout<<(rawLine % 10)-2<<", ";

              }

          }

 

          static void print(){

              long rawLine = ReverseSteps::First;

              printDigit(rawLine);

              std::cout<<"\n";

              ReversePrint<typename ReverseSteps::Rest>::print();

          }

     };

 

     template<> struct ReversePrint<Empty>{

          static void print(){std::cout<<"\n";}

     };

public:

     static void print(){

          ReversePrint<typename Reverse<Steps>::Result>::print();

     }

};

 

其思路是,首先将结果逆序排列,然后取出结果列表中的第一个代表青蛙排列的整数,调用printDigit将它打印出来。然后输出一个换行后,打印列表中的其余内容。printDigit函数首先通过递归调用,打印除个位以外的其余部分,然后通过进行模10运算,获得待打印数字的个位,将其减2后,打印出来,并在后面追加一个逗号。

 

最终程序的测试代码如下:

int main(int argc, char* argv[]){

typedef MoveFrog<1112333> MoveResult;

 

if(MoveResult::value == true){

          std::cout<<"Find a result: \n";

          PrintSteps<typename MoveResult::Result>::print();

}

else

          std::cout<<"No solution\n";

}

 

程序输出为:

Find a result:

-1, -1, -1, 0, 1, 1, 1,

-1, -1, 0, -1, 1, 1, 1,

-1, -1, 1, -1, 0, 1, 1,

-1, -1, 1, -1, 1, 0, 1,

-1, -1, 1, 0, 1, -1, 1,

-1, 0, 1, -1, 1, -1, 1,

0, -1, 1, -1, 1, -1, 1,

1, -1, 0, -1, 1, -1, 1,

1, -1, 1, -1, 0, -1, 1,

1, -1, 1, -1, 1, -1, 0,

1, -1, 1, -1, 1, 0, -1,

1, -1, 1, 0, 1, -1, -1,

1, 0, 1, -1, 1, -1, -1,

1, 1, 0, -1, 1, -1, -1,

1, 1, 1, -1, 0, -1, -1,

1, 1, 1, 0, -1, -1, -1,

 

结论

 

本文给通过移动青蛙游戏,给出了利用C++解决此问题的一个递归回溯算法。并且利用C++的编译期编程能力,进一步给出了一个完全的函数式编程实现。由于计算全部在编译期进行,所以该程序的调试比较困难。错误的程序会导致C++编译器陷入无限递归无法停止,从而直接造成编译器挂起,并生成巨大的.o目标文件。作者也暂时没有找到好的调试方法。一个可供参考的手段是,借助一个Lisp方言Scheme环境,给出一个纯函数式的实现,仔细移植到C++编译期代码,彼此参考对照,排除错误。

 

移植性

 

不同编译器对于C++ template meta programming的支持有所不同。这主要是各个编译器对于C++标准的支持不尽相同造成的。本文中的例子代码片断在Visual C++ 2005 Express版本上全部测试过。在附录中提供(可供下载的)例子代码时,作者使用了GNU的编译器g++ 3.4.4版本进行了测试。这个版本的编译器对内部类模板偏特化有一些额外的限制。在类模板内部嵌套定义类模板时(这相当于LISP方言Scheme中的Local定义),必须引用外部类模板的全部模板参数,才能进行偏特化。并且内部嵌套类模板,不得使用和外部同名的模板参数,否则就会出现Shelding问题。为此如果外部模板带有参数A,笔者就在内部类模板偏特化时,通过_A引用此参数,例如:

 

template<class A> struct Outter{

     template<class B, class _A> struct Inner;

    

     template<class _A> struct Inner<int, _A>{

          //...

          Outter<_A>

     };

}; 

 

这样_A就既能满足不隐藏覆盖A的要求,在内部类模板偏特化时引用了全部参数。因此附录中(可供下载)的代码会和文中的例子代码略有差异。

 

参考书目:

[1] WikiPedia, Depth-frist search. http://en.wikipedia.org/wiki/Depth-first_search

[2] Liu Xinyu, Scheme and C++ template. 2006, June. http://liuxinyu95.googlepages.com/softdev.books.book1.essay7.chn

[3] Liu Xinyu, C++ template programming. 2006, July. http://liuxinyu95.googlepages.com/softdev.books.book1.essay8.chn

 

附录

 

  1. 点击下载:移动青蛙的Flash游戏
  2. 点击下载:普通的C++移动青蛙游戏的源代码
  3. 点击下载:编译期编程的C++移动青蛙游戏的源代码
  4. 点击下载:Lisp方言Scheme实现的移动青蛙游戏的源代码

 


 

[English][上一篇][目录][下一篇][主页][联系我们: liuxinyu95@gmail.com]

  

ċ
Xinyu LIU,
Apr 9, 2012, 1:50 AM
ċ
Xinyu LIU,
Apr 9, 2012, 1:50 AM
Comments