已阅读5页,还剩10页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
迷 宫,最短路径,093670 施沈翔,应用背景: 最短运输问题、校园导游问题 对于一个陌生环境进行摸索而得到众多路径中的最短路径 迷宫的最短路径问题,问题的提出,二维数组mazeij 有向图 广度优先搜索 队列(链队列),运用内容,表示迷宫(基本假设),二维数组mazeij表示迷宫,可取0或1,0表示走通,1表示受阻 迷宫入口坐标为00,出口坐标为 m-1n-1,而且maze00=0, mazem-1n-1=0,表1 迷宫及其最短路径,弧,迷宫有向图,图1 表示迷宫的有向图,表2从入口到当前方位所走步数,广 度 优 先 搜 索,那么我们需要解决两个问题 (1)如何用数据结构实现和迷宫相应的有向图 (2)如何用数据结构得到路径,数据结构运用,通过上面的假设,我们自然用二维数组maze表示迷宫,从迷宫的任意一个方位(i,j)出发,一般情况下可能有8个方向可走,如图2所示。假设可以到达下 一方位的坐标为(g,h),则,数据结构迷宫有向图,图2 .8个相邻位置的坐标,其中下标增量数组是di和dj(v的值=0为向东方向,之后顺时针旋转增加)。 如果当前方位(i,j)是有向图中的一个“顶点”(即相应坐标元素为0),则其“邻接点”由计算所得元素值为0的方位(g,h)而得。,表3 下标增量数组,数据结构迷宫有向图,(i,j+1),(i+1,j+1),(i+1,j),(i+1,j-1),(i,j-1),(i-1,j-1),(i-1,j),(i-1,j+1),保存搜索路径顶点 记录是从哪一个顶点搜索到该顶点的 在到达出口方位时逆搜索方向“倒退”回到入口,以确定从入口到出口的最短路径。 怎样实现?那我们可以运用链队列的知识,下面先进行补充。,数据结构路径,队列(queue)是限定只能在表的一端进行插入,在表的另一端进行删除的线性表。允许插入一端为队尾(rear),允许删除的一端为队头(front),并且遵从先进先出(FIFO,即First In First Out)的原则。 用链表表示的队列链队列 一个链队列需要两个分别指向队头和队尾的指针(分别称为头指针和尾指针)。,队列和链队列,图3 队列结构示意图,我们用链队列结构和它们的操作来改变广度优先遍历: 一是在出队列时“只修改队头指针而不删除队头结点”; 二是入队列时,在你新插入的队尾结点中“加入弧尾顶点(方位)的信息”。 为此,在链队列的结点中增加一个指针域,它的值指向当前出队列的的顶点(即从“队头”到“队尾”之间存在一条弧)。 。,数据结构路径,图4 最短路径搜索过程中的队列,表2 从入口到当前方位所走步数,数据结构路径,(1)产生迷宫矩阵mazeij和下标增量数组; (2)建立链队列的头指针、尾指针和指向弧尾位置的指针; (3)用matlab的动态数组实现队列,进行广度优先搜索; (4)找到路径后,逆搜索方向“倒退”回到入口,以确定从入口到出口的最短路径。,Matlab程序思路,下面是运行matlab程序后,根据所得的不同类型的maze矩阵(随机而得)的三种不同的情况。 图中,绿色点为入口,红色点为出口,黑色点为所的路径。,结果分析,图5.1有最短路径,结果分析,图5.2 没有最短路径,只进行了一些搜索,图5.3开始便搜索受阻,这样的问题还可以推广为骑士巡游问题,也就是:设有一个mn的棋盘(2m50,2n50),在棋盘上任一点有一个中国象棋“马”,马走的规则为:马走日字;马只能向右走。当m,n给出后,同时给出马起始的位置和终点的位置,试找出从起点到终点所有路径的数目,并求最短路径。 这样的问题思路都是有相通之处的
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 公司合作协议书6篇
- 2024年江西省上饶市万年县小升初语文自主招生备考卷含答案
- 2024年河北省秦皇岛市青龙县小升初语文检测卷含答案
- 2024年武邑县小升初语文检测卷含答案
- 解释劳动合同书
- 离婚协议对子女权益的维护规定
- 离婚协议的签署注意事项
- 如何解除离婚协议书
- 离婚协议携手共同面对未来挑战
- 离婚协议的子女人性教育
- 猪胎盘的地方标准
- 测绘收费标准2002
- 中巴铁矿石谈判方案
- 水中氨氮方法验证报告
- 工业机器人技术与应用PPT完整全套教学课件
- 天津市混凝土搅拌站明细表
- 利安隆(内蒙古)新材料有限公司3000吨TMP扩建项目环评报告
- 新加坡公司章程
- 七类作业JSA分析记录表格模板
- 3500字颜体-楷书(2022年-2023年)字帖
- 七年级下《实数》作业设计
评论
0/150
提交评论