用递归回溯解决迷宫问题

《用递归回溯解决迷宫问题》由会员分享，可在线阅读，更多相关《用递归回溯解决迷宫问题（16页珍藏版）》请在装配图网上搜索。

1、扬州大学试题纸（20152016 学年 第 二 学期）ACM 竞赛辅导论文报告学 院：班 级：信息工程学院计科 1302号： 名：指导老师：用递归回溯解决迷宫问题盛晓伟（扬州大学计算机科学与技术系扬州225100）SHENG Xiao-Wei, School of Information Science and Technology, Yangzhou University, Yangzhou 225100, China）For many practical problems, the solution is to move along a series of orderly decision

2、-making points, each of the choices made at each decision point will lead along a path. If the choice is correct, the problem will be resolved. On the other hand, if you go into a dead end or find that the choice at a certain point is wrong, then you must return to the previous decision point and tr

3、y another route. This algorithm is called backtracking algorithm.If the backtracking algorithm is considered as a continuous process of trying to solve the problem, the process seems to be iterative. However, for most of this problem, the recursive method is more easily solved. The recursive princip

4、le point of view is very simple; for a backtracking problem, if and only if at least a word problem solutions can be solved, and these subproblems generated source in the initial of each a possible choice.Key words:backtracking algorithm: Recursive; Iterative； Maze摘 要 ： 对许多实际问题而言，其解决过程就是沿着一系列有序的决 策点

5、前进，在每个决策点所做的每一个选择都会导向沿着某一路径前 行。如果选择是正确的，问题将得到解决。从另一方面讲，如果走进了 死胡同，或者发现在某个决策点的选择是错误的，那么必须返回到以前 的决策点，尝试另一条路径。这中方式的算法称为回溯算法。如果吧回溯算法看成是一个不断地进行各种尝试直至解决问题的过 程，那么这个过程似乎具有迭代性。然而，对大多数这种形式的问题， 采用递归方法更容易解决。采用递归原理的着眼点很简单；对于一个回 溯问题而言，当且仅当至少有一个字问题有了解决方案后才可能得到解 决，而这些子问题的产生又源于最初所做的每一种可能的选择。关键词：回溯；递归；迭代；迷宫迷宫的神话背景1在希腊

6、神话时代，地中海岛屿中的克里特岛被一个叫弥诺斯的暴君所 统治。弥诺斯不时地向雅典索取进贡；年轻男女，用来祭祀弥诺陶洛斯 一个可怕的牛头人身的怪物。为了留住这个可怕地怪物，弥诺斯强 迫他的奴隶底得勒斯(这个天才工匠后来凭借自己打造的一对翅膀逃离 了那个岛屿)在诺塞斯修建了一个巨大的地下迷宫。那些从雅典来的祭 品年轻男女们被带进迷宫，在他们没找到出口之前就被怪物弥诺陶 洛斯给吃掉了。这个阴谋一直在继续，知道雅典年轻的提修斯志愿成为 供品之一为止。提修斯听从弥诺斯的女儿阿里阿德妮的建议，带着一把 剑和一个线团进入了迷宫。在杀死了怪物之后，提修斯凭借着揭开的线 团沿着原路返回。右手规则2.1提修斯的方

7、法反映了一个逃离迷宫的规则，但不是每一个处于此类 困境的人都很幸运地拥有一个线团或者聪明的伙伴给他提出有效的建 议。幸运的是，还有其他逃离迷宫的方法，在这些方法中，最有名的是 右手规则，用以下的伪代码形式来表示：Put your right hand against a wall.While(you have not yet escaped from the maze)Walk forward keeping your right hand on a wall.当前进时，右手触墙的要求会迫使你转弯，有时还要折回。即便如此，右手规则保证可以在任何迷宫中找到一个通向外界的出口。想象以下右手规则的操

8、作，假设提修斯现在已经成功地杀死了弥诺 陶洛斯，并且就站在用提修斯的名字的第一个字母所标注的位置，那是假使提修斯将他的右手放在墙上，并自此开始遵守右手规则前行，他将会走过如下图虚线所示的轨迹：寻找递归方法2.2伪代码形式中的while循环清楚表明，右手规则是一种迭代性策 略，然而，也可以从递归的角度来考虑迷宫问题的解决过程。要这样做， 就要采用一种不同的思维模式，不能再想着找出一条完整的路径来解决 问题。相反地，需要从递归的角度将问题简化。一步一个台阶。一旦简 化成功，就可以用同样的方法来解决每一个后续的子问题。回到在右手规则示例所描述的迷宫结构中，将自己置于提修斯的位 置。这时有三种选择，如

9、下图箭头所示：如果有出口，就肯定分布在其中一条路线上。如果选对了方向，那 么将向解决方案更靠近一步。因此，沿着那条路走，问题就变得简单起 来，这就是递归式解法的关键。这中观点指出了必不可少的递归思维。 只有至少解决啦如图1 所示的新迷宫中的一个，原来的迷宫才有可能得 到解决。每幅图中的 X 号标明了原始出发点，这是任何递归解法的禁区，因为最优解法是不会回到这个点的2.3迷宫的简单情景是什么呢？一种可能性是已经置身于迷宫之外，如 果这样的话，工作就已经完成了。显然，这中情景是一个简单情景。然 而，还有另外一种可能性：跑遍所有可能移动的地方之后进入了一条死 胡同，例如，在开始时向北走，而后沿着那条

10、途径使用递归方法，会试 图解决如下图所示的迷宫：匚这时，已经走遍了所有可前进的空间，新位置的每一条通道都已标 注或是被墙堵住，很显然，这个迷宫在该点是没有解的。因此，这个迷 宫问题就有了第二个简单情景。在这种禁区下，当前区域的四周都被堵 塞，或者是被一堵墙或者是被已走过的标记。如果在考虑前进方向时对那些方格采用递归调用，而不是在前进时 核实每一个已标记过的方格，那么很容易以编码方式实现递归算法。在 程序开始就查看该方格是否已经被标注过，如果是，就可以在该点中止 递归。归根到底，如果发现自己处于一个已标记的位置，那么一定是在 重复以前的路径，这就意味着出路肯定在别的方向上。因此，这个问题的两个简

11、单情景如下：1) 如果当前方格已在迷宫之外，那么该问题已经解决了。2) 2)如果当前方格已被标记，那么该问题不可解。迷宫解决方案算法编码2.4虽然解决这个问题在概念上需要的只是递归思维和简单情景，但是实 际上还要考虑众多的实现细节，才能编写出一个完整的程序。例如，妮 需要觉得迷宫的表述形式，比如标出墙在哪、记录当前位置、显示一个 特定方格是否标记过，并且判断是否已经逃离迷宫。虽然为迷宫设计一 个核实的数据结构就其本身而言是相当有趣的编程挑战，这和理解我们 讨论的焦点递归算法没有什么关系。但是如果做的不好，数据结构 的细节问题将很可能使你纠缠其中进而影响对递归策略的整体理解。 幸运的是，可以通过

12、引进一个新的抽象层来将这些细节撇开。抽象的目 的是为主程序提供信息接口，而这些信息是解决问题所需的，即便细节 问题隐藏于接口之后也无妨。一旦能够访问mazelib.h接口，那么编写程序来解决这个迷宫问题就变得简单多了。这个问题的本质就是写一个使用递归回溯的 solvemaze函数，mazelib模型具备该迷宫问题的特征。Solvemaze的参 数是起始位置，该参数对于每一个递归字问题来说都是不同的。为了确 保递归能够在找到解后停止，Solvemaze函数也必须返回一些指示值， 说明是否成功。传达这些信息最简单的方法就是将Solvemaze函数定义 为谓词函数：当找到时返回TURE，否则返回FA

13、LSE。所以，Solvemaze 的原型如下：Bool Solvemaze (poinT pt);有了上面这个定义，主程序如下Main()Readmazemap(mazefile);If(solvemaze(getstartposition()Printf(“The marked squares show a solution path.n”);ElsePrintf(“No solution exists.n”);Solvemaze调用的所有函数中，唯一没有从mazelib接口导出的函 数是AdjacentPoint(pt,dir),该函数返回在dir方向上离pt位置一步 之遥的方格的坐标。以

14、下是一个简单的AdjacentPoint实现，它辅助初 始点，而后调整合适的坐标值：Point AdjacentPoint(point pt, directiont dir)Point newpt;Newpt=pt;Switch(dir)Case North:newpt.y+;break;Case East:newpt.x+;break;Case South:newpt.y-;break;Case West:newpt.x-;break;Return(newpt);在 for 循环结束时解除当前方格标记的代码在实现中严格说来并不 是必需的，事实上，如果问题中包含有回路的话，还会降低该程序的性

15、能。但是，这样做最根本的好处在于从初始位置到出口的解决的途径被 一条已标记方格所组成的链给串起来了。如果对该算法进行图解分析， 当从某条路径退出时，应该将标记擦掉，以便能更容易看清楚当前的路 径。2.5确信解决方案可以正确运行2.5为了有效地利用递归，在某些点就要想图6-3中SolveMaze这个例 子那样对递归函数有所认识，并且这样跟自己说：“我知道它如何工作， 问题正变得越来越简单，因为每一次有更多的方格被标记，简单情景显 然是正确的。这短程序肯定能解决这个问题。”然而，许多人并不能很 容易地获得对递归算法的信心。与生俱来的怀疑本性促使人们想知道解 决方案的每一步。问题是，即便如前面所示的

16、简单迷宫问题，其解决方 案中所包含的全部步骤也会太多，很不容易理清楚。例如，解决这个迷 宫问题，要求进行66 次调用 SolveMaze 函数，它的嵌套多达27 层。如 果试图追踪代码的细节，毫无疑问，肯定会失败。如果还不能接受递归跳跃的思想，最好在更为通用的意义上跟踪代 码的运行。已经知道，程序初次尝试解决迷宫时想北方挪动一个方格， 因为 for 循环是按照 directionT 枚举所确定的顺序来遍历所有方向的。所以解决方案过程的第一步是在调用一个从以下位置开始的递归程序：这时，同样的过程又发生，程序又一次试图北移，而且在如下位置做出新的递归调用：在递归的这一水平上，不再可能向北移动，所以

17、for循环从其他方向进行循环。在南方简单浏览之后，因为遇到了一个标记过的方格，同样的过程又再次发生了，这就导致了如下状态：XX9X1X在这个位置上，for循环中没有一个方向是有用的，所有的方格不 是被墙堵住就是已经有了标记，因此，如果for循环在这种无路可退的 境地下，它就会解除当前方格的标记，而向后回溯到前一级水平上。结 果是这个位置的所有路径也都尝试过了，因此程序解除该方格的标记并 回到递归程序的更高一级水平上，最终，程序回溯了所有到初始递归调 用的路径，在穷尽了沿北方的所有可能性后，for循环又尝试东方，发 现已被堵塞，又尝试向南的通道，在如下状态开始调用递归程序：从这里开始，同样的过程

18、接着发生。递归程序有规则的遍历了该方 向上的所有通道，大量抵达死胡同的调用后，程序又将返回，在这条路 线上唯一的不用之处在于程序在这条路上的每一步的附加递归调用中 退下来之后，最终在如下位置进行了递归调用：这时，提修斯站在了迷宫的外面。这个简单情景破门而出，并对其调用者返回 TRUE 值，然后这个值通过所有 27 级递归传播回去，对 solveMaze 的最初调用点返回到了主程序。结束语3.涌过迷宫游戏，学习了如何按次序做出选择从而达到某一目标的方 法。该方法的基本策略是编写一个有追踪指令的程序，这样当某一步失 误时，还可以回溯到前面的状态。通过递归，可以不用对回溯过程的具 体细节进行编码，而

19、是开发出对各种问题都可以通用的方法。在回溯问 题中，即便只是相对简单的应用程序，递归调用的细节也往往很难理解， 对于需要很多设计大量回溯步骤的问题，接受对递归跳跃的信任是非常 重要的。附中文参考文献:遇娜.基于迷宫问题的算法新解渭南师范学院学报，2011,(02):66-68.doi:10.3969/j.issn.l009-5128.2011.02.018.崔兆顺.基于遗传规划的迷宫问题高效求解制造业自动化，2011,(01):194-196.doi:10.3969/j.issn.l009-0134.2011.66.m fiRKBLXJ WANFANiGDlLTjl论文相槪性检测报告（详细版报吿NHk ahcDllf- la拥枫论文片段lj&抽也土*送横论上口槪捌inifl卡部悩抵榊规部井的字救.歳晚世文总丫做沖考丈儘桐恒比*匿怜枪丈冷血辛乃丄故棚血曲的宇甑送总论文总7绘1拙陀參咼上松IIIM:匕=总射似比-集艰厳棚仪比1. #1命相世比空览相tl Lt-扎fl片民总和似比