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