05 回溯法

  我们来考虑一个非常简单的问题：求5的全排列并且打印出结果。

   如果你没有学习过算法，或许你在初次遇到这个问题时会有这样的想法（我也是）。那就是穷举法。

void enum1(){

       int i1,i2,i3,i4,i5;

       for(i1=1;i1<=5;i1++)

              for(i2=1;i2<=5;i2++)

                     for(i3=1;i3<=5;i3++)

                            for(i4=1;i4<=5;i4++)

                                   for(i5=1;i5<=5;i5++)

                                          if(i1!=i2 && i1!=i3 && i1!=i4 && i1!=i5 &&

                                             i2!=i3 && i2!=i4 && i2!=i5 &&

                                             i3!=i4 && i3!=i5 &&

                                             i4!=i5)

                                             cout<<i1<<i2<<i3<<i4<<i5<<endl;

}

在写那一大堆if的条件时，可能头都晕了。当然可以有好的方法判断n个数是否都不同，判断n个数不同可以用递归：

   BOOL NoEqualElem(int *A,int n){

       if(n==1)  return TRUE;

       for(int i=1;i<n;i++)

         if(A[i]==A[0])

           return FALSE;

       return NoEqualElem(&A[1],n-1);

    }

O(n²)的时间复杂度。

更好的办法是先把这n个数排序，然后顺序扫描，比较相邻的元素有没有相同的。或者修改排序算法，在排序过程中判断，最坏的复杂度是O(nlogn)。

但要是求n（n在运行时输入）的排列怎么办呢？

上面的方法显然是不好的。那么有什么好的方法吗？

我们的目标是把所有的可能解都尝试一遍。

在这个例子中所有的解有：

   (1,1,1,1,1),(1,1,1,1,2),……,(1,1,1,1,5)

   (1,1,1,2,1),(1,1,1,2,2),……,(1,1,1,2,5)

   ……

   共5⁵＝3125种

如果我们能为每一个可能解编上号码，那么我们就可以用一个循环尝试所有的可能解了。在这个例子中我们可以把一个可能解看出一个5位的5进制数（每个位的取值是{1,2,3,4,5}）。i1,i2,i3,i4,i5分别对应到第5，4，3，2，1位。

void enum2(){

     int n=3125;

     int i1,i2,i3,i4,i5;

     for(int i=0;i<3125;i++){

            int k=i;

            i5=k%5+1;

            k/=5;

            i4=k%5+1;

            k/=5;

            i3=k%5+1;

            k/=5;

            i2=k%5+1;

            k/=5;

            i1=k%5+1;

            k/=5;

            if(i1!=i2 && i1!=i3 && i1!=i4 && i1!=i5 &&

              i2!=i3 && i2!=i4 && i2!=i5 &&

              i3!=i4 && i3!=i5 &&

              i4!=i5)

                   cout<<i1<<i2<<i3<<i4<<i5<<endl;

     }//for i

}

但要是每个数的取值不同，比如第一个可以取1－6，其余的是1－5，那么计算起来就比较麻烦。我们也可以把每位看成一个计数器，低位计数到最大数时向高位产生进位。用0表示初始值，初始为（0，0，0，0，0）。只要每次求它的下一个比它大的最小数就可以了。

比（0，0，0，0，0）大的最小5位数是（1，1，1，1，1），然后一直到（1，1，1，1，5），比5＋1＝0，产生进位变成（1，1，1，2，0），这是一个4位数，然后要产生最小的5位数（1，1，1，2，1），……，直到（1，1，1，5，5）。第5位的5+1=0，产生进位，第4位5＋1＝0，产生进位，得到（1，1，2，0，0）这也不是一个合法的5位数，依次取合法的最小的数（1，1，2，1，1），以次类推，使每一个“数”都被尝试过一次且仅一次。

在上面的过程中我们看到是1，2，3，4，5位依次产生，进位时是从后向前，因此可以使用栈来实现。k表示栈顶的指针，X[1…n]是栈。给X[k]找一个最小的值，k等于5则表明它是一个5位数，可以判断是否满足条件，如果k小于5，则要给下一位找一个值。当k＝＝0时表明第1位的所有可能值都尝试过了。即所有的值都尝试过了。

void enum3(){

     int n=5;

     int k=1;

     int *X=new int[n+1];//第0位不使用。

     for(int i=0;i<=n;i++)

            X[i]=0;

    

     while(k>0){

            int next=(X[k]+1)%(n+1);

            if(next!=0){

                   X[k]=next;

                   if(k==n){

                          if(NoEqualElem(&X[1],n)==TRUE){

                                 for(int j=1;j<=n;j++)

                                        cout<<X[j];

                                 cout<<endl;

                          }

                   }

                   else

                          k++;

            }

            else

            {

                   X[k]=0;

                   k--;//产生进位。

            }

     }

    

     delete [] X;

}

比如现在栈为（1，1，5，5，5），k＝5，第5位的next（下一个值）＝0，产生进位，k--，第4位的next也是0，产生进位，k――＝3，还是产生进位，k＝2，next＝2，然后k＋＋＝3，X[k]＝1；k＋＋＝4，X[k]＝1，……。

  也可以使用递归来实现穷举。给n位数的每一位赋一个值可以看出先给第一位赋值，然后递归给n－1位数赋值。

void enum4(int *X,int n,int k){

  for(int i=1;i<=n;i++){

         X[k]=i;

         if(k==n){

                       if(NoEqualElem(&X[1],n)==TRUE){

                              for(int j=1;j<=n;j++)

                                     cout<<X[j];

                              cout<<endl;

                       }

         }

         else

                enum4(X,n,k+1);

  }

}

 

在上面的例子中，我们发现（1，1，1，1，1），（1，1，1，1，2），…，（1，1，5，5，5）都是不可能满足条件的，因为它的第1，2位相同。我们在给每一位找next值时如果它在前面已经出现过了，那么它不可能满足最后的条件。也就是把最后的判断放到生成每一位的过程种进行。

假设一个问题是给一个n元组（X₁,X₂,…,X_n）的每一元取一个值，X_i  属于S_i （上面例子S_i ={1,2,3,4,5}），使它满足一定条件（上面例子的条件是：如i!=j,则Xi!=Xj）。

穷举法是列举所有的可能，然后有条件进行判断。而回溯法不仅在最后判断，而且在列举的过程中也进行判断。当然列举过程中的条件是最终条件的必要条件。具体点说：最终条件是“X1!=X2 and X1!=X3 and ……”，而“X1!=X2”是它的必要条件。

以上面的例子为例，穷举法列举所有的可能，而不去考虑当前要生成的元（位）与以前生成的元的关系。比如第1位是1，那么第2位它仍然会生成1，它不会考虑最终条件的一个必要条件X1!=X2。而回溯法就会在生成当前元是用最终条件的一个必要条件去淘汰一些不满足的取值（不满足最终条件的必要条件自然不会满足最终条件）。

下面是回溯法的一般形式：

void BackTrack(){

   int X[1…n];

   k=1;

   while(k>0){

       if(还存在X[k]属于S_k 且X[1],X[2],…,X[k]满足最终条件的必要条件){

           if(X[1],X[2],…X[k]是原问题的一个解)

                输出;

           else

               k++;

       }

       else

          k--;

   }//while k

}//BackTrack

 

递归形式为：

void BackTrack(X[1…n],int k){

     //前面X[1],…X[k-1]都已经有了值。

     for(X[k]属于S_k 且X[1],X[2],…,X[k]满足最终条件的必要条件){

           if(X[1],X[2],…X[k]是原问题的一个解)

                输出;

           else

                BackTrack(X[1…n],k+1);

     }//for

}//BackTrack

 

来看例子，还是求5的全排列。先看递归。

BOOL IsValid(int *X,int k,int i){

  for(int j=1;j<k;j++){

         if(X[j]==i)

                return FALSE;

  }

  return TRUE;

}

 

void backtrack1(int *X,int n,int k){

  int i;

  for(i=1;i<=n;i++){

        if(IsValid(X,k,i)==TRUE){

                X[k]=i;

                if(k==n){

                              for(int j=1;j<=n;j++)

                                     cout<<X[j];

                              cout<<endl;

                       }

                else

                       backtrack1(X,n,k+1);

 

         }//if(Is...

  }//for i

}

 

void backtrack2(int *X,int n){

  int k=1;

  while(k>0){

         int next=(X[k]+1)%(n+1);

         X[k]=next;

         if(next!=0){

                if(IsValid(X,k,next)==TRUE){

                       if(k==n){

                              for(int j=1;j<=n;j++)

                                     cout<<X[j];

                              cout<<endl;

                       }

                       else

                              k++;

                }

         }

         else

                k--;

  }

}

在判断第k位能不能放i时要依赖第1,2,…,k-1位。如果我们把哪些数字是否已经填在了某个位置的状态记录下来，则可以减少一些工作量。当然，我们在尝试把第k位放上i时要把i的状态改为已经使用过了；当回溯的时候还要改为没有使用。可以用一个数组used[]表示，used[1]=0表示1这个数没有使用，否则表示已经使用过了。

BOOL IsValid(int *X,int k,int i){

  for(int j=1;j<k;j++){

         if(X[j]==i)

                return FALSE;

  }

  return TRUE;

}

 

void backtrack3(int *X,int n,int k,int *used){

  for(int i=1;i<=n;i++){

        if(used[i]==0){

                X[k]=i;

                used[i]=1;

                if(k==n){

                              for(int j=1;j<=n;j++)

                                     cout<<X[j];

                              cout<<endl;

                       }

                else

                       backtrack3(X,n,k+1,used);

 

                used[i]=0;

 

         }//if(Is...

  }//for i   

}

 

**************************************************************************************************************************************************************

上面的东西写了快一年了，有的东西连我自己都记不清楚了，大家看不懂也没关系。主要是提出一些问题。1，怎么实现穷举；2，穷举和回溯的关系。

 

我们换一个角度来看。

还是求n个数的所有排列的问题。如果要求其中一个排列。我们可能会这样做：先把第一个位置放上1，第二个位置放上2，……，第n个位置放上n。我们考虑每次动作（放上数字）前后的状态。则最初的状态是(0,0,….,0)，0表示没有放上数字。把1放在第一个位置则使得它的状态变成了(1,0,0,…,0)，放2后变成（1,2,0,…0）。一直到放n变成(1,2,…,n)。

也就是说，我们希望从最初的状态变成解状态（也就是每个位置都非0，且任意两个位置的数字都不同）。初态(0,0,…,0)可以变成(1,0,…0),(2,0,….,0),…..,(n,0,…0)；也可以变成(0,0,….,1)。但我们可以假设不会变成(0,0,….,1)。因为如果(0,0,0)->(0,0,1)->(0,3,1)->(2,3,1)是从初态到解状态的变化过程的话，那么我们可以从(0,0,0)->(0,3,0)->(2,3,0)->(2,3,1)得到同样的解。还有像这样的变化也是不用考虑的：(0,0,0)->(1,0,0)->(0,0,0)->(2,0,0)。即把1放在第一个位置又拿走。这和不放上去没有什么区别。

所以我们可以假设状态的变化规则为：1，在从左到右第一个非零的位置把0变成非0；2，放上的数不得和前面的数相同。

我们可以把每个状态想象成一个节点，如果可以从一个状态转变成另一个状态则加上一条有向边。我们的目标是求从初态节点到一个（或所有）解节点的路径。

那么求解的过程是这样的：求初态节点到解节点的路径 当且仅当 求与初态节点相邻的所有节点到解节点的路径然后加上从初态节点到这个相邻节点的这条边。

这句话说起来很费劲，但应该不能理解。假设要从1->5,与1相邻的有2,3,4。那么从1到5的所有路径就是1->2(3,4)加上2(3,4)到5的所有路径。而求2(3,4)到5的路径又是一个相同的问题，可以递归求解。

 

 我们来看求n个数的全排列的方法。

 首先我们要用一种数据结构来表示所有的状态。按照前面的思路，用一个数组就可以了。另外还要有一个方法生成当前状态可以到达的状态（图中1可到达的是2，3，4）。最后需要一个方法判断某种状态是否是解状态。算法实现如下：

  public void Method1(int[] status){

    if(IsSolution(status)){

      for(int i=0;i<status.length;i++)

        System.out.print(status[i]);

      System.out.println();

      return;

    }

 

    List possibleChanges=GetPossibleChanges(status);

 

    int[] statusNew;

    for(int i=0;i<possibleChanges.size();i++){

      statusNew=(int[])possibleChanges.get(i);

      Method1(statusNew);

    }

  }

算法很简单：如果当前状态是解 if(IsSolution(status)){ ，则输出这解并返回。如果不是则先求出这个状态可能到达的所有状态 ：List possibleChanges=GetPossibleChanges(status); 然后递归调用求出这些状态到解状态的方法 Method1(statusNew);

再来看实现细节。

  private List GetPossibleChanges(int [] status){

    //找到第一个非0的位置

    int pos=0;

    while(status[pos]!=0&&pos<status.length)

      pos++;

    if(pos==status.length)

      return null;

    List allChanges=new ArrayList();

    int j;

    for(int i=1;i<=status.length;i++){

      for(j=0;j<pos;j++){

        if(i==status[j])

          break;

      }

      if(j==pos){

        int[] newStatus=new int[status.length];

        for(int k=0;k<status.length;k++)

          newStatus[k]=status[k];

        newStatus[pos]=i;

        allChanges.add(newStatus);

      }

    }

    return allChanges;

  }

  这个算法很罗嗦，但思路还是比较简单的。首先找到第一个非0的位置，然后把从1到n的数和前面的数比较，如果前面没有出现过，就是合理的新状态。

  判断是否是解看起来应该是这样：检查n个位置都非0，并且任意两个位置都不相同。但实际上只要判断最后一个位置非0就可以了，因为我们是从左到右的放上数字的，而且生成状态的方法保证了这n个位置都不相同。可以看出，最费时间的操作是生成新状态的方法。

  在上面的实现中生成新状态是完全的。比如初态是(0,0,0)，那么由它生成的状态是(1,0,0),(2,0,0)和(3,0,0)。我们返回的是包含(1,0,0),(2,0,0)和(3,0,0)的一个List。如果我们想节省一点空间，我们只要返回1,2,3就可以了（这就不是完全的状态，而是状态的变化）。然后我们还要知道是在第一个非0的地方填上这些数字，如果不想每次搜索数组以得到第一个非0的位置，也可以把它存在一个变量中。

  除了这些外，还有一个重要的优化就是GetPossibleChanges，它每次都有把1到n的数和前面的数比较。比如现在要放最后一位，则要1+2+3+…+n-1+n次比较（前面出现过的数字共要比较(1+2+…+n-1)次，没有出现的n次）。我么考虑一下如果要让我们手工来放会怎么样。比如我们知道第一个位置可以放1到n的任意数，然后放第二个位置时可以放除了第一个位置的所有数，第三个位置可以放除了前面两个位置的任意数，……。因此我们可以使用一个辅助的数据结构，表示当前状态还有哪些数没有放过。当然我们有责任维护这个数据结构以便当状态改变时这个数据结构也相应的改变。

   public void Method2(int []status,boolean[] used,int curPos){

    if(curPos==status.length){

      for(int i=0;i<status.length;i++)

        System.out.print(status[i]);

      System.out.println();

      return;

    }

 

    for(int value=1;value<=status.length;value++){

      if(used[value-1]==false){

        used[value-1]=true;

        status[curPos]=value;

        Method2(status,used,curPos+1);

        used[value-1]=false;

        status[curPos]=0;

      }

    }

  }

  Method2使用了一个布尔型数组used来表示当前状态下哪些数字用过没有。和前面的Method1比较，你会发现没有了生成新状态的GetPossibleChanges函数。它到哪里去了呢？因为有了used数组，只要扫描1到n的数，看它们是否被用过，如果没有，就是一个新的状态。另外，每次把新状态都放到newStatus中很费时，我们可以直接使用status，只要在使用后保证和使用前面一样就可以了。

  还有没有可以改进的地方呢？比如现在已经有n－1个数已经被“使用过”了，上面的算法还是会扫描所有这n－1个数。怎么避免呢？最好是有一个数据结构来跟踪当前状态下哪些数没有使用过。而且当状态变化时，这个数据结构也跟着变化。用数组来实现显然不好，因为状态会经常变化，没有被“使用过”的数也得经常变化，所以链表是比较合适的。

  // helpers是一个带头节点的链表。

  public void Method3(int[] status,IntSLList helper,int curPos){

    if(curPos==status.length){

      for(int i=0;i<status.length;i++)

        System.out.print(status[i]);

      System.out.println();

      return;

    }

 

    IntNode preNode=helper.head;

    IntNode curNode=preNode.next;

    for(;curNode!=null;curNode=curNode.next){

      int possibleValue=curNode.info;

      status[curPos]=possibleValue;

      //暂时删除curNode。

      preNode.next=curNode.next;

      Method3(status,helper,curPos+1);

      //恢复curNode。

      status[curPos]=0;

      curNode.next=preNode.next;

      preNode.next=curNode;

 

      //进入下次循环。

      preNode=curNode;

    }

  }

 

 通过实际测试，发现Method3的运行时间大概是Method2的一半（输出语句被注释掉了）。这是比较合理的，因为刚开始时没有被使用过的有n个，然后是n-1,…..，用Method3要1+2+…+n，而Method2要n*n。

 还有没有更好的办法呢？

 我们看Method3，当n＝4时，最开始可以使用的是1234，当我们把第一个位置放上1以后，可用的是234；当第一个位置放2的时候，可用的是134。但链表可能比较费时，我们能不能使用顺序表（数组）呢？比如开始是1234，使用了2，如果是链表就应该把2删除出链表。数组的话删除2就变成了1x34了（x表示这个位置空着）。当然如果把1x34传给后面的递归函数的话，它还得扫描4个而不是我们希望的3个。那么我们把它对齐，传递x134个后面，然后告诉它从第2个位置开始的数是没有使用过的。

那么如果第一个位置如果使用了4，就是123x，要把它变成x123就得移动4次（因为是数组表示的线性表）。这看起来似乎不是一个好的办法。因为链表的话不用移动元素，只是暂时把它删除出去，最后在恢复过来就行了。

不过上面只是单个的考虑，如果整体来考虑就不一样了。

比如现在可用的是1234，那么我们要把1放在位置1上面，然后传递参数1234，从第二个位置开始（也就是说传的是234，但为了借用一份空间），递归调用；把2放在位置1上面，传递参数2134，从2开始；把3放在位置1上，传递参数3124；把4放在1位置1上，传递参数4123。

这又怎么样呢？第一次可以什么也不干，直接把1234传递给后面；第二次可以把第一个位置和第二个位置交换，得到2134；第三次把第一个位置和第三个位置交换（不是最初的1234交换，而是前面交换后的2134）得到3124；第四次把第一个位置和第四个位置交换，得到4123。这样每次都只交换一次就可以了。那么你是怎么想到这些的呢？我也没有想到。而是看到了一个生成排列的算法，而且看得不是很明白。想了好久，终于找到一种理解的方法，这个算法等下再说。为了统一，可以把第一次看做第一个位置和第一个位置的交换。另外，在这次调用使用完了后，还得保证原来的可用参数。比如如果我们不管的话，1234经过四次使用后就变成了4123，234经过三次使用后会变成423。那么就会出问题。比如现在是1234，我们先使用1，然后传递234给后面，后面使用了234后把它变成非234了。那么我们把一个位置和的二个位置交换就不是我们期望的2134了。那么会不会比较巧合，虽然不是234了但仍然能够通过交换而使用到所有的数呢？比如使用1，传递234，后面把它变成了423，返回后得到1423，交换12位置得到4123，使用4，传递123，后面把它变成了231，返回后得到4231，交换13位置得到3241，使用3，传递241如果最后一次把它变成了412，则返回后得到3412，交换14位置得到2413，最后使用2。虽然使用的顺序不是1234了，但如果恰好保证每个都使用过一次也是没有问题的（如果把1234看出四位数，则输出的顺序不是递增的了）。可惜不行（测试证明），因为使用1然后传递234，234使用2传递34，大家都不保证使用后和使用前面一样那么经过n次使用后是什么样子？事实上当n＝4时，经过debug观察，发现使用1传递234返回后变成了1243，使用2传递143返回后变成了2134，使用3传递124返回后变成了3142，则第四次又使用了2传递143，而4根本没有被使用过。

因此使用后还得恢复，我们发现，使用后1234变成了4123，也就是最后一个数到了第一个位置，其它的数的位置后移了一个。

这样，我们就得到了Method5

   public void Method5(int[] status, int[] used, int curPos) {

    if (curPos == status.length) {

      for (int i = 0; i < status.length; i++)

        System.out.print(status[i]);

      System.out.println();

      return;

    }

    int tmp;

    for (int i = curPos; i < status.length; i++) {

      tmp = used[i];

      used[i] = used[curPos];

      used[curPos] = tmp;

      status[curPos] = tmp;

      Method5(status, used, curPos + 1);

    }

    tmp = used[curPos];

    for (int i = curPos; i < status.length - 1; i++) {

      used[i] = used[i + 1];

    }

    used[status.length - 1] = tmp;

  }

 

  再观察一下Method5中的status和used。比如现在n=4。刚开始，status=(0,0,0,0), used=(1,2,3,4) 使用1后，status=(1,0,0,0) used=(1,2,3,4) 使用2后，status=(2,0,0,0) used=(2,1,3,4) 先后使用123后，status=(1,2,3,0) used=(1,2,3,4) 先后使用了423后 status=(4,2,3,0) used=(4,2,3,1)。也就是说如果status=(a,b,c,0)，则used=(a,b,c,d)。为什么？因为status先放上a，则传递给后面的是bcd，再使用b，传递给后面的是cd，使用c，传递给后面的是d。即从0到curPos-1位status和used总是相同的。而我们为什么要使用status呢？为了表示一个状态，那么直接用used配合curPos就可以表示status了，因为前curPos-1位相同，而从curPos-1开始的位时status都等于0。

 把Method5中的status和used合并成一个变量，就得到Method4

   public void Method4(int []status,int curPos){

    if(curPos==status.length-1){

      //for(int i=0;i<status.length;i++)

      //  System.out.print(status[i]);

      //System.out.println();

      return;

    }

    int tmp;

    for(int i=curPos;i<status.length;i++){

      tmp=status[i];

      status[i]=status[curPos];

      status[curPos]=tmp;

      Method4(status,curPos+1);

 

    }

    tmp=status[curPos];

    for(int i=curPos;i<status.length-1;i++){

      status[i]=status[i+1];

    }

    status[status.length-1]=tmp;

 

  }

  细心的朋友可能发现Method4怎么是由Method5得来的呢（习惯一般是先写Method4，然后再写Method5）？实际上我是通过Method4发现Method5的。Method4是比较流行的求排列的算法（很多算法书都有），但我看了那些书的解释后都不太明白，仔细思考后找到了一种解释方法，那就是Method5。Method4好像出自”Thingking Recursively” 这本书，可惜我找不到这本书，也不知道里面是怎么解释这个算法的。除了Method5的解释外，我自己还得到一种理解方法。

  问题是求n个元素的全排列。这n个元素放到了status数组中。

  我们把问题“加强”一点。把问题描述成：求status数组中n个元素的全排列，并且要求求完后status数组还得保持不变。运用递归的思想，可以先求后面n－1个元素的全排列，求完后status数组保持不变。然后交换第一个和第二个，因为status不变，得到第二个没有使用过的元素，再交换第三个，……。

  我们发现第一次调用后可以不恢复status，不过这点计算根本不费时间（参考Method6和Method7），而且还导致输入参数被改变。经过测试，可以发现Method4最快，Method5比Method3稍微快一点，都大约是Method4的两倍。Method2大约是Method3的两倍。Method1没有任何优化，比Method3慢差不多10倍，它只不过用来解释算法的一般框架而已。Method5是Method4的两倍比较好理解：Method4只维护status数组的顺序，而Method5要维护status和used两个几乎一样的数组。

  可能你觉得费这么大的力气优化一个算法没有什么意思。而且都是一个数量级的，能快得了几倍？买个好的CPU就解决了。我也不知道这种看法对不对，不过如果有闲工夫，看看也不错。

 

  在生成所有可能状态时有两种办法，一种是一步到位的方法，一次全求出来；另一种则是只求一个，用完之后再求下一个。比如Method1就是第一种，而Method4是第二种。当然第二种好些，因为它省了不是空间，但需要多一点技巧。

  你可能觉得这和你学过的回溯不同。而且从形式上看也没有“回溯”。我们可以把这个递归求解的过程看出搜索一棵树：初态是根，每个状态可以生成的新状态就是它的子节点。上面的算法都是“先根序”遍历的。如果把它化成非递归的就有回溯了。

  非递归遍历一棵树的关键是要保存父节点的信息，遍历树以后再说。