通过迷宫问题归纳回溯法

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

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

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

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

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

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

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

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

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

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

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

  1 #include <iostream>  
  2 #include <vector>  
  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<Point> Path;//保存一条可通的路径  
 22 vector<Point> BestPath;//保存最短的路径  
 23    
 24    
 25 //初始化迷宫  
 26 void InitMaze()  
 27 {  
 28 <span style="white-space:pre">  </span>//简单起见，本题定义一个固定大小10*10的迷宫  
 29 <span style="white-space:pre">  </span>//定义一个迷宫，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<N && y>0 && Maze[x][y]==0)
 59     {    Path.push_back(p);  
 60         Maze[x][y] = 1;         //设置为已走，不可走  
 61      
 62     //cout<<"来到("<<x<<","<<y<<")"<<endl;    
 63     
 64     //如果该位置是出口，输出结果  
 65         if(x == EXIT_X && y== EXIT_Y)  
 66         {  
 67         cout<<"找到一条道路"<<endl;  
 68         paths++;  
 69         hasPath = true;
 70         
 71           
 72         //输出路径  
 73         vector<Point>::iterator it;  
 74         for(it=Path.begin();it!=Path.end();++it)  
 75         {  
 76             cout<<"("<<it->x<<","<<it->y<<") ";  
 77         }  
 78         cout<<endl;  
 79    
 80         //判断是否更优  
 81         if(BestPath.size()==0)//如果是找到的第一条路径，直接复制到最优路径  
 82         {  
 83             for(it=Path.begin();it!=Path.end();++it)  
 84             {  
 85                 BestPath.push_back(*it);  
 86             }  
 87 
 88         }  
 89         else //不是第一条，则判断是否更短  
 90         {  
 91             //更短，复制到最优路径  
 92             if(Path.size()<BestPath.size())  
 93             {  
 94                 BestPath.clear();  
 95                 for(it=Path.begin();it!=Path.end();++it)  
 96                 {  
 97                     BestPath.push_back(*it);  
 98                 }  
 99             }  
100         }
101         
102         return hasPath
103         }  
104    
105         ///////////////////////////////////////  
106         //判断(x,y)位置的上、下、左、右是否可走  
107         
108         hasPath =  MazeTrack(x-1,y) || MazeTrack(x+1,y) || MazeTrack(x,y-1) || MazeTrack(x,y+1)
109        
110         if (!hasPath)
111         {
112             //返回上一步  
113             Path.pop_back();  
114             Maze[x][y] = 0;         //设置为未走  
115         }
116     
117     }
118     return hasPath
119 
120 }  
121    
122    
123 int main(int argc, char* argv[])  
124 {  
125     //初始化迷宫  
126     InitMaze();  
127           
128 /*  //显示迷宫 
129     for(int i=0;i<N;++i){ 
130         for(int j=0;j<N;++j) 
131             cout<<Maze[i][j]<<"  "; 
132         cout<<endl; 
133     }*/  
134    
135     //回溯法走迷宫  
136     MazeTrack(ENTER_X,ENTER_Y);  
137    
138     //显示最优的路径  
139     cout<<"可行路径总条数为"<<paths<<"；最优路径为"<<endl;  
140     vector<Point>::iterator it;  
141     for(it=BestPath.begin();it!=BestPath.end();++it)  
142     {  
143         cout<<"("<<it->x<<","<<it->y<<") ";  
144     }  
145     cout<<endl;  
146     return 0;  
147 }

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

 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<Point>solutionPath ;  //存放有解的坐标路径
12 
13 //主函数 x,y默认为起始结点，如(0,0), 得到从起始结点到目的结点的路径。
14 bool hasSolutionFunction( template<typename T>* 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<<solutionPath<<endl;
22     return res
23 
24 }
25 
26 //深度遍历求解路径的函数
27 bool hasSolutionCore(template<typename T>*  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; }