可连通迷宫算法设计及实现.

1、可连通迷宫算法设计及实现摘 要随着科技的日益开展,计算机信息知识越来越被人们所认知和使用。在当今时代,计算机毫无疑问地已成为人们常用的日常工具,尤其在学习和娱乐两方面成为了网络的两大亮点。主要是因为网络提供了一个虚拟的环境，可以给人们提供一个开放性、快速、高效、自由等优点的平台，实现网上、网下育人相结合，促进人们整体素质的提高 。本文通过C语言程序设计和数据结构等相关，经过调试运行，实现设计目标。阐述了系统可连通迷宫的内容和要求，论证了该迷宫的可连通性。采用“穷举求解方法，并结合栈和链表的相关知识，经过编译和运行后，得出了所有的可连通的路径和一条最优路径，并显示出来。本文在教学和娱乐中有较大的

2、价值，而且可连通迷宫程序的实现有利于在以后的开发工程中提供良好的思维方式和参考价值。关键词: C语言，迷宫，栈，链表，穷举求解Algorithm Design and Realization of Connected Maze AbstractAlong with the development of science and technology, computer information have been more cognized and used by people, in the modern age, computer undoubtedly has become commonly

3、 used as daily tools, especially in study and entertainment. Its mainly to supply a fictitious circumstance which is also a good flat with advantages of openness, high speed, effectiveness and etc.It designed a algorithm that can generate a connected maze and then realize it. Besides, it designed a

4、proper data structure to express the maze and reach the goal after compile and run in Microsoft Visual C+6.0 environment . It expatiates the continent and request of connected maze, also prove the connection of maze.Through using exhaustively solving method and list of relevant knowledge, after comp

5、iling and running, it obtained all the way that can be connected with the optimal way with a strength, and displayed.In sum, this article has a great value in teaching and entertainment，and also provide a proper thinking method and reference in the coming developing project in realization of connect

6、ed maze.Keywords: The C language，Maze， Stack，List， Exhaustively solving目录 TOC o 1-3 h z u HYPERLINK l _Toc294016879 1 绪论 PAGEREF _Toc294016879 h 1 HYPERLINK l _Toc294016880 1.1. 课题背景 PAGEREF _Toc294016880 h 1 HYPERLINK l _Toc294016881 1.2. 现状分析 PAGEREF _Toc294016881 h 1 HYPERLINK l _Toc294016882 1.3

7、. 论文整体介绍 PAGEREF _Toc294016882 h 2 HYPERLINK l _Toc294016883 2 系统分析及算法根底 PAGEREF _Toc294016883 h 4 HYPERLINK l _Toc294016884 2.1. 任务分析 PAGEREF _Toc294016884 h 4 HYPERLINK l _Toc294016885 2.2. 广度优先搜索算法 PAGEREF _Toc294016885 h 4 HYPERLINK l _Toc294016886 2.3. 穷举求解算法 PAGEREF _Toc294016886 h 4 HYPERLINK

8、 l _Toc294016887 根底理论 PAGEREF _Toc294016887 h 5 HYPERLINK l _Toc294016888 方案的规模及难度 PAGEREF _Toc294016888 h 6 HYPERLINK l _Toc294016889 主函数执行流程图 PAGEREF _Toc294016889 h 6 HYPERLINK l _Toc294016890 2.7. 模块介绍 PAGEREF _Toc294016890 h 7 HYPERLINK l _Toc294016891 2.7.1. 迷宫创立模块 PAGEREF _Toc294016891 h 8 HY

9、PERLINK l _Toc294016892 路径查找模块 PAGEREF _Toc294016892 h 8 HYPERLINK l _Toc294016893 输出模块 PAGEREF _Toc294016893 h 9 HYPERLINK l _Toc294016894 其他模块 PAGEREF _Toc294016894 h 10 HYPERLINK l _Toc294016895 2.8. 简介及系统配置 PAGEREF _Toc294016895 h 10 HYPERLINK l _Toc294016896 2.8.1 系统配置 PAGEREF _Toc294016896 h 1

10、0 HYPERLINK l _Toc294016897 简介 PAGEREF _Toc294016897 h 10 HYPERLINK l _Toc294016898 3 构建可连通迷宫算法设计及实现 PAGEREF _Toc294016898 h 12 HYPERLINK l _Toc294016899 3.1. 可连通迷宫算法设计 PAGEREF _Toc294016899 h 12 HYPERLINK l _Toc294016900 算法实现 PAGEREF _Toc294016900 h 13 HYPERLINK l _Toc294016901 4 迷宫路径查找算法设计及实现 PAGE

11、REF _Toc294016901 h 16 HYPERLINK l _Toc294016902 4.1. 迷宫路径查找算法设计 PAGEREF _Toc294016902 h 16 HYPERLINK l _Toc294016903 4.2. 算法实现 PAGEREF _Toc294016903 h 18 HYPERLINK l _Toc294016904 5 调试结果及算法分析 PAGEREF _Toc294016904 h 20 HYPERLINK l _Toc294016905 . 调试结果 PAGEREF _Toc294016905 h 20 HYPERLINK l _Toc2940

12、16906 复杂度分析 PAGEREF _Toc294016906 h 22 HYPERLINK l _Toc294016907 5.2.1 时间复杂度分析 PAGEREF _Toc294016907 h 22 HYPERLINK l _Toc294016908 5.2.2 空间复杂度分析 PAGEREF _Toc294016908 h 25 HYPERLINK l _Toc294016909 遇到的问题及解决 PAGEREF _Toc294016909 h 27 HYPERLINK l _Toc294016910 算法的改良思想 PAGEREF _Toc294016910 h 28 HYPE

13、RLINK l _Toc294016911 6 总结与展望 PAGEREF _Toc294016911 h 29 HYPERLINK l _Toc294016912 6.1. 总结 PAGEREF _Toc294016912 h 29 HYPERLINK l _Toc294016913 6.2. 展望 PAGEREF _Toc294016913 h 29 HYPERLINK l _Toc294016914 参考文献 PAGEREF _Toc294016914 h 30 HYPERLINK l _Toc294016915 致谢 PAGEREF _Toc294016915 h 311 绪论1.1.

14、 课题背景人类建造迷宫已经有5000多年的历史了。在世界的不同文化开展时期，这些奇特的图形始终吸引着人们的眼球，沿着弯弯曲曲、困难重重的小路却要很吃力地行走，寻找出可通路径或者无通路时沿着原路返回。有时侯迷宫也比喻复杂艰深的问题或难以捉摸的局面。比方：门户道路复杂难辨，人进去不容易出来的建筑物； 比喻不易探索的领域，例如：探索科学的迷宫。迷宫问题其实是取自心理学的一个古典实验，关于迷宫的故事最早出现是在古希腊神话中。据说,半人半神的英雄西修斯在克里特的迷宫中勇敢地杀死半人半牛的怪物,并循着绳索逃出迷宫。希腊史学家希罗多德曾探访过那里，他描述说:整个迷宫由12座带顶院落所构成,所有院落都由通道连

15、接,形成3000个独立的“室。后来的参观者也说,一旦进入迷宫,如果没有向导指引,根本没有任何可能走出这个迷宫。历史上,大局部人们都认为迷宫具有很大的魔力。后来随着人们新颖的思想,迷宫逐渐地成为了一种好玩的游戏，并随之进入人们的生活中。在如今计算机非常普及的情况下,迷宫又主要以游戏的形式呈现在我们日常生活中，供人们娱乐消遣，且千变万化。在经常接触到的游戏中，我们也会碰到随机生成的地图，即使在制作简单迷宫游戏的时候，也需要面对迷宫地图的制作问题。另外它还主要以程序的形式供学生学习和研究程序算法。其中本文可连通的迷宫的出现对今后的程序设计工作垫定了坚实的根底。1.2. 现状分析进入21世纪以来，伴随

16、着计算机信息技术的应用与迅速普及，那么人们对利用计算机程序设计迷宫的技术要求越来越高。借助计算机构建迷宫主要有手动输入和自动生成两种方法。其中手动输入的迷宫是否存在路径，取决于输入的情况，不具有随机性，而且比拟浪费时间。但是利用计算机自动生成的迷宫具有随机性、复杂性、可趣性以及提高系统效率等特点。迷宫路径查找有很多种方法，例如常用的方法有：右手左手法那么、穷举求解法、回溯法等。其中右手左手法那么的思想既在寻找路径的过程中，遇到转弯的地方都选右左方向继续下去，直至走出迷宫，显然此法那么具有效率低的特点，甚至永远查找不出最优路径的特点。穷举求解法，或称为 HYPERLINK :/baike.bai

17、du /view/1850655.htm t _blank 暴力破解法是基于计算机特点而进行解题的思维方法，其特点是算法比拟简单，但运行时所花费的时间量较大。回溯法是一种选优搜索法，它适合用于求解一些组合数较大的问题，具有效率高等优点。基于以上方法的各自优点，现在求解迷宫路径的经典算法主要有深度优先搜索和广度优先搜索。该算法主要将原问题转化为迷宫路径深度图的问题，通过比拟路径深度从入口走到出口的路径长度的大小，得出可连通迷宫的最优路径，具有易于理解、易于编程、时间和空间复杂度低等优点。1.3. 论文整体介绍本文主要讲述了可连通迷宫算法设计及实现，根据C语言和数据结构等知识，通过Microso以

18、下简称VC+ 6.0环境运行，最终给予最优路径方案、计时等主要结果。本文通过四章来介绍本系统的完成过程。第一章 绪论。本章主要讲述了可连通迷宫算法设计及实现相关的课题背景和现状分析。第二章 系统分析及算法根底。本章主要介绍了本次毕业设计的相关任务分析、算法根底、各个模块的功能以及系统配置和运行环境作了详细的介绍。第三章 构建可连通迷宫算法设计及实现。本章主要对本次课程设计的迷宫的可连通流程图、主要函数流程图以及各功能模块等功能进行了详细地描述。第四章 迷宫路径查找算法设计及实现。本章主要给予的可连通迷宫路径查找算法设计思想和核心程序，并给予了效果图证实算法的正确性。第五章 调试结果及算法分析。

19、本章主要给予了此次毕业设计运行的效果图和对算法的时间和空间复杂度分析，以及遇到的问题和解决方案。第五章 总结与展望。总结了本次和毕业设计所获得的经验、缺乏以及展望。2 系统分析及算法根底2.1. 任务分析本次毕业设计是根据算法设计原理和结合恰当的数据结构知识，设计一个可以随机生成可连通迷宫的算法，并实现该算法，可以在环境中运行并显示该迷宫。其主要的任务有三点：首先是如何实现迷宫的可连通性；其次是可连通迷宫的路径如何查找；最后是对算法的详细分析。2.2. 广度优先搜索算法广度优先搜索Breadth_First Search，以下简称BFS是最简便的图的搜索算法之一，其遍历类似于树的按层次遍历的过

20、程，既从根节点开始，沿着图遍历树的各个节点，如果发现目标，那么演算终止。一般的实验里，其邻居节点尚未被检验过的节点会被放置在一个被称为 open 的容器中例如队列或是链表，而被检验过的节点那么被放置在被称为 closed 的容器中。既常采用的open-closed表。在遍历的过程中需要一个访问的标志组，且这一算法也是很多重要的图的算法的原型。它属于一种盲目搜寻法，并不考虑节点的可能位址，主要目的是系统地展开并彻底地搜索检查图中的所有节点，直到找到结果为止。BFS遍历图的时间复杂度为On+e。从BFS算法的观点看，所有因为展开节点而得到的孩子节点都会被加进一个先进先出的队列中。本次毕业设计运用B

21、FS算法主要表达在可连通迷宫的初始化中，利用stl容器把扩展得到的点存放在queue队列中。2.3. 穷举求解算法穷举求解法又称列举法、枚举法，是蛮力策略的具体表现，是一种简单而直接地解决问题的方法。其根本思想是逐一列举问题所涉及的所有情形，并根据问题提出的条件检验哪些是问题的解，哪些应予排除。由于现代计算机的运算速度非常快，加之本次毕业设计的可连通迷宫规模不是很大，所以运用穷举求解的方法对迷宫内部的节点逐一判断，并可以快速地求解得到所有的路径，其中穷举求解的应用领域也是非常广阔的。穷举法求解的算法设计比拟简单，解的数目有限，但应用穷举求解方法时应注意对问题所涉及的有限种情形必须一一列举，不能

22、重复，又不能遗漏。重复列举直接引发曾解，影响解的准确性。穷举求解应用循环结构来实现，在循环体中，根据所求解的具体条件，应用选择结构实施判断筛选，求得所要求的解。2.4根底理论本次毕业设计主要运用了C语言和数据结构等知识。下面主要对两者进行详细的介绍：C语言是国际上广泛流行的计算机高级语言，同时它适合作为系统描述语言，既可以用来编写系统软件，也可用来编写应用软件。它具有语言简洁、紧凑，使用方便、灵活；运算符丰富；数据类型丰富，具有现代语言的各种数据结构；具有结构化的控制语句；语法限制不太严格，程序设计自由度大；允许直接访问物理地址，能进行位bit操作，能实现汇编语言的大局部功能，可以直接对硬件进

23、行操作；生成目标代码质量高，程序执行效率高；可移植性好等优点。正是C语言具有这些优点，所以国际上才广泛采用，可以说它是其他高级语言的根底，高级语言都是基于C语言的根底上展开的。数据结构是一门理论性很强、思维抽象、难度较大的课程，也是根底课和专业课之间的桥梁。本文主要运用了数据结构中的三大知识点：其一是广度优先搜索算法；其二是双向链表；其三是栈。三者与C语言知识相结合，设计合格的算法，可以到达本次的可连通的迷宫设计的要求。其中广度优先搜索算法是实现迷宫的可连通性；栈主要是用来存储求解路径节点的压栈和出栈操作，最终显示路径；双向链表主要是在求解迷宫路径的时候，结合数学坐标知识的思想对当前位置作判断

24、后，得到脚步移动的方向，并通过程序输出可连通的路径。因此本次在求解可连通迷宫的路径时，主要是基于三者的优点而进行展开的。2.5方案的规模及难度本次毕业设计的迷宫构造主要是采用C语言中常用的随机函数来实现的，即rand和srand函数。开始迷宫内部全部都为阻隔墙，然后运用数组函数来随机的产生空格，既通路，其中我们可以在程序中改变参数i和j的值，来求的不同的余数，使得内部有不同的空格，使得迷宫内部的复杂难度各不相同，既寻找路径的难度和时间也不尽相同。由于运行界面以及方块占32位的限制，导致了本实验的迷宫矩阵行坐标的值不能超过33，如果超过了33以上，就导致了图案折叠现象的产生，如果不考虑重叠问题，

25、本实验矩阵的坐标值可以到达171左右当然具体的要以程序里面的参数为准。在程序里面主要设置了四种难度等级方案，主要是随机取消内部的墙壁，改变路径的条数，使得难度有所改变。因此本实验可以在不同的矩阵下实现不同规模的迷宫产生并且给予路径的显示。主函数执行流程图程序启动时，开始执行主函数main()输出显示界面菜单。用户根据显示的界面提示输入enter键，计算机开始完全随机产生可连通的迷宫，然后执行后面的功能。其中主函数执行流程如图2-1所示。界面显示选择难度等级初始化计时开始寻找路径完成相关功能开始结束初始化计时结束路径查找计时结束路径查找计时开始初始化迷宫图2-1主函数执行流程图2.7. 模块介绍

26、任何一个完整的程序都是由许多的模块拼接起来的，通过主函数main来调用各模块函数来实现相应的功能。本函数也是如此，将实现可连通迷宫的生成和路径的查找等主要功能，并且图形化输出其中所有的路径和最短的路径等根本要求。本实验路径脚步的存放是通过栈来实现，迷宫使用二维数组来存放。计算机通过“穷举求解方法求出迷宫的所有路径，并通过比拟求出最优路径，并输出显示。其中本实验功能模块图如图2-2所示：迷宫路径查找程序创立模块路径查找模块输出模块迷宫的定义路径查的找求得最优解图形化输出路径的输出迷宫的复原数组的改写脚步后退脚步前进可通性检查其他模块图2-2功能模块图其中各个模块图的具体说明如下：2.7.1. 迷

27、宫创立模块可连通迷宫的构造主要是通过此模块来创立的。在计算机求解可连通的迷宫之前，计算时机调用InitMaze ()函数自动创立一个大小为M*N的迷宫。其中迷宫的定义通过修改二维数组给予实现，并运用随机函数rand()创立迷宫内部的墙壁多少，并结合迷宫初始化条件，使得计算机最终创立一个系统完全随机的可连通迷宫。2.7.2路径查找模块路径查找模块是本实验的核心函数模块，主要查找出所有可通路径。求解思路主要是依次判断东北南西四个方向，假设某一方向可以通过那么进行前进操作，不可通过那么转向下一个方向，四个方向都不可通过时那么进行后退操作。它的核心分为两个局部：路径查找和求解最优解。其中路径查找又包括

28、可通性检查、脚步前进以及脚步后退三个模块。1. 可通性检查可通性检查用来判断指定当前脚步的相邻四个方向是否有通路。那么需要判断两方面内容：一方面，下一点是否有障碍；另一方面，下一点是否已经压入栈中。如果当前脚步同时满足无障碍和无压入栈这两个条件，那么就可以通过，否那么不能通过并给予记录和保存。2. 脚步前进如果检查当前脚步可以在有通路的情况下抵达下一个通道块，那么就完成前进操作。其中“前进的实现主要有两方面内容：一方面，将新节点压入栈中；另一方面，在迷宫数组中将本脚步的坐标标记为“已走 ，以便防止寻找路径时再次检查，提高系统效率。3. 脚步后退脚步后退是在当前脚步四个方向都无通路的情况下，那么

29、回退一步，并转向上一通道块的其他方向，同时删除栈中的栈顶元素，并将迷宫数组中已删除节点指向的元素重新标记为“未走，以便进行其他路径的寻找路径操作时可以重新判断。如果回退一步其他方向还没有通路时，再回退一步，直到回到的通道块其他相邻方向有通路时为止，再寻找通路，如此继续下去，直至寻找出所有的可通路径停止。4. 更优解查找当求出的所有的路径时，本模块完成更优解的查找。找出最短路径和所对应的方案号，并将最短路径通道块的各元素存储在栈中，并输出和显示。 2.7.3输出模块输出模块主要功能是输出系统完全随机到的迷宫和它的图形化路径，并把路径查找模块查找出所有的可通路径，都对每一条路径的坐标、方向、脚步数

30、以及计算机查找所有路径的时间给予输出显示。其中显示还有主界面的显示等。2.7.4其他模块复原迷宫模块是依靠调用Renew ()函数，用于迷宫求解后的处理，主要有初始化存储迷宫的二维数组、各变量值。迷宫改写模块，当第一条路径找到并记录之后，删除上次求解路径时栈中的所有元素，既释放内存空间，继续求解其他的路径并保存路径的节点，以满足要求并最终输出结果。 系统配置计算机主要配置如下：操作系统：Microsoft Windows XP Professional (5.1,版本 2600)处理器： HYPERLINK :/product.pconline /so/s34827/ t _b

31、lank Intel Pentium Dual-Core T3200(2.0GHz)处理器主频：2000MHzCPU内部缓存： HYPERLINK :/product.pconline /so/s27103/ t _blank L2 1M内存容量：1GB硬盘容量：160G显卡：独立，256MB2.8.2VC+ 6.0是 HYPERLINK :/baike.baidu /view/2353.htm t _blank 微软公司推出的一款C+编译器，将“高级语言翻译成“机器语言低级语言的程序。 HYPERLINK :/baike.baidu /view/100377.htm t _blank Vis

32、ual C+是一个功能强大的可视化 HYPERLINK :/baike.baidu /view/973702.htm t _blank 软件开发工具。自1993年微软公司推出Visual C+1.0后，随着其新版本的不断问世，Visual C+已成为专业程序员进行软件开发的首选工具。虽然微软公司推出了Visual C+.NET(Visual C+7.0)，但它的应用的很大的局限性，只适用于Windows 2000,Windows XP和Windows NT4.0。所以在实际中，人们更多的是以为平台。不仅是一个C+编译器，而且是一个基于Windows操作系统的可视化集成开发环境IDE。由许多组件

33、组成，包括编辑器、调试器以及持续向导AppWizard、类向导Class Wizard等开发工具。这些组件通过一个名为Developer Studio的组件集成为和谐的开发环境。由于C+是由C语言开展起来的，也支持C语言的编译。版本是使用最多的版本，很经典。所以本次毕业设计就是利用它的这一优点在如上系统配置下作为运行环境的。3 构建可连通迷宫算法设计及实现3.1. 可连通迷宫算法设计在计算机随机迷宫的入口和出口之后，主要利用广度优先搜索算法，从起点向终点进行搜索，直到找到终点为止，在搜索迷宫路径的过程中，利用queue队列存放扩展得到的点并记录该路径，同时在搜索完毕之后标记为可通路径，其中入口

34、相邻右方向的通道块强制设置为通路。程序开始时，先将入口相邻右方向通道块的节点放入队列中，开始进入循环，当队列为空时那么结束。其中在循环过程中，每次弹出对列的首元素，随机将当前节点的周围四个节点放入队列中，进入循环，只有当队列首元素既为队尾元素时那么结束。当然当前节点在放入队列中的时候要进行相关的条件判断，其一：被放入的当前节点是否超出了地图的边界；其二：被放入的当前节点是否已经被访问过，只有同时满足二者条件是才允许放入队列中。其中数组father记录某点的父亲节点的坐标，这样就可以在完成“保证有一条通路的情况下，把该条通路找出来，然后再进行标记。其迷宫的可连通流程图如图3-1所示。开始起点入队

35、列队列是否为空结束Temp=队列首元素N=0随机选取Temp四周的一个点放入队列N=4？YTemp=end？YNNYN+N 图3-1 可连通流程图算法实现其构建迷宫可连通的主要程序如下。void CreateWell( char MazeMN, PosType start, PosType end, int degree ) int i, j;Mazestart.rstart.c=s;/设置入口Mazeend.rend.c=e;/设置出口start.c +;end.c -;queue Q;Q.push( start );Mazestart.rstart.c = ;bool flag4;PosT

36、ype temp, temp1, fatherMN;bool mapMN;memset( map, true, sizeof(map) );while ( !Q.empty() ) temp = Q.front();Q.pop();if ( temp.c = end.c & temp.r = end.r ) break;int t = 0;memset( flag, true, sizeof(flag) );while ( t != 4 ) i = rand() % 4;if ( !flagi ) continue;t+;flagi = false;temp1 = temp;temp1.r +

37、= diri0;temp1.c += diri1;if ( temp1.r = M-1 | temp1.c = N-1 ) continue;if ( maptemp1.rtemp1.c = false ) continue;maptemp1.rtemp1.c = false;Q.push( temp1 );fathertemp1.rtemp1.c.c = temp.c;fathertemp1.rtemp1.c.r = temp.r;int x, y;/打通通路while ( temp.c != start.c | temp.r != start.r ) Mazetemp.rtemp.c =

38、;x = temp.r;y = temp.c;temp.r = fatherxy.r;temp.c = fatherxy.c;其迷宫可连通效果图如图3-2所示。图3-2 可连通效果图4 迷宫路径查找算法设计及实现4.1. 迷宫路径查找算法设计在系统随机出可连通的迷宫之后，主要对该迷宫进行路径的查找。经过反复研究和分析，一个求解路径简单的方法是：在系统随机产生可连通的迷宫以及随机入口和出口之后，便从随机入口出发，沿着某一方向东、南、西、北向前探索，假设沿着某一方向能够走通，那么继续往前走；否那么沿原路退回，换另一个方向再继续探索，直至所有可能的通路都探索到为止，既所谓常用的“穷举求解法。为了保证

39、在任何位置上都能沿原路退回，显然需要用到一个“后进先出的栈结构来存储从随机入口到当前位置的路径。假设“当前位置指的是“在搜索过程中的某一时刻所在迷宫图中某个方块的位置，那么求迷宫中一条路径的算法的根本思想是：假设当前位置“可通，那么纳入“当前路径，并继续朝“下一位置探索，即切换“下一位置为“当前位置，如此重复直至到达随机出口，并把路径记录下来；假设当前位置“不可通，那么应顺着“来向退回到“前一通道块，然后朝着除“来向之外的其他方向继续向前探索，假设该通道块的四周4个方块均“不可通，那么应从“当前路径上删除该通道块，并留下不可走通的标记，使得防止后面重复搜索，提高算法的效率。所谓“下一位置指的是

40、当前位置相邻的4个方向东、南、西、北上相邻的方块。假设以栈“S记录“当前路径，那么栈顶中存放的是“当前路径上最后一个通道块。由此，“纳入路径的操作即为当前位置“入栈 ；“路径上删除前一通道块的操作即为“出栈。直到计算机求出所有的通路路径，最后在所有可以路径的根底上进行比拟，得出一条或者多条最优路径，且所有的路径都给予路径坐标、方向和脚步数显示。其计算机求解可连通迷宫的路径时，其迷宫路径的查找流程图如图4-1所示：随机入口东标记已走是否是出口移动一步下步是否可行改变方向东西南北是否遍历回退一步改变方向路径查找成功NYNNYY栈顶元素出栈当前节点入栈图4-1 路径查找流程图4.2. 算法实现其可连

41、通迷宫路径查找算法设计如下。PosType NextPos(PosType test, int di)/求下一个探索的目标,方向先后PosType ReturnPos; switch (di)case 1:/向东寻ReturnPos.r=test.r;ReturnPos.c=test.c+1;break;case 2:/向北寻ReturnPos.r=test.r-1;ReturnPos.c=test.c;break;case 3:/向南寻ReturnPos.r=test.r+1;ReturnPos.c=test.c;break;case 4:/向西寻ReturnPos.r=test.r;Ret

42、urnPos.c=test.c-1;break;ReturnPos.di=1;ReturnPos.ord=0;return ReturnPos;其可连通迷宫成功查找出路径的效果图如图4-2所示。图4-2 成功出查找路径效果图5 调试结果及算法分析5.1. 调试结果界面显示图如图4-1所示。图5-1界面显示图迷宫规模相同但是难度等级不同的效果图如图4-2至4-5所示。 图5-2 难度等级为1 图5-3 难度等级为2 图5-4 难度等级为3 图5-5 难度等级为4迷宫难度相同但是规模不同的效果图如下图。 图5-6 规模为15 图5-7 规模为20 图5-8 规模为25 图5-9 规模为305.2复

43、杂度分析程序的复杂度分析主要包括时间复杂度分析和空间复杂度分析。5 时间复杂度分析1初始化迷宫所需时间如表4-1所示。表5-1 初始化迷宫所需时间M=N9102040608096难度等级为1时间1ms001500015时间2ms000001616时间3ms000016016时间4ms00000016时间5ms000001516难度等级为2时间1ms00000016时间2ms000001615时间3ms000001516时间4ms0001501615时间5ms000001616难度等级为3时间1ms0000151615时间2ms000001616时间3ms000001615时间4ms000015

44、1615时间5ms0000151516难度等级为4时间1ms000001516时间2ms0000000时间3ms0001501216时间4ms0000151615时间5ms0000151516注：由于计算机运行界面的原因，导致界面只能在M=N=96时显示初始化迷宫的时间，所以在此初始化时间列举到96停止。经以上表格数据可知：1：系统在同难度等级、但不同M、N的情况下，系统初始化迷宫的平均时间分别约为4.0ms、4.4ms、5.7ms、4.7ms。2：系统在M、N值相同、但不同难度等级的情况下，系统初始化迷宫的平均时间分别约为，那么经以上的数据分析可知：系统初始化任何一个可连通迷宫的时间约为：4

45、.0+4.4+5.7+4.7+0.8+1.5+4.55+10.75+14.9/11=4.7ms。在允许实验误差的范围内：从数据方面可以看出，在同难度等级的情况下，系统初始化迷宫的平均时间随着M和N值的增大而成递增线性关系；在M和N值相同的情况下，系统初始化迷宫的平均时间随着难度等级的提高也成递增线性关系。2查找出所有路径时间如表5-2所示： 表5-2 查找出所有路径的时间M=N91020406080100140171难度等级为1时间1ms062140235970342662626598901562227时间2ms0152509067561535363312452598986时间3ms01517

46、221940624856383125689278652时间4ms016944937237522824435956382153621时间5ms09447218406183124203147773189283难度等级为2时间1ms12161724067184203695378528803时间2ms31321103904656231325141889010928时间3ms3131463913241391314031485462时间4ms16152664692501391190633133607时间5ms15161721906796407703265006671难度等级为3时间1ms161662188

47、25075098433753547时间2ms16154717243864118288914984时间3ms16151561562811359111033449860时间4ms1516147375813656190665473891时间5ms0161405624226569229221328难度等级为4时间1ms031471571531390563954259时间2ms151562219469422109410162609时间3ms16166223448412978909375016时间4ms16164734428165618599681360时间5ms153294281453657515953

48、5047注：由于难度等级和M、N大小的关系，尤其当M、N很大和难度等级比拟低时，系统搜索路径的时间比拟长，考虑到时间的关系，加之计算机配置不是很高的原因，所以这样的情况在本次测试的过程中考虑的比拟少，但是不影响结果的分析。经以上表格数据可知：1：系统在同难度等级、但不同M、N的情况下，系统查找出所有路径的平均时间分别约为71436ms、2886ms、1197ms、720ms。2：系统在M、N值相同、但不同难度等级的情况下，系统查找出所有路径的平均时间分别约为12ms、25ms、117ms、638ms、1291ms、9904ms、40506ms、11253ms、107807ms。那么经以上的数据

49、分析可知：在允许实验误差的范围内，从数据方面可以看出，在同M、N值相同的情况下，系统查找出所有迷宫路径的平均时间随着难度等级的增大而成递增线性关系，主要是因为在难度等级为1的时候，系统查找出所有路径花费的时间较多引起的；但在难度等级相同的情况下，系统查找出迷宫所有路径的平均时间随着M、N值的提高也成递减线性关系。因此，我们从数据分析的情况下可以得到：系统初始化迷宫和系统查找出所有路径所需的时间均和M、N值以及难度等级都有关系，各自呈现出线性关系，符合理论。5 空间复杂度分析可连通迷宫求解路径的空间复杂度问题比拟复杂。求解的时间与系统完全随机到的可连通迷宫、迷宫的大小m*n、迷宫的形状、第一次成

50、功求解时产生的栈的长度等均有关系。下面就举出以下两种极端的情况，作一说明：1：当迷宫大小为m*n且路径如图5-10所示时，既当系统随机到的迷宫的入口和出口在一条水平直线，并且在此水平直线上面没有任何的障碍物时，可以通过判断得知此路径是最优路径。此时计算机进行了m-2个迷宫节点的遍历，存储m-2个节点，其空间复杂度为T(m-2)。图5-10 迷宫大小m*n2：当迷宫大小为m*n且路径如图5-11所示时，既当随机到的迷宫的入口和出口在对角线两端，可以通过判断得知此路径是最长路径。此时计算机进行了m-2*n-2个迷宫节点的遍历，此时系统存储了m-2*n-2个节点，其空间复杂度为T(m-2*n-2)。

51、图5-11 迷宫大小m*n因此可以得到：系统存储可连通迷宫路径的空间复杂度为TT(m-2), T(m-2*n-2)。5.3遇到的问题及解决在编写和调试程序的过程中，遇到了以下一些问题：1：在编写程序时，最初并没有考虑求最短路径的问题，导致在后来编写求最短路径的代码中，出现了崩溃问题，而且还有较多的错误。通过给程序“缝补缀补，效果并不是很明显，依旧有错误，还导致代码冗余混乱。最后审视了思路上的问题，明确思路和流程图后，重新编写程序，并采用了单步调试的方法，才得以解决。2：在最初的脚步可通性检查中，仅仅运用函数判断了下一个点是否有障碍，没有考虑到下一个点是否早已入栈，结果导致经典的迷宫死循环。通过

52、画图和计算，参阅相关经典错误的资料，最终明确了导致此问题产生的原因并对判断条件进行了更正，消除了错误，提高了程序的稳定性。计算机在求解过程时，如果判断条件不严密那么会造成死循环现象的产生。3：在求解第一次迷宫路径之后，当进行第二次迷宫路径求解时，构造的迷宫在输出时会出现“乱码的现象。主要是因为在上次求解完毕之后，没有迷宫数组进行复原操作。类似的，考虑到其他变量也可能出现此问题，上次求解的迷宫节点压入栈后并没有释放空间，导致了内存泄露的问题，于是在求解下面的路径时，首先要对栈进行清空的操作，既删除栈Sfirst到Slast间存储的迷宫路径，然后对路径上的节点进行压栈和出栈的操作，直到找到可通的路

53、径节点。4：在路径求解的过程中，开始求出的显示路径是断断续续的符号拼接起来的，并不是一条连续的折线段，最后通过数学知识解决了这个问题。既通过两点的坐标来判断线条的形状， “两点确定一条直线，“三点确定一个折线，其中两点坐标并不能完全判断出形状。于是完善了折线形状的判断方法，使用三个点进行判断，使迷宫路径的问题才得以解决。5：在初始化可连通迷宫的过程中，发现计算机消耗的时间太久，导致效率降低的问题。于是对初始化迷宫条件做了进一步的改良，既运用广度优先搜索的思想才得以解决这一问题，提高了系统的运行效率。5.4算法的改良思想虽然本次毕业设计长达3个月之久，但是并没有到达很好的结果，存在一定的缺乏。从利用计算机求解可连通迷宫路径的方法来看，依旧采用的是穷举求解的方法，当运用此方法对可连通迷宫求解的路径如图5-11所示时，表现出了极大的劣势。如果计算机在查找可连通迷宫路径的过程中，能引入数据结构中图的拓扑化思想，就更完美了。具体想法如下:虽然在可连通迷宫路径查找的过程中，能够通过判断当前节点的p-pre、p、p-next三个点的坐标值，得出当前节点路径的形状。如果将存储结构改为链栈结构，通过p、p-next、