回溯法迷宫求最优路径

实 验 报 告

课程名称 算法设计与分析实验 实验名称________回溯法__________ 实验类型_______设计型____________ 实验地点_______计算机楼307 实验日期______ 2016年6月 _ 指导教师______________张威_____________

专 业_____软件工程__________ 班 级_____软件1301__________ 学 号_____1311030120_________

姓 名_____王振鑫__________ 成 绩______________

辽宁石油化工大学计算机与通信工程学院

1 / 5

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 Path; vector BestPath; bool First = true;

//初始化迷宫 void InitMaze() {

2 / 5

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::iterator it;

//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 //不是第一条，则判断是否更短 {

3 / 5

//更短，复制到最优路径 if(Path.size()=0 && Maze[x-1][y]==0) { MazeTrack(x-1,y); } if((x+1)=0 && Maze[x][y-1]==0) { MazeTrack(x,y-1); } if((y+1)

4 / 5

cout<<\可行路径总条数为\；最优路径为\ vector::iterator it;

for(it=BestPath.begin();it!=BestPath.end();++it) {

cout<<\ }

cout<

2.3实验截图

3实验心得

这次实验的内容很有代表性，通过上机操作实践与对问题的思考，

5 / 5

让我更深层地领悟到了回溯算法的思想。回溯算法的基本思路并不难理解，简单来说就是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。回溯法的基本做法是深度优先搜索，是一种组织得井井有条的、能避免不必要重复搜索的穷举式搜索算法。本次实验通过回溯法求解迷宫最优路径，把走过的路变为墙，如果不通则返回。把第一条路径保存，之后的每一条路径都与之对比，留下最短的路径，求出最优解。现在我学习回溯算法的时间还不长，理解还很浅显，以后要多加练习，这样才能做到熟练运用。

6 / 5