VC++2012编程演练数据结构《8》回溯法解决迷宫问题

大灰狼

回溯法(探索与回溯法)是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

可用回溯法求解的问题P，通常要能表达为：对于已知的由n元组（x1，x2，…，xn）组成的一个状态空间E={（x1，x2，…，xn）∣xi∈Si ，i=1，2，…，n}，给定关于n元组中的一个分量的一个约束集D，要求E中满足D的全部约束条件的所有n元组。其中Si是分量xi的定义域，且 |Si| 有限，i=1，2，…，n。我们称E中满足D的全部约束条件的任一n元组为问题P的一个解。
解问题P的最朴素的方法就是枚举法，即对E中的所有n元组逐一地检测其是否满足D的全部约束，若满足，则为问题P的一个解。但显然，其计算量是相当大的。

迷宫按照数组来组织

int mase[m][n]={{0,0,0,1,0,0},{0,1,0,0,0,0},{0,1,1,1,1,0},{0,0,0,0,0,1},{1,0,1,1,0,0}};

创建迷宫类如下

[cpp] view plaincopy

• //使用回溯法求解迷宫问题  
• #include<iostream.h>  
• #include<iomanip.h>  
• #include<stdlib.h>  
• #include<fstream.h>  
• //路口的结构体定义  
• typedef struct  
• {int left;  
• int forward;  
• int right;  
• }InterS;  
• //迷宫类定义与实现  
• class Maze  
• {private:  
•   int mazeSize;//路口个数  
•   int Exit;    //出口  
•   InterS *intSec;//路口集合  
• public:  
• //构造函数  
•   Maze(char *filename);  
• //搜索函数  
•   int TravMaze(int intSecV);  
• };  
• Maze::Maze(char *filename)  
• {ifstream fin;  
• fin.open(".\\1.dat",ios::in);//打开文件  
• if(!fin)  
• {cerr<<"数据文件无法打开!\n";exit(1);}  
• fin>>mazeSize;//读入路口个数  
• intSec=new InterS[mazeSize+1];//建立路口集合数组  
• for(int i=1;i<=mazeSize;i++)//读入所有路口的结构体数值  
•   fin>>intSec.left>>intSec.forward>>intSec.right;  
• fin>>Exit; //读入出口号码  
• fin.close();//关闭文件  
• }  
• int Maze::TravMaze(int intSecV)  
• {if(intSecV>0)  
•   {if(intSecV==Exit)//到达出口  
•     {cout<<intSecV<<"<==";//输出路口号码  
•      return 1;}  
•    else if(TravMaze(intSec[intSecV].left))//向左搜索  
•     {cout<<intSecV<<"<==";//输出路口号码  
•      return 1;}  
•    else if(TravMaze(intSec[intSecV].forward))//向前搜索  
•     {cout<<intSecV<<"<==";  
•      return 1;}  
•    else if(TravMaze(intSec[intSecV].right))//向右搜索  
•     {cout<<intSecV<<"<==";  
•      return 1;}  
•   }  
•   return 0;  
• }  
  

调用代码如下

[cpp] view plaincopy

• //迷宫类的测试  
• void main()  
• {cout<<"运行结果:\n";  
• cout<<"求解迷宫问题:\n";  
• char fileName[20]={".\\1.dat"};  
• Maze m(fileName);  
• int start=1;  
• if(m.TravMaze(start))  
•   cout<<endl<<"此迷宫的一条通路如上输出所示!\n";  
• else cout<<"此迷宫无通路!\n";  
• cin.get();  
• }  
  

效果如下