迷宫最短路径问题新算法

1、迷宫最短路径问题新算法摘 要：提出了求解迷宫最短路径问题的新算法 该算法抛弃了经典算法（深度优先搜索和广度优先搜索 中繁杂低效的递归、回溯思想。通过合理的变换，将原问题转化为迷宫路径深度图的生成问题。最后对算法进行了严谨的分析和实例测试，显示出该算法易于理解、易于编程、时间空间复杂度低等优点。关键词：最短路径；时间复杂度；深度优先搜索；广度优先搜索New Algorithm for Solving Shortest Path of Maze ProblemZHANG Lin- feng, LV Hui, QU Jun- feng(The Missile Institute, Air Force

2、 Engineering University, Sanyuan, Shannxi 713800, China)Abstract: A new algorithm is presented for solving the shortest path of maze problem, which is not based on the inefficient recursive backtracking theory of classical algorithm (DFS- Depth First Search and BFS- Breadth First Search).Byappropria

3、te conversion, the algorithm changes the original problem into the creation of the maze graph problem.At last,an example is given, which shows that the new algorithm is easy to be understood and programmed as well as its lowtime and space complexity.Key words: shortest path; time complexity; Depth F

4、irst Search; Breadth First Search1问题描述迷宫最短路径(the shortest path of maze)问题是一个典型的搜索、遍历问题其程序设计思想在人工智能设计、机器人设计等事务中均有应用。如图1所示，一个NXM的大方块迷宫，带斜线的单元格表 示墙壁（障碍），空白的单元格表示通道。迷宫问题可以表述为 寻找从某一个给定的起始单元格（迷宫入口）出发，经由行相邻 或列相邻的通道单元格 最终可以到达目标单元格（迷宫出 口）,所走过的单元格序列。行进中 只能沿上下左右四个方向 刖进。而迷宫最短路径问题就是找出从迷宫入口到出口所经过 单元格个数最少的路径。2经典算法

5、求解迷宫问题，经典算法有深度优先搜索和广度优先搜索 两种深度优先搜索（DFS）:从入口出发，顺着某一方向向前探 索，若能走通则继续彳主前走；否则沿原路退回（回溯）,换一个 方向再继续探索，直至所有可能的通路都探索到为止。如果恰 好某一步探索到出口，则就找到了从入口到出口的路径。为了 保证在任何位置上都能沿原路退回防止死循环，需要使用堆 栈来保存大量记录。而要求解迷宫最短路径则必须用深度优 先搜索出所有到达出口的路径 通过比较得到最短距离的路 径，这样也必然要求增加数据空间来保存搜索过程中当前最短 路径，增加了空间复杂度。广度优先搜索（BFS）:从入口出发，离开入口后依次访问 与当前位置邻接的单

6、元格（上下左右方向），然后分别从这些相 邻单元格出发依次访问它们的邻接格 并使“先被访问的单元 格的邻接格先于后被访问的单元格的邻接格”被访问直至 访问到迷宫出口，则找到了迷宫问题的最优解即迷宫最短路 径。该算法的显著特点是“层层推进”，探索点会随着探索的深 入急剧增加，相应地，需要大量的空间用来保存探索过程的记 录，空间复杂度大。与此同时，上述两种算法都比较抽象复杂 编程实现容易 出现问题，调试比较困难 因此在本篇论文中提出了一种新的 容易理解和调试的算法，该算法复杂度较彳氐 求解较大规模的 迷宫问题也有不俗的表现。3本文算法3.1本文算法基本思想描述首先与其他算法一样，将NXM的图形迷宫表

7、示为一个二维矩阵，用二维数组aNM来存储信息，N和M分别代表迷宫 的行数和列数，迷宫中的每个位置都可用矩阵数组的行号和列 号来指定。在矩阵中，当且仅当在位置（i，j）处有一个障碍时其 值aij为1，否则其值为0。图2给出了与图1迷宫对应的矩 阵描述。其次在本算法中引入了 “路径深度”及“路径深度图”的 概念。路径深度：从某位置走到出口的最短路径的长度 记为 depth。，设每一方块为单位路径长度。假定出口处路径深度为 0，障碍处路径深度为-1。路径深度图：与迷宫对应的图，每一个节点值为与该节点对应的迷宫单元格的路径深度 即该单元格与迷宫出口的最短距离。显然路径深度图有且唯一(因为每个单元格与迷

8、宫出口的最短距离有且唯一)。如图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迷宫路径深度图算法定理 形成迷宫路径深度

9、图的必要条件是 图中每一个节点值不大于周围(上下左右四个可行进方向)最小节点值+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交换

10、标记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()经过动 态 调整后达到稳定平衡(定理所述状态)，即形成路径深度图，算法 结束。现在证明该

11、算法最终形成了路径深度图。用反证法证明。由上述算法形成的图记为图G,假设图G并非本文定义的路径深度图G，即图G总存在一点A,其节点值depth(A)=k,而该点对应的单元格与迷宫出口的最短路径的长度为l, lk,设最短路径为AfPl-1f Pl-2P1f出口，而在图G中此路径上有l个节点，沿路径顺序其节点值为上界为k,下界为l的递减整数数列因为lPi+1+1,则该图G未达到稳定平衡与前提G是稳定平衡下的路径深度图矛盾，故假设不成立，从而证明了算法形成的最终图就是待求解的路径深度图。3.3通过路径深度图寻找最短路径算法构造出路径深度图G后，就可以很方便地找到迷宫中任意一点到出口的最短路径。在这里

12、 以求解迷宫入口到出口的最短路径为例，设depth(s)二k。算法如下：步骤1指针p指向入口，入口位置进路径队列 路径深度标记 depth二k- 1;步骤2寻找p指向的单元格周围(上下左右可行进方向)路径深 度等于depth的单元格；步骤3该单元格进入路径队列p指向该单元格，depth-;步骤4如果depth0,转步骤2;步骤5如果depth=0,说明找到出口，出口位置进入路径队列 算 法结束。至此，迷宫最短路径新算法结束。4算法评价4.1时间空间复杂度分析本算法主要分两个部分 而最主要的时间开销就在第一部分求路径深度图算法上。算法主要过程是逐步判断每个单元格是否与周围4个单元格达到稳定平衡状

13、态时间复杂度为O( 4XNXM),空间方面主要需要两个NXM的二维数组(一个存储迷宫信息一个存储路径深度图),故空间复杂度为 O(NXM)。第二部分算法为通过路径深度图求最短路径当最短路径 长度为k时，时间方面最多需要判断3k次，空间方面路径队 列长度为k,其中k=O( N+M),所以时间和空间复杂度均为 O( N+M)。综上所述，本算法的时间和空间复杂度均为O(NXM)。而经典算法中广度优先搜索 空间复杂度方面除了要两个NXM的二维数组存储迷宫信息和迷宫单元格访问信息外 还 实验结果显示，不论是峰值信噪比还是滤波图像的视觉质 量，数字双边l1滤波器的滤波效果均极为显著性能大大优于中值滤波器。

14、可见，脉冲双边l1滤波器比传统中值滤波器具有更强的噪声抑制能力和边缘保持能力。同时式(10)运算简单, 实现方便，因此是对传统中值滤波器极为合理而有效的推广与 改进，具有重要的实用价值。5结论本文旨在研究非线性数字滤波器设计问题。基于稳健统计理论和双边滤波思想 文中提出稳健的图像复原统一框架 并 由此导出了一种数字滤波器的统一设计框架 简洁地建立了非 线性数字滤波器与最优能量泛函框架之间的理论联系。基于统 一设计框架，文中提出了一种新型脉冲噪声滤波器 即双边l滤波器。双边l1滤波器赋予噪声点的权重相对于图像信息的权重接近于零，更好地抑制了噪声点对滤波过程的影响 是一种 比中值滤波器更为鲁棒的滤

15、波机制。实验结果验证了双边l1滤波器抑制脉冲噪声的有效性。(收稿日期：2006年2月)参考文献：FARSIU S, ROBINSON M D, ELAD 虬 et al.Fast and robust multiframe super resolutionJ.IEEE Transactions on Image Processing, 2004, 13(10): 1327- 1344.TOMASI C, MANDUCHI R.Bilateral filtering for gray and color imagesC/ /Proc 6th Int Conf Computer Vision, New Delhi, India, 1998: 839- 846.ELAD M.On the bilateral filter an