迷宫最短路径问题的计算机解法

《迷宫最短路径问题的计算机解法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、迷宫最短路径问题的计算机解法的信息目录1.问题描述12.数据的输入与输出22.1.输入迷宫问题的大小规模22.2.建立数值迷宫图形22.3.走向(DirectiorO控制22.4.数据输出23.数据结构23.1.数组(Arroy)33.2.栈(Stock)33.3.队歹34.算法基本思想34.1.基本算法思想34.1.1.步骤一:34.1.2.步骤二：34.1.3.步骤三34.2.具体实施44.2.1.其一：44.2.2.其二：45.算法细化参考46.算法分析56.1.吋间复杂性56.1.1.其一：56.1.2.其二：56.2.空间复杂性56.2.1.其一：56.2.2.其二

2、：6扳手1-11拉车1-21钢材1-32迷宫最短路径问题的计算机解法的信息迷宫最短路径(theShortestPathofLabyrinth)问题是一个典型的搜索、遍历问题其程序设计思想在许多计算机运算程序、计算机管理程序中均有应用。一般來说用计算机解决一个具体问题时.大致需要经过下列几个步骤:首先要从具体问题抽象出一个适当的数学模型•然后设计一个解此数学模型的算法•最后编出程序•进行调试、调整•直至得到最终解答。其中•寻求数学模型的实质是分析问题从屮提取操作的对象并找出这些操作对彖Z间的关系然后用数学语言加以描述。但是，迷宫最短路径问题处理的对象不仅仅是纯粹的数值，而且还包

3、括字符、表格、图象等多种具冇一定结构的数据，这些非数值计算问题无法用数学方程加以描述，这就给程序设计带来一些新的问题。迷宫最短路径(theShortestPathofLabyrinth)问题是一个典型的搜索、遍历问题•其程序设计思想在许多计算机运算程序、计算机管理程序中均有应用。一般来说•用计算机解决一个具体问题时•大致需要经过下列儿个步骤:首先要从具体问题抽象出一个适当的数学模型然后设计一个解此数学模型的算法最后编出程序谜行调试、调整直至得到最终解答。其中，寻求数学模型的实质是分析问题，从中提取操作的对彖,并找出这些操作对象Z间的关系.然后用数学语言加以描述。但是•迷宫最短

4、路径问题处理的对象不仅仅是纯粹的数值•而且还包括字符、表格、图彖等多种具有一泄结构的数据•这些非数值讣算问题无法用数学方程加以描述.这就给程序设计带来一些新的问题。1•问题描述迷宫最短路径问题即从一个迷宫的入口(Sourse)到lB□(Destination)找出一条最短路径。求迷宫屮从入口到出口的路径并找出其屮最短者的计算机解法应当用“穷举求解”的方法即从入口出发，顺某一方向向前探索若能走通，则继续往前走否则沿原路退回(回溯),换一个方向再继续探索，直至所有对能的通路都探索到并确定出最短路径为止o为了保证在任何位置上都能沿原路退冋•确保正确记录各个路径的长度•在求迷宫最短路

5、径问题屮应用诸如顺序表数组、栈、队列等数据结构•也就是自然而然的事了。扳手1-1拉车1-2钢材1-32.数据的输入与输出迷宫最短路径问题的数据输入主要包括程序规模、数字化迷宫形成、行进方向设定等。其数据输出包括迷宫图形和运行结果。2.1.输入迷宫问题的大小规模釆用m行门列数值矩阵描述迷宫。控制问题规模的系数m、n都应该是正整数.反映迷宫的长宽尺度。(路墙比)也是一个正整数用来调整迷宫中0与1的个数比例。该数越人迷宫中0的个数越多，宫墙相对越少谜宫越容易通过。22建立数值迷宫图形可用一个二维数组moze[m4-1][n4-1]模拟该数值迷宫•由随机函数产生随机数(RandomV

6、alue)0或1。数组元素为0表示该位置允许通过•数组元素为1表示该位置已被封锁，用以表示通路或宫墙。和moze[m][口]分别为迷宫的入口和出口。这样便得到了以矩阵形式排列的迷宫数值模型。2.3.走向(Direction)控制用二维数组dire[8][2]存放八个方向上的位移量。2.4.数据输岀运行该程序首先输出模拟迷宫的二维数组，若其中存在最短路径•则由出口冋溯到入口•再打印这一条路径•如下所示(m.n).(i,j).….(1.1喏无通路•则打印："Thereisnopath!”3.数据结构本问题将用到多种类型的数据结构(DasStructure)•其优点在于实现了信息的

7、隐蔽.即将一切用户不必了解的细节都封装在某种结构类型中。3.1.数组(Array)数组是一种应用广泛的数据结构•其元素之间的关系由下标体现，用二维数组模拟迷宫形彖贴切。为了程序中判断方便把迷宫扩展成为maze[m+2][门+2].扩展部分的元素(迷宫外围)设置为1•相当于在迷宫周围布上一圈不准通过的墙。这样•在迷宫的任何一个位置(i・j)上都有八个可供考虑的移动方向。2.1.栈(Stack)栈是回溯(Bocktracking)通道时常用的一种数据结构.为了标志已经通过的位置•采用一个状态顺序ttstat