提出了求解迷宫最短路径问题的新算法,该算法抛弃了经典算法(深度优先搜索和广度优先搜索)中繁杂低效的递归、回溯思想.通过合理的变换,将原问题转化为迷宫路径深度图的生成问题.最后对算法进行了严谨的分析和实例测试,显示出该算法易于理解、易于编程、时间空间复杂度低等优点.
维普资讯 doc.guandang.net
迷短路径问题新算法宫最 张林锋,吕辉,瞿军锋
(空军工程大学导弹学院,陕西三原 7 3 0 ) 18 0 E— i: e an 2@s h .o mal i r i 5 2 o u c m c
摘要:出了求解迷宫最短路径问题的新算法,提该算法抛弃了经典算法 (度优先搜索和广度优先搜索 )深中繁杂低效的递归、溯思想。过合理的变换,原问题转化为迷宫路径深度图的生成问题。后对算法进行了严谨的分析和实例测回通将最
试,示出该算法易于理解、于编程、间空间复杂度低等优点。显易时 关键词:最短路径;间复杂度;时深度优先搜索;度优先搜索广 文章编号:0 2 8 3 ( 0 6 3— 0 3 0 文献标识码: 中图分类号: P 0 . 10— 3 12 0 )2 0 6— 2 A T31 6
Ne Al o ih o ov n h r e t P t f M a e P o lm w g rt m f r S l i g S o t s a h o z r be Z HANG i l g L l, L I e, V Hl QU u -e g卜fn i J n fn ( h si ntue A rF reE g er gUn es y S nu n S an i7 3 0, hn ) T e Mi l Istt, i oc n i ei i r t,a y a,h n x 1 8 0 C ia se i n n v i Ab t a t s r c:A e lo t m s p e e td o ov n h h r s a f ma e p o lm, h c s n t b s d o h n f n w ag r h i r s ne fr s li g t e s ot t t o z r b e w ih i o a e n t e i e - i e p h
i e trc rie b c t kn h oy o l ia a o h f in e usv a kr c ig te r fcasc grtm ( F— ph FrtS ac n S B e d Frt erh)B c a s l l i D S De t i e rh a d BF— ra t i S ac .y s h s a p p a e o v rin,h lo t m h n e e o gn r b e i t h r a in o e ma e g a h p b e A l t p r r t c n e o t e a g r h c a g s t r i a p lm
n o t e c e t f t z r p r lm. t a, o i s i h i l o o h o s
a xm l i g e,hc hw a te nw a o tm i e y t b n e t d ad p ga e e t l l ea pe s i n w i so st t h e grh s a o eu d ro n r r l v h h l i s s o o mm d a w l a i o s ls s w t n p c o lx t. i me a d s a e c mp e i y Ke r s s o t s p t; me c mp e i De t i t S a c B e d i t S a c y wo d: h re t a t o lx t h i y; p h F r e r h; r a t F r e r h s h s
l问题描述 迷宫最短路径 ( e s o e tp t fmae问题是一个典 t h r s a o z ) h t h
深度优先搜索 ( F )从入口出发,着某一方向向前探 DS:顺索,能走通,继续往前走;则沿原路退回(若则否回溯 )换一个,方向再继续探索 .至所有可能的通路都探索到为止。如果恰直好某一步探索到出口,就找到了从入口到出口的路径。为了则 保证在任何位置上都能沿原路退回,止死循环,要使用堆防需 栈来保存大量记录。而要求解迷宫最短路径,必须用深度优则
型的搜索、遍历问题,程序设计思想在人工智能设计、器人其机 设计等事务中均有应用。 如图 1示,个 N M的大方块迷宫,斜线的单元格表所一 x带示墙壁 (碍 )空白的单元格表示通道。宫问题可以表述为:障。迷
寻找从某一个给定的起始单元格 (宫入口 )发,由行相邻迷出经或列相邻的通道单元格,终可以到达目标单元格 (宫出最迷 口)所走过的单元格序列。行进中,,只能沿上下左右四个方向 前进。 人 口
先搜索出所有到达出口的路径,通过比较得到最短距离的路径 .样也必然要求增加数据空间来保存搜索过程中当前最短这 路径 .加了空间复杂度。增
广度优先搜索 (F )从入口出发,开入口后依次访问 BS:离与当前位置邻接的单元格 (下左右方向 )然后分别从
这些相上,邻单元格出发依次访问它们的邻接格,使“被访问的单元并先格的邻接格‘于’被访问的单元格的邻接格”访问,至先后被直 访问到迷宫出口,找到了迷宫问题的最优解,则即迷宫最短路
径。该算法的显著特点是“层推进”探索点会随着探索的深层,入急剧增加,应地,要大量的空间用来保存探索过程的记相需 出 口
录 .间复杂度大。空
图 1迷宫
与此同时,述两种算法都比较抽象复杂,程实现容易上编 出现问题 .试比较困难,调因此在本篇论文中提出了一种新的
而迷宫最短路径问题就是找出从迷宫入口到出口所经过 单元格个数最少的路径。
容易理解和调试的算法,算法复杂度较低,解较大规模的该求 迷宫问题也有不俗的表现。
2经典算法 求解迷宫问题,典算法有深度优先搜索和广度优先搜索经 两种。
3本文算法 31本文算法基本思想描述 . 首先与其他算法一样,将Ⅳ M的图形迷宫表示为一个二×
作者简介:林锋 (9 1,,士生,究方向:算机控制;辉 (9 1,,士生导师;究方向:算机网络和计算机控制;军锋张 1 8一)男硕研计吕 14一)男博研计瞿 (9 6 )男,士生,究方向:算机控制。 17一,硕研计
计算机工程与应用 2 0 .2 063
6 3

迷宫最短路径问题新算法_工学_高等教育_教育专区。迷宫最短路径问题可是设计迷宫最短路径问题新算法张林锋, 吕辉, 瞿军锋 ( 空军工程大学 导弹学院, 陕西 三原...
迷宫最短路径问题新算法_计算机软件及应用_IT/计算机_专业资料。迷宫最短路径问题新算法 摘要: 提出了求解迷宫最短路径问题的新算法, 该算法抛弃了 经典算法( ...
迷宫最短路径问题新算法_五年级英语_英语_小学教育_教育专区 暂无评价0人阅读0次下载举报文档 迷宫最短路径问题新算法_五年级英语_英语_小学教育_教育专区。...
最短路径求解迷宫问题 暂无评价 14页 2下载券 迷宫最短路径问题新算法 3页 ...路径 计数器,最短路径长度 const int move[4][2]={ {-1,0},{0,1},{...
完成了迷宫最短路径问题的一种 计算机算法,并解决了搜索过程中的 循环绕道问题...17 No. 1 February 2004 0) {/ / 新的通行位置(x ,y) 记入seat 数组 ...
算法分析与设计 查找迷宫的最短路径(深度算法)_...7 3 / 12 一、 问题描述迷宫最短路径( the ...在新位置上继 续进行搜索;如果 4 个方向都走不通...
本文利用蚁群算法求解迷宫最优路径问题 , 获得了较好的实验结果 ,为迷宫问题的求解提供了一条新的 途径 。收稿日期 : 2003 - 12 - 02 — 114 — 图 3 ...
{未出界,未走过则可视为新的结点} inc(open); {队列尾指针加 1} with ...五、 小结本论文主要讨论一种解决迷宫最短路径问题的经典算法,从广度优先方面...
关于迷宫最短路径及所有路径的问题_计算机软件及应用_IT/计算机_专业资料。求... 迷宫最短路径问题新算法 3页 免费 迷宫最短路径问题的计算... 4页 免费 ...
求迷宫问题的最短路径 月 25 日至 2013 年 6 ...maze[1][1]=-1; //标记入口点已经到达 算法 2...front 指向新的出发点 } // 队空循环结束 return...
热门文档