回溯法解决迷宫问题

1算法设计与分析课程设计题目：基于回溯法的迷宫问题学院：理学院专业：信息与计算科学姓名：边微学号：200910010218指导教师：闫少宏2用回溯方法解决迷宫问题一：概述：1.算法的概念算法（Algorithm）是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。或者看成按照要求设计好的有限的确切的计算序列，并且这样的步骤和序列可以解决一类问题。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。算法可大致分为基本算法、数据结构的算法、数论与代数算法、计算几何的算法、图论的算法、动态规划以及数值分析、加密算法、排序算法、检索算法、随机化算法、并行算法。2.算法的性质一个算法应该具有以下五个重要的特征：（1）输入：有零个或多个外部量作为算法的输入。（2）输出：算法产生至少一个量作为输出。（3）确定性：组成算法的每条指令清晰、无歧义。（4）有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。（5）算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成3.算法的复杂度同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。时间复杂度算法的时间复杂度是指算法需要消耗的时间资源。一般来说，计算机算法是问题规模n的函数f(n)，算法的时间复杂度也因此记作：T(n)=Ο(f(n))因此，问题的规模n越大，算法执行的时间的增长率与f(n)的增长率正相关，称作渐进时间复杂度。空间复杂度算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。二：回溯算法1、回溯算法也叫试探法，他是一种系统地搜索问题的解的方法。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。31.用回溯方法解决问题的一般步骤：1针对所给问题，定义问题的解空间，它至少包含问题的一个（最优）解。2确定易于搜索的解空间结构,使得能用回溯法方便地搜索整个解空间。3以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。问题的解空间通常是在搜索问题解的过程中动态产生的，这是回溯算法的一个重要特性。确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试,直到找到符合条件的位置就可以了回溯在迷宫搜索中使用很常见，就是这条路走不通，然后返回前一个路口，继续下一条路。回溯算法说白了就是穷举法。不过回溯算法使用剪枝函数，剪去一些不可能到达最终状态（即答案状态）的节点，从而减少状态空间树节点的生成。回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。三、迷宫问题的描述首先进入迷宫，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路返回，换一个方向再继续探索，直到所有肯呢过的通路都探索到为止。四、算法实现#includestdafx.h#includeiostream.h#includestring.h4#includestdio.hdoubledMeans=0,dWalkLen=10000;//dMeans表示走出迷宫的方法，dWalkLen表示当前走出迷宫最少步数charMaze[10][52]={{###################################################},{##################},{%#################################},{######################},{##########################},{########################},{#################################},{######################},{########################@},{###################################################},};//迷宫intMazeFlag[10][51];//迷宫的标志：0表示未走过，i(i=1,2,3,4)表示已经走过了,i表示方向。intMazeMin[10][51];//路径最小的迷宫的标志voidWalk(intnx,intny);//走迷宫的函数，nx是列，ny是行5voidPrintOut();//打印路径及迷宫的函数，同时比较获取路径较短的行走方法intJudge(intnx,intny,inti);//判断在第nx列ny行向第i个方向走是否可以,可以返回1否则返回0。//i=1表示向右，2表示向下，3表示向左，4表示向上voidWalk(intnx,intny){if(Maze[nx][ny]=='@')//判断是否走出迷宫，@是迷宫出口标志PrintOut();//走出则打印出迷宫及行走路径else//未走出迷宫{for(inti=1;i=4;i++)//四个方向逐个行走，i=1向右2向下3向左4向上{if(Judge(nx,ny,i))//如果列为nx行为ny的位置向i方向是否可以行走{MazeFlag[nx][ny]=i;//将标志位置i表明该位置向i方向可行走if(i==1)//分散处理，根据不同的i来确定下一步的位置，以便行走。Walk(nx,ny+1);elseif(i==2)Walk(nx+1,ny);elseif(i==3)6Walk(nx,ny-1);elseif(i==4)Walk(nx-1,ny);}}MazeFlag[nx][ny]=0;//如果4个方向都走不通，或者回朔则清空该点标志位，置为0表明未走过。}}voidPrintOut(){intnx,ny;doubledCount=0;dMeans++;coutThedMeanswaysis:endl;for(nx=0;nx10;nx++){for(ny=0;ny51;ny++){if(Maze[nx][ny]=='#')//＃表示墙cout#;elseif(MazeFlag[nx][ny]==0)//不是墙但未走过的地方用空格表示cout;7else//不是墙且走过的地方用*表示{cout.;dCount++;//走一步总步数加1}}coutendl;}coutThiswayuseddCountstepsendl;if(dCountdWalkLen)//如果此种方法的步数比以前方法中最少步数还要少，{//则将此种方法列为当前最少行走步数for(nx=0;nx10;nx++)for(ny=0;ny51;ny++)MazeMin[nx][ny]=MazeFlag[nx][ny];dWalkLen=dCount;}}intJudge(intnx,intny,inti){if(i==1)//判断向右可否行走{8if(ny50&&(Maze[nx][ny+1]==”||Maze[nx][ny+1]=='@')&&MazeFlag[nx][ny+1]==0)return1;elsereturn0;}elseif(i==2)//判断向下可否行走{if(nx9&&(Maze[nx+1][ny]==””||Maze[nx+1][ny]=='@')&&MazeFlag[nx+1][ny]==0)return1;elsereturn0;}elseif(i==3)//判断向左可否行走{if(ny0&&(Maze[nx][ny-1]==””||Maze[nx][ny-1]=='@')&&MazeFlag[nx][ny-1]==0)return1;elsereturn0;}elseif(i==4)//判断向上可否行走9{if(nx0&&(Maze[nx-1][ny]==””||Maze[nx-1][ny]=='@')&&MazeFlag[nx-1][ny]==0)return1;elsereturn0;}Elsereturn0;}intmain(intargc,char*argv[]){intnx,ny,ni,nj;cout迷宫游戏:endl;for(ni=0;ni10;ni++)//输出迷宫形状，并且找到迷宫的入口，同时将迷宫标志初始化{for(nj=0;nj51;nj++){coutMaze[ni][nj];MazeFlag[ni][nj]=0;//将迷宫标志初始化为0表示未走过if(Maze[ni][nj]=='%'){nx=ni;//迷宫入口列坐标10ny=nj;//迷宫入口行坐标}}coutendl;}coutendl入口坐标:endlnx=nxny=nyendl;Walk(nx,ny);//调用行走迷宫函数，从入口处开始行走coutendlTheMinLenwayis:endl;for(nx=0;nx10;nx++)//输出最短路径{for(ny=0;ny51;ny++){if(Maze[nx][ny]=='#')cout#;elseif(MazeMin[nx][ny]==0)cout;else{cout.;}}coutendl;}11coutThisWayuseddWalkLenstepsendl;//输出最短路径总行走步数return0;}