回溯法，是一种常用的枚举求解子空间的一种思想。在搜索过程中尝试找到问题的解。如果将每个状态空间看作是一个结点，则回溯查找解路径的过程有点类似于图或者树的深度优先遍历。当未达到终点时，一直往下遍历，如果遇到这条路径无解，则回溯到上一个可行结点，再往其他方向搜索。

方法：联想到二叉树的深度优先遍历，可以规划成递归的形式，或者用栈保存求解路径。

 

 下面通过一个迷宫寻路问题来归纳出比较通用的回溯法的步骤。

 

迷宫寻路问题：问题：给定一个迷宫，找到从入口到出口的所有可行路径，并给出其中最短的路径

 分析：用二维数组来表示迷宫，则走迷宫问题用回溯法解决的的思想类似于图的深度遍历。从入口开始，选择下一个可以走的位置，如果位置可走，则继续往前，如果位置不可走，则返回上一个位置，重新选择另一个位置作为下一步位置。

        N表示迷宫的大小，使用Maze[N][N]表示迷宫，值为0表示通道（可走），值为1表示不可走（墙或者已走过）；

        Point结构体用来记录路径中每一步的坐标(x,y)

       (ENTER_X,ENTER_Y) 是迷宫入口的坐标

       (EXIT_X, EXIT _Y)    是迷宫出口的坐标

       Path容器用来存放一条从入口到出口的通路路径

       BestPath用来存放所有路径中最短的那条路径

 

1 #include 
      
           2 #include 
       
            3      4 using namespace std;    5      6 typedef struct    7 {    8     int x;    9     int y;   10 }Point;   11     12 #define N 10         //迷宫的大小   13 #define ENTER_X 0    //入口的位置（0，0）   14 #define ENTER_Y 0   15 #define EXIT_X N-1   //出口的位置(N-1,N-1)   16 #define EXIT_Y N-1    17     18     19 int Maze[N][N]//定义一个迷宫，0表示通道，1表示不可走（墙或已走）   20 int paths;     //路径条数   21 vector
        
          Path;//保存一条可通的路径   22 vector
         
           BestPath;//保存最短的路径   23     24     25 //初始化迷宫   26 void InitMaze()   27 {   28 
            //简单起见，本题定义一个固定大小10*10的迷宫   29 
            //定义一个迷宫，0表示通道，1表示墙(或不可走)   30     int mz[10][10]={   31     {
    0,0,1,1,1,1,1,1,1,1}, //0   32     {
    1,0,0,1,1,0,0,1,0,1}, //1   33     {
    1,0,0,1,0,0,0,1,0,1}, //2   34     {
    1,0,0,0,0,1,1,0,0,1}, //3   35     {
    1,0,1,1,1,0,0,0,0,1}, //4   36     {
    1,0,0,0,1,0,0,0,0,1}, //5   37     {
    1,0,1,0,0,0,1,0,0,1}, //6   38     {
    1,0,1,1,1,0,1,1,0,1}, //7   39     {
    1,1,0,0,0,0,0,0,0,0}, //8   40     {
    1,1,1,1,1,1,1,1,1,0}  //9   41     //   0 1 2 3 4 5 6 7 8 9   42     };    43     44     //复制到迷宫   45     memcpy(Maze,mz,sizeof(mz));   46     47     paths = 0;   48 }   49     50 //从(x,y)位置开始走；初始为(0,0)   51 bool MazeTrack(int x,int y)   52 {   53     ///   54     //当前点加入到路径   55     bool hasPath = false; 56     Point p={x,y};   57      58     if ( x < N && x>=0 && y
          
           0 && Maze[x][y]==0) 59     {    Path.push_back(p);   60         Maze[x][y] = 1;         //设置为已走，不可走   61       62     //cout<<"来到("<
           
            <<","<
            
             <<")"<
             
              ::iterator it; 74 for(it=Path.begin();it!=Path.end();++it) 75 { 76 cout<<"("<
              
               x<<","<
               
                y<<") "; 77 } 78 cout<
                
                 ::iterator it; 141 for(it=BestPath.begin();it!=BestPath.end();++it) 142 { 143 cout<<"("<
                 
                  x<<","<
                  
                   y<<") "; 144 } 145 cout<
                  
                 
                
               
              
             
            
           
          
         
        
       
      

 

总结归纳一下回溯法求解路径的模板，如下：

 

1 using namespace std; 2 #define N 100   3 #define M 100 4  5 typedef struct   6 {   7        int x;   8        int y; 9 }Point; 10  11 vector
     
      solutionPath ;  //存放有解的坐标路径12 13 //主函数 x,y默认为起始结点，如(0,0), 得到从起始结点到目的结点的路径。14 bool hasSolutionFunction( template
      
       * Matrix , int x, int y)15 {16         17     bool *visited = new bool[M*N]; 18     memset (visited,0,M*N); //visited 存放每个结点是否被遍历，true为已经遍历过，false为否19     20     res =  hasSolutionCore(Matrix , x ,y)21     cout<
       
        <
        
         *  Matrix , int x, int y)28 {29     30     hasSolution = false;31     Point p = Point(x,y);32     33 34         35     if (x,y) is terminal  //x,y 已经是终止条件，当求解到这个结点是叶结点或目的地    36         {37         solutionPath.push_back(p);38         return true;39         }40 41     if ((x,y) && visited[x][y]==flase )// x,y是合法结点(具体条件可扩展)，且未被访问过42     {43         visited[x][y] = true;44         solutionPath.push_back(p);45         46         hasSolution = hasSolutionCore(Matrix,x-1, y) ||hasSolutionCore(Matrix,x,y-1)||... //如果不是叶结点，则该路径是否有解取决于其他方向的往后求解。47         48         // x,y结点以下的所有子路径都无解，则回溯49         if (!hasSolution)50         {51         visited[x][y] = false;52         solutionPath.pop_back();53         }54         55     }56     return hasSolution;57     58 }
        
       
      
     

 

 

#include <iostream>  #include <vector>     using namespace std;     typedef struct  {      int x;      int y;  }Point;     #define N 10         //迷宫的大小  #define ENTER_X 0    //入口的位置（0，0）  #define ENTER_Y 0  #define EXIT_X N-1   //出口的位置(N-1,N-1)  #define EXIT_Y N-1         int Maze[N][N]//定义一个迷宫，0表示通道，1表示不可走（墙或已走）  int paths;     //路径条数  vector<Point> Path;//保存一条可通的路径  vector<Point> BestPath;//保存最短的路径        //初始化迷宫  void InitMaze()  {  <span style="white-space:pre">  </span>//简单起见，本题定义一个固定大小10*10的迷宫  <span style="white-space:pre">  </span>//定义一个迷宫，0表示通道，1表示墙(或不可走)      int mz[10][10]={      {0,0,1,1,1,1,1,1,1,1}, //0      {1,0,0,1,1,0,0,1,0,1}, //1      {1,0,0,1,0,0,0,1,0,1}, //2      {1,0,0,0,0,1,1,0,0,1}, //3      {1,0,1,1,1,0,0,0,0,1}, //4      {1,0,0,0,1,0,0,0,0,1}, //5      {1,0,1,0,0,0,1,0,0,1}, //6      {1,0,1,1,1,0,1,1,0,1}, //7      {1,1,0,0,0,0,0,0,0,0}, //8      {1,1,1,1,1,1,1,1,1,0}  //9      //   0 1 2 3 4 5 6 7 8 9      };          //复制到迷宫      memcpy(Maze,mz,sizeof(mz));         paths = 0;  }     //从(x,y)位置开始走；初始为(0,0)  bool MazeTrack(int x,int y)  {      ///      //当前点加入到路径  bool hasPath = false;    Point p={x,y};  if ( x < N && x>=0 && y<N && y>0 && Maze[x][y]==0)    {Path.push_back(p);  Maze[x][y] = 1;         //设置为已走，不可走       //cout<<"来到("<<x<<","<<y<<")"<<endl;        //如果该位置是出口，输出结果  if(x == EXIT_X && y== EXIT_Y)  {          cout<<"找到一条道路"<<endl;          paths++;  hasPath = true;                  //输出路径          vector<Point>::iterator it;          for(it=Path.begin();it!=Path.end();++it)          {              cout<<"("<<it->x<<","<<it->y<<") ";          }          cout<<endl;             //判断是否更优          if(BestPath.size()==0)//如果是找到的第一条路径，直接复制到最优路径          {              for(it=Path.begin();it!=Path.end();++it)              {                  BestPath.push_back(*it);              }  

        }          else //不是第一条，则判断是否更短          {              //更短，复制到最优路径              if(Path.size()<BestPath.size())              {                  BestPath.clear();                  for(it=Path.begin();it!=Path.end();++it)                  {                      BestPath.push_back(*it);                  }              }          }return hasPath}     ///  //判断(x,y)位置的上、下、左、右是否可走  hasPath =  MazeTrack(x-1,y) || MazeTrack(x+1,y) || MazeTrack(x,y-1) || MazeTrack(x,y+1)   if (!hasPath){//返回上一步  Path.pop_back();  Maze[x][y] = 0;         //设置为未走  }}return hasPath

}        int main(int argc, char* argv[])  {      //初始化迷宫      InitMaze();            /*  //显示迷宫     for(int i=0;i<N;++i){         for(int j=0;j<N;++j)             cout<<Maze[i][j]<<"  ";         cout<<endl;     }*/         //回溯法走迷宫      MazeTrack(ENTER_X,ENTER_Y);         //显示最优的路径      cout<<"可行路径总条数为"<<paths<<"；最优路径为"<<endl;      vector<Point>::iterator it;      for(it=BestPath.begin();it!=BestPath.end();++it)      {          cout<<"("<<it->x<<","<<it->y<<") ";      }      cout<<endl;      return 0;  }