迷宫最短路径doc资料.ppt

《迷宫最短路径doc资料.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、迷宫最短路径二维数组maze[i][j]有向图广度优先搜索队列（链队列）运用内容列012345行00266112522343345表示迷宫（基本假设）二维数组maze[i][j]表示迷宫，可取0或1，0表示走通，1表示受阻迷宫入口坐标为[0][0],出口坐标为[m-1][n-1],而且maze[0][0]=0,maze[m-1][n-1]=0列012345行0010100110011020110013100110表1迷宫及其最短路径弧迷宫有向图图1表示迷宫的有向图表2从入口到当前方位所走步数广度优先搜索那么我们需要解决两个问题（1）如何用数据结构实现和

2、迷宫相应的有向图（2）如何用数据结构得到路径数据结构运用通过上面的假设，我们自然用二维数组maze表示迷宫，从迷宫的任意一个方位（i,j）出发,一般情况下可能有8个方向可走，如图2所示。假设可以到达下一方位的坐标为（g,h），则数据结构迷宫有向图g=i+di[v]h=j+dj[v]v=0,1…….7i-1,j+1i+1,j+1i,j+1i,ji-1,ji+1,ji,j-1i-1,j-1i+1,j-1图2.8个相邻位置的坐标其中下标增量数组是di和dj（v的值=0为向东方向，之后顺时针旋转增加）。如果当前方位（i,j）是有向图中的一个“顶点”（即相应坐标

3、元素为0），则其“邻接点”由计算所得元素值为0的方位（g,h）而得。di01110-1-1-1dj110-1-1-101表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）是限定只能在表的一端进行插入，在表的另一端进行删除的线性表。允许插

4、入一端为队尾（rear），允许删除的一端为队头（front），并且遵从先进先出（FIFO，即FirstInFirstOut）的原则。用链表表示的队列——链队列一个链队列需要两个分别指向队头和队尾的指针（分别称为头指针和尾指针）。队列和链队列出队列（队头元素）a1a2-------an（队尾元素）入队列图3队列结构示意图我们用链队列结构和它们的操作来改变广度优先遍历：一是在出队列时“只修改队头指针而不删除队头结点”；二是入队列时，在你新插入的队尾结点中“加入弧尾顶点（方位）的信息”。为此，在链队列的结点中增加一个指针域，它的值指向当前出队列的的顶点（即

5、从“队头”到“队尾”之间存在一条弧）。。数据结构路径图4最短路径搜索过程中的队列列012345行00266112522343345表2从入口到当前方位所走步数1,20,01,12,02,33,10,2Q．frontQ．rear数据结构路径(1)产生迷宫矩阵maze[i][j]和下标增量数组;(2)建立链队列的头指针、尾指针和指向弧尾位置的指针；(3)用matlab的动态数组实现队列，进行广度优先搜索；(4)找到路径后，逆搜索方向“倒退”回到入口，以确定从入口到出口的最短路径。Matlab程序思路下面是运行matlab程序后，根据所得的不同类型的maz

6、e矩阵(随机而得)的三种不同的情况。图中，绿色点为入口，红色点为出口，黑色点为所的路径。结果分析图5.1有最短路径结果分析图5.2没有最短路径，只进行了一些搜索图5.3开始便搜索受阻这样的问题还可以推广为骑士巡游问题，也就是：设有一个m×n的棋盘(2≤m≤50,2≤n≤50)，在棋盘上任一点有一个中国象棋“马”，马走的规则为：马走日字；马只能向右走。当m,n给出后，同时给出马起始的位置和终点的位置，试找出从起点到终点所有路径的数目，并求最短路径。这样的问题思路都是有相通之处的：首先表示出用二维数组表示出棋盘，然后将其生成有向图，并用链队列进行广度优先搜索

7、或深度优先搜索，最后逆路径而得最短路径。推广与总结Thankyou!此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢