迷宫课程设计需求介绍.doc

软件需求 功能需求分析 求迷宫中从入口到出口的所有路径是一个经典的程序设计问题。由于计算机解迷宫时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向在继续探索，直至搜有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求迷宫通路的算法中应用“栈”也就是自热而然的事了 软件功能 图1.1 系统功能结构图 1、迷宫的建立： 迷宫中存在通路和障碍，为了方便迷宫的创建，可用0表示通路，用1表示障碍，这样迷宫就可以用0、1矩阵来描述。 2、迷宫的存储： 迷宫是一个矩形区域，可以使用二维数组表示迷宫，这样迷宫的每一个位置都可以用其行列号来唯一指定，但是二维数组不能动态定义其大小，我们可以考虑先定义一个较大的二维数组maze[M+2][N+2],然后用它的前m行n列来存放元素，即可得到一个m×n的二维数组，这样(0,0)表示迷宫入口位置，(m-1,n-1)表示迷宫出口位置。 3、迷宫路径的搜索： 首先从迷宫的入口开始，如果该位置就是迷宫出口，则已经找到了一条路径，搜索工作结束。否则搜索其上、下、左、右位置是否是障碍，若不是障碍，就移动到该位置，然后再从该位置开始搜索通往出口的路径；若是障碍就选择另一个相邻的位置，并从它开始搜索路径。为防止搜索重复出现，则将已搜索过的位置标记为2，同时保留搜索痕迹，在考虑进入下一个位置搜索之前，将当前位置保存在一个队列中，如果所有相邻的非障碍位置均被搜索过，且未找到通往出口的路径，则表明不存在从入口到出口的路径。这实现的是广度优先遍历的算法，如果找到路径，则为最短路径。 需求分析用例 表1-1 “管理员用户登陆”功能需求分析用例 功能点编号 ATQ0101 功能点名称 迷宫问题 角色 任意 功能说明 用户能通过本功能点进出迷宫。 事件流程 用户输入迷宫的行数和列数。 用户按照行数和列数用1和0构造出一个迷宫。 用户输入进点坐标和出点坐标。 按回车键就可得出出入迷宫的路径。 前置条件 无 后置条件 无 输入数据 迷宫的行数和列数以及出入口坐标 输出数据 （i，j，d） 备注 无 求迷宫路径的基本思想 若当前位置可通，则纳入当前路径，并继续朝“下一位置”探索，即切换“下一位置”为“当前位置”，如此重复直至到达出口；若当前位置“不可通”，则应顺着“来向”退回到“前一通道块”，然后朝着除“来向”之外的其他方向继续探索；若该通道块的四周四个方块均“不可通”，则应从“当前路径”上删除该通道块。所谓“下一位置”指的是“当前位置”四周四个方向（东、南、西、北）上相邻的方块。 以0，1输入表示迷宫，0为通路，1为障碍。向电脑输入由0和1组成的二维数组“0”表示通道，“1”表示障碍。然后输出走出迷宫的路径 实现输出迷宫通道，当迷宫无通道时显示“找不到通路”迷宫求解流程图 评审： 某些方块文字描述过多，可以图表化一点点罗列观察起来会更明了。表1-1 “管理员用户登陆”功能需求分析用例，表中好像内容与管理员没有衔接关系，从其他地方拷贝资料借鉴时应注意更改全面。功能点编号跟所做的课程设计标题有关联应该好点，不然是多余的，例如更改为MG113。分析过程中没有考虑多条通路进行折取最短路径，也没说明只有一条通路。但是系统结构功能图比较好，整体思路比较清晰，对迷宫求解这个设计探索的还是比较熟悉。 等级：良好 评分：85分 评审人：张立 评审时间：2013-12-11 迷宫问题 以一个m*n的长方阵表示迷宫 0和1分别表示迷宫中的通路和障碍 通路以三元组（i，j，d）的形式输出 程序结束 求解完毕 迷宫无解 判断个方向是否通路 下 右 左 上 从迷宫入口开始寻路 创建迷宫 定义添加迷宫