回溯法迷宫求最优路径

《回溯法迷宫求最优路径》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验报告课程名称算法设计与分析实验实验名称________回溯法__________实验类型_______设计型____________实验地点_______计算机楼307实验日期______2016年6月_指导教师______________张威_____________专业_____软件工程__________班级_____软件1301__________学号_____1311030120_________姓名_____王振鑫__________成绩______________8/5辽宁石油化工大学计算机与通

2、信工程学院1实验目的与要求1、初步掌握回溯算法2、熟悉回溯算法的基本原理与适用范围2、掌握迷宫求解问题的算法2实验内容2.1回溯法迷宫求解在一个10*10的棋盘上，生成一个可通行的迷宫通道，生成迷宫后，用回溯法求解迷宫。2.2实验代码#include#includeusingnamespacestd;8/5typedefstruct{intx;inty;}Point;#defineN10#defineENTER_X0#defineENTER_Y0#defineEXIT_XN-1

3、#defineEXIT_YN-1intMaze[N][N];intpaths;vectorPath;vectorBestPath;boolFirst=true;//初始化迷宫voidInitMaze(){intmz[10][10]={{0,0,1,1,1,1,1,1,1,1},{1,0,0,1,1,0,0,1,0,1},{1,0,0,1,0,0,0,1,0,1},{1,0,0,0,0,1,1,0,0,1},{1,0,1,1,1,0,0,0,0,1},{1,0,0,0,1,0,0,0,0

4、,1},8/5{1,0,1,0,0,0,1,0,0,1},{1,0,1,1,1,0,1,1,0,1},{1,1,0,0,0,0,0,0,0,0},{1,1,1,1,1,1,1,1,1,0}};//复制到迷宫memcpy(Maze,mz,sizeof(mz));paths=0;}//从(x,y)位置开始走；初始为(0,0)voidMazeTrack(intx,inty){//当前点加入到路径Pointp={x,y};Path.push_back(p);Maze[x][y]=1;//设置为已走if(x==EXIT_X

5、&&y==EXIT_Y)//找到出口{paths++;//cout<<"找到一条道路"<::iteratorit;//for(it=Path.begin();it!=Path.end();++it)//{//cout<<"("<x<<","<y<<")";//}//cout<

6、estPath.push_back(*it);}First=false;}else//不是第一条，则判断是否更短{//更短，复制到最优路径if(Path.size()=0&&Maze[x-1][y]==0){MazeTrack(x-1,y);}8

7、/5if((x+1)=0&&Maze[x][y-1]==0){MazeTrack(x,y-1);}if((y+1)

8、X,ENTER_Y);//显示最优的路径8/5cout<<"可行路径总条数为"<::iteratorit;for(it=BestPath.begin();it!=BestPath.end();++it){cout<<"("<x<<","<y<<")";}cout<