资源描述：
《迷宫最短路径问题新算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、迷宫最短路径问题新算法摘要:提出了求解迷宫最短路径问题的新算法,该算法抛弃了经典算法(深度优先搜索和广度优先搜索)中繁杂低效的递归、回溯思想。通过合理的变换,将原问题转化为迷宫路径深度图的生成问题。最后对算法进行了严谨的分析和实例测试,显示出该算法易于理解、易于编程、时间空间复杂度低等优点。关键词:最短路径;时间复杂度;深度优先搜索;广度优先搜索NewAlgorithmforSolvingShortestPathofMazeProblemZHANGLin-feng,LVHui,QUJun-feng(TheMissileInstitute,AirForceEngineeri
2、ngUniversity,Sanyuan,Shannxi713800,China)Abstract:Anewalgorithmispresentedforsolvingtheshortestpathofmazeproblem,whichisnotbasedontheinef-ficientrecursivebacktrackingtheoryofclassicalalgorithm(DFS-DepthFirstSearchandBFS-BreadthFirstSearch).Byappropriateconversion,thealgorithmchangestheori
3、ginalproblemintothecreationofthemazegraphproblem.Atlast,anexampleisgiven,whichshowsthatthenewalgorithmiseasytobeunderstoodandprogrammedaswellasitslowtimeandspacecomplexity.Keywords:shortestpath;timecomplexity;DepthFirstSearch;BreadthFirstSearch1问题描述迷宫最短路径(theshortestpathofmaze)问题是一个典型的搜索、
4、遍历问题,其程序设计思想在人工智能设计、机器人设计等事务中均有应用。如图1所示,一个N×M的大方块迷宫,带斜线的单元格表示墙壁(障碍),空白的单元格表示通道。迷宫问题可以表述为:寻找从某一个给定的起始单元格(迷宫入口)出发,经由行相邻或列相邻的通道单元格,最终可以到达目标单元格(迷宫出口),所走过的单元格序列。行进中,只能沿上下左右四个方向前进。而迷宫最短路径问题就是找出从迷宫入口到出口所经过单元格个数最少的路径。2经典算法求解迷宫问题,经典算法有深度优先搜索和广度优先搜索两种深度优先搜索(DFS):从入口出发,顺着某一方向向前探索,若能走通,则继续往前走;否则沿原路退回
5、(回溯),换一个方向再继续探索,直至所有可能的通路都探索到为止。如果恰好某一步探索到出口,则就找到了从入口到出口的路径。为了保证在任何位置上都能沿原路退回,防止死循环,需要使用堆栈来保存大量记录。而要求解迷宫最短路径,则必须用深度优先搜索出所有到达出口的路径,通过比较得到最短距离的路径,这样也必然要求增加数据空间来保存搜索过程中当前最短路径,增加了空间复杂度。广度优先搜索(BFS):从入口出发,离开入口后依次访问与当前位置邻接的单元格(上下左右方向),然后分别从这些相邻单元格出发依次访问它们的邻接格,并使“先被访问的单元格的邻接格‘先于’后被访问的单元格的邻接格”被访问,
6、直至访问到迷宫出口,则找到了迷宫问题的最优解,即迷宫最短路径。该算法的显著特点是“层层推进”,探索点会随着探索的深入急剧增加,相应地,需要大量的空间用来保存探索过程的记录,空间复杂度大。与此同时,上述两种算法都比较抽象复杂,编程实现容易出现问题,调试比较困难,因此在本篇论文中提出了一种新的容易理解和调试的算法,该算法复杂度较低,求解较大规模的迷宫问题也有不俗的表现。3本文算法3.1本文算法基本思想描述首先与其他算法一样,将N×M的图形迷宫表示为一个二维矩阵,用二维数组a[N][M]来存储信息,N和M分别代表迷宫的行数和列数,迷宫中的每个位置都可用矩阵数组的行号和列号来指定
7、。在矩阵中,当且仅当在位置(i,j)处有一个障碍时其值a[i][j]为1,否则其值为0。图2给出了与图1迷宫对应的矩阵描述。其次在本算法中引入了“路径深度”及“路径深度图”的概念。路径深度:从某位置走到出口的最短路径的长度,记为depth(),设每一方块为单位路径长度。假定出口处路径深度为0,障碍处路径深度为-1。路径深度图:与迷宫对应的图,每一个节点值为与该节点对应的迷宫单元格的路径深度,即该单元格与迷宫出口的最短距离。显然路径深度图有且唯一(因为每个单元格与迷宫出口的最短距离有且唯一)。如图1所示的迷宫入口处的路径深度为1
