迷宫最短路径问题新算法

迷宫最短路径问题新算法摘要：提出了求解迷宫最短路径问题的新算法该算法抛弃了经典算法（深度优先搜索和广度优先搜索中繁杂低效的递归、回溯思想。通过合理的变换，将原问题转化为迷宫路径深度图的生成问题。最后对算法进行了严谨的分析和实例测试，显示出该算法易于理解、易于编程、时间空间复杂度低等优点。关键词：最短路径；时间复杂度；深度优先搜索；广度优先搜索NewAlgorithmforSolvingShortestPathofMazeProblemZHANGLin-feng,LVHui,QUJun-feng(TheMissileInstitute,AirForceEngineeringUniversity,Sanyuan,Shannxi713800,China)Abstract:Anewalgorithmispresentedforsolvingtheshortestpathofmazeproblem,whichisnotbasedontheinefficientrecursivebacktrackingtheoryofclassicalalgorithm(DFS-DepthFirstSearchandBFS-BreadthFirstSearch).Byappropriateconversion,thealgorithmchangestheoriginalproblemintothecreationofthemazegraphproblem.Atlast,anexampleisgiven,whichshowsthatthenewalgorithmiseasytobeunderstoodandprogrammedaswellasitslowtimeandspacecomplexity.Keywords:shortestpath;timecomplexity;DepthFirstSearch;BreadthFirstSearch1问题描述迷宫最短路径(theshortestpathofmaze)问题是一个典型的搜索、遍历问题其程序设计思想在人工智能设计、机器人设计等事务中均有应用。如图1所示，一个NXM的大方块迷宫，带斜线的单元格表示墙壁（障碍），空白的单元格表示通道。迷宫问题可以表述为寻找从某一个给定的起始单元格（迷宫入口）出发，经由行相邻或列相邻的通道单元格最终可以到达目标单元格（迷宫出口）,所走过的单元格序列。行进中只能沿上下左右四个方向刖进。而迷宫最短路径问题就是找出从迷宫入口到出口所经过单元格个数最少的路径。2经典算法求解迷宫问题，经典算法有深度优先搜索和广度优先搜索两种深度优先搜索（DFS）:从入口出发，顺着某一方向向前探索，若能走通则继续彳主前走；否则沿原路退回（回溯）,换一个方向再继续探索，直至所有可能的通路都探索到为止。如果恰好某一步探索到出口，则就找到了从入口到出口的路径。为了保证在任何位置上都能沿原路退回防止死循环，需要使用堆栈来保存大量记录。而要求解迷宫最短路径则必须用深度优先搜索出所有到达出口的路径通过比较得到最短距离的路径，这样也必然要求增加数据空间来保存搜索过程中当前最短路径，增加了空间复杂度。广度优先搜索（BFS）:从入口出发，离开入口后依次访问与当前位置邻接的单元格（上下左右方向），然后分别从这些相邻单元格出发依次访问它们的邻接格并使“先被访问的单元格的邻接格‘先于’后被访问的单元格的邻接格”被访问直至访问到迷宫出口，则找到了迷宫问题的最优解即迷宫最短路径。该算法的显著特点是“层层推进”，探索点会随着探索的深入急剧增加，相应地，需要大量的空间用来保存探索过程的记录，空间复杂度大。与此同时，上述两种算法都比较抽象复杂编程实现容易出现问题，调试比较困难因此在本篇论文中提出了一种新的容易理解和调试的算法，该算法复杂度较彳氐求解较大规模的迷宫问题也有不俗的表现。3本文算法3.1本文算法基本思想描述首先与其他算法一样，将NXM的图形迷宫表示为一个二维矩阵，用二维数组a[N][M]来存储信息，N和M分别代表迷宫的行数和列数，迷宫中的每个位置都可用矩阵数组的行号和列号来指定。在矩阵中，当且仅当在位置（i，j）处有一个障碍时其值a[i][j]为1，否则其值为0。图2给出了与图1迷宫对应的矩阵描述。其次在本算法中引入了“路径深度”及“路径深度图”的概念。路径深度：从某位置走到出口的最短路径的长度记为depth。，设每一方块为单位路径长度。假定出口处路径深度为0，障碍处路径深度为-1。路径深度图：与迷宫对应的图，每一个节点值为与该节点对应的迷宫单元格的路径深度即该单元格与迷宫出口的最短距离。显然路径深度图有且唯一(因为每个单元格与迷宫出口的最短距离有且唯一)。如图1所示的迷宫入口处的路径深度为12,最短路径为图2中箭头所指出的道路。即：(1,1)-(1,2)-(2,2)-(3,2)-(3,1)-(4,1)-(5,1)-(5,2)-(5,3)-(4,3)-(4,4)-(4,5)-(5,5)。迷宫单元格的路径深度如图3所示。从图3中，可以看出：迷宫最短路径是一条从入口处开始的路径深度逐次递减1的序列。因此如果能求出整个迷宫每个单元格的路径深度从而形成迷宫的路径深度图则求解最短路径就很简单。本论文的关键算法在求解迷宫的路径深度图上。3.2迷宫路径深度图算法定理形成迷宫路径深度图的必要条件是图中每一个节点值不大于周围(上下左右四个可行进方向)最小节点值+1。证明：设点A(x,y)为迷宫中任意一点(非障碍),而点B为与点A邻接点(上下左右四个方向)中节点值最小的点(非障碍)。必要性：假设从点B出发，存在一条到达迷宫出口的最短路径。则从点A出发，可以先到达B点，然后顺着从点B到出口的最短路径，就能到达出口。而由本文路径深度的定义显然有depth(A)Wdepth(A->B->出口)=1+depth(B)。必要性得证。下面给出求解迷宫路径图的算法：步骤1置初值，depth(障碍)=-1,depth(出口)=0,depth(通道)NXM;步骤2交换标记tag置为0;步骤3指针指向某一通道单元格A;步骤4如果当前单元格是迷宫障碍转步骤7;步骤5找出周围可行方向单元格(非障碍)的最小路径深度min(depth());步骤6如果depth(A)>min(depth())+1,则调整depth(A)=min(depth())+1,并记交换标记tag=1;步骤7如果已遍历完所有单元格转步骤9;步骤8指针以某一遍历规则(比如顺序访问)后移，转步骤3;步骤9如果tag=1,转步骤2;步骤10如果tag=0,说明所有单元格路径深度depth()经过动态调整后达到稳定平衡(定理所述状态)，即形成路径深度图，算法结束。现在证明该算法最终形成了路径深度图。用反证法证明。由上述算法形成的图记为图G,假设图G并非本文定义的路径深度图G，，即图G总存在一点A,其节点值depth(A)=k,而该点对应的单元格与迷宫出口的最短路径的长度为l,l<k,设最短路径为AfPl-1fPl-2P1f出口，而在图G中此路径上有l个节点，沿路径顺序其节点值为上界为k,下界为l的递减整数数列因为l<k,由鸽巢原理，则必有一节点Pi,Pi>Pi+1+1,则该图G未达到稳定平衡与前提G是稳定平衡下的路径深度图矛盾，故假设不成立，从而证明了算法形成的最终图就是待求解的路径深度图。3.3通过路径深度图寻找最短路径算法构造出路径深度图G后，就可以很方便地找到迷宫中任意一点到出口的最短路径。在这里以求解迷宫入口到出口的最短路径为例，设depth(s)二k。算法如下：步骤1指针p指向入口，入口位置进路径队列路径深度标记depth二k-1;步骤2寻找p指向的单元格周围(上下左右可行进方向)路径深度等于depth的单元格；步骤3该单元格进入路径队列p指向该单元格，depth--;步骤4如果depth>0,转步骤2;步骤5如果depth=0,说明找到出口，出口位置进入路径队列算法结束。至此，迷宫最短路径新算法结束。4算法评价4.1时间空间复杂度分析本算法主要分两个部分而最主要的时间开销就在第一部分求路径深度图算法上。算法主要过程是逐步判断每个单元格是否与周围4个单元格达到稳定平衡状态时间复杂度为O(4XNXM),空间方面主要需要两个NXM的二维数组(一个存储迷宫信息一个存储路径深度图),故空间复杂度为O(NXM)。第二部分算法为通过路径深度图求最短路径当最短路径长度为k时，时间方面最多需要判断3k次，空间方面路径队列长度为k,其中k=O(N+M),所以时间和空间复杂度均为O(N+M)。综上所述，本算法的时间和空间复杂度均为O(NXM)。而经典算法中广度优先搜索空间复杂度方面除了要两个NXM的二维数组存储迷宫信息和迷宫单元格访问信息外还实验结果显示，不论是峰值信噪比还是滤波图像的视觉质量，数字双边l1滤波器的滤波效果均极为显著性能大大优于中值滤波器。可见，脉冲双边l1滤波器比传统中值滤波器具有更强的噪声抑制能力和边缘保持能力。同时式(10)运算简单,实现方便，因此是对传统中值滤波器极为合理而有效的推广与改进，具有重要的实用价值。5结论本文旨在研究非线性数字滤波器设计问题。基于稳健统计理论和双边滤波思想文中提出稳健的图像复原统一框架并由此导出了一种数字滤波器的统一设计框架简洁地建立了非线性数字滤波器与最优能量泛函框架之间的理论联系。基于统一设计框架，文中提出了一种新型脉冲噪声滤波器即双边l滤波器。双边l1滤波器赋予噪声点的权重相对于图像信息的权重接近于零，更好地抑制了噪声点对滤波过程的影响是一种比中值滤波器更为鲁棒的滤波机制。实验结果验证了双边l1滤波器抑制脉冲噪声的有效性。(收稿日期：2006年2月)参考文献：FARSIUS,ROBINSONMD,ELAD虬etal.Fastandrobustmultiframesuperresolution[J].IEEETransactionsonImageProcessing,2004,13(10):1327-1344.TOMASIC,MANDUCHIR.Bilateralfilteringforgrayandcolorimages[C]//Proc6thIntConfComputerVision,NewDelhi,India,1998:839-846.ELADM.Onthebilateralfilterandw