实验报告
课程名称算法设计与分析实验
实验名称________回溯法__________
实验类型_______设计型____________
实验地点_______计算机楼307
实验日期______ 2016年6月_
指导教师______________张威_____________
专业_____软件工程__________
班级_____软件1301__________
学号_____1311030120_________ 姓名_____王振鑫__________
成绩______________
辽宁石油化工大学计算机与通信工程学院
1实验目的与要求
1、初步掌握回溯算法
2、熟悉回溯算法的基本原理与适用范围
2、掌握迷宫求解问题的算法
2实验内容
2.1回溯法迷宫求解
在一个10*10的棋盘上，生成一个可通行的迷宫通道，生成迷宫后，用回溯法求解迷宫。
2.2实验代码
#include
#include
using namespace std;
typedef struct
{
int x;
int y;
}Point;
#define N 10
#define ENTER_X 0
#define ENTER_Y 0
#define EXIT_X N-1
#define EXIT_Y N-1
int Maze[N][N];
int paths;
vector
vector
bool First = true;
//初始化迷宫
void InitMaze()
{
int mz[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,1},
{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)
void MazeTrack(int x,int y)
{
//当前点加入到路径
Point p={x,y};
Path.push_back(p);
Maze[x][y] = 1; //设置为已走
if(x == EXIT_X && y== EXIT_Y) //找到出口
{
paths++;
//cout<<"找到一条道路"< vector //for(it=Path.begin();it!=Path.end();++it) //{ // cout<<"("< //} // cout< //判断是否更优 if(First)//如果是找到的第一条路径，直接复制到最优路径 { for(it=Path.begin();it!=Path.end();++it) { BestPath.push_back(*it); } First = false; } else //不是第一条，则判断是否更短 { //更短，复制到最优路径 if(Path.size() { BestPath.clear(); for(it=Path.begin();it!=Path.end();++it) { BestPath.push_back(*it); } } } } //判断(x,y)位置的上、下、左、右是否可走 if((x-1)>=0 && Maze[x-1][y]==0) { MazeTrack(x-1,y); } if((x+1) { MazeTrack(x+1,y); } if((y-1)>=0 && Maze[x][y-1]==0) { MazeTrack(x,y-1); } if((y+1) { MazeTrack(x,y+1); } //返回上一步 Path.pop_back(); Maze[x][y] = 0;//设置为未走 } int main(int argc, char* argv[]) { //初始化迷宫 InitMaze(); //回溯法走迷宫 MazeTrack(ENTER_X,ENTER_Y); //显示最优的路径 cout<<"可行路径总条数为"< vector for(it=BestPath.begin();it!=BestPath.end();++it) { cout<<"("< } cout< return 0; } 2.3实验截图 3实验心得 这次实验的内容很有代表性，通过上机操作实践与对问题的思考， 让我更深层地领悟到了回溯算法的思想。回溯算法的基本思路并不难理解，简单来说就是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。回溯法的基本做法是深度优先搜索，是一种组织得井井有条的、能避免不必要重复搜索的穷举式搜索算法。本次实验通过回溯法求解迷宫最优路径，把走过的路变为墙，如果不通则返回。把第一条路径保存，之后的每一条路径都与之对比，留下最短的路径，求出最优解。现在我学习回溯算法的时间还不长，理解还很浅显，以后要多加练习，这样才能做到熟练运用。
相关主题
文本预览