迷 宫 最短路径 093670 施沈翔.

Presentation on theme: "迷 宫 最短路径 093670 施沈翔."— Presentation transcript:

1 迷 宫 最短路径 施沈翔

2 问题的提出 应用背景： 最短运输问题、校园导游问题 对于一个陌生环境进行摸索而得到众多路径 中的最短路径 迷宫的最短路径问题

3 运用内容 二维数组maze[i][j] 有向图 广度优先搜索 队列（链队列）

4 表示迷宫（基本假设） 二维数组maze[i][j]表示迷宫，可取0或1， 0表示走通，1表示受阻 迷宫入口坐标为[0][0],出口坐标为
[m-1][n-1],而且maze[0][0]=0, maze[m-1][n-1]=0 迷宫有向图 列 0 1 2 3 4 5 行0 6 列 0 1 2 3 4 5 行0 广 度 优 先 搜 索 弧 表2从入口到当前方位所走步数 图1 表示迷宫的有向图 表1 迷宫及其最短路径

5 数据结构运用 那么我们需要解决两个问题 （1）如何用数据结构实现和迷宫相应的有向图 （2）如何用数据结构得到路径

6 数据结构迷宫有向图 g=i+di[v] h=j+dj[v] v=0,1…….7
通过上面的假设，我们自然用二维数组maze表示迷 宫，从迷宫的任意一个方位（i,j）出发,一般情况下 可能有8个方向可走，如图2所示。假设可以到达下 一方位的坐标为（g,h），则 g=i+di[v] h=j+dj[v] v=0,1…….7 i-1, j+1 i+1 , j+1 i , j+1 i , j i -1, j i +1, j i , j-1 i-1 , j-1 i +1, j-1 图2 .8个相邻位置的坐标

7 数据结构迷宫有向图 di 1 -1 dj 其中下标增量数组是di和dj（v的值=0为向东方向， 之后顺时针旋转增加）。
如果当前方位（i,j）是有向图中的一个“顶点”（即 相应坐标元素为0），则其“邻接点”由计算所得元 素值为0的方位（g,h）而得。 （i,j+1） （i+1，j） （i，j-1） （i-1，j） di 1 -1 dj （i+1，j+1） （i-1，j-1） （i-1，j+1） （i+1，j-1） 表3 下标增量数组

8 数据结构路径 保存搜索路径顶点 记录是从哪一个顶点搜索到该顶点的
在到达出口方位时逆搜索方向“倒退”回到入口， 以确定从入口到出口的最短路径。 怎样实现？那我们可以运用链队列的知识,下面先进 行补充。

9 队列和链队列 队列（queue）是限定只能在表的一端进行插入，在 表的另一端进行删除的线性表。允许插入一端为队尾 （rear），允许删除的一端为队头（front），并且 遵从先进先出（FIFO，即First In First Out）的原 则。 用链表表示的队列——链队列 一个链队列需要两个分别指向队头和队尾的指针（分 别称为头指针和尾指针）。 出队列 （队头元素）a1 a2 ---- --- an （队尾元素） 入队列 图3 队列结构示意图

10 数据结构路径 我们用链队列结构和它们的操作来改变广度优先遍历： 一是在出队列时“只修改队头指针而不删除队头结 点”；
二是入队列时，在你新插入的队尾结点中“加入弧尾 顶点（方位）的信息”。 为此，在链队列的结点中增加一个指针域，它的值指 向当前出队列的的顶点（即从“队头”到“队尾”之 间存在一条弧）。 。

11 数据结构路径 列 0 1 2 3 4 5 行0 6 表2 从入口到当前方位所走步数 图4 最短路径搜索过程中的队列 0,0 1,1 1,2
2,0 2,3 3,1 0,2 Q．front Q．rear 列 0 1 2 3 4 5 行0 6 表2 从入口到当前方位所走步数 图4 最短路径搜索过程中的队列

12 Matlab程序思路 (1)产生迷宫矩阵maze[i][j]和下标增量数组; (2)建立链队列的头指针、尾指针和指向弧尾位置的 指针；
(4)找到路径后，逆搜索方向“倒退”回到入口，以 确定从入口到出口的最短路径。

13 结果分析 下面是运行matlab程序后，根据所得的不同类型的 maze矩阵(随机而得)的三种不同的情况。
图中，绿色点为入口，红色点为出口，黑色点为所的 路径。 图5.1有最短路径

14 结果分析 图5.3开始便搜索受阻 图5.2 没有最短路径，只进行了一些搜索

15 推广与总结 这样的问题还可以推广为骑士巡游问题，也就是：设 有一个m×n的棋盘(2≤m≤50,2≤n≤50)，在棋盘上任 一点有一个中国象棋“马”，马走的规则为：马走日字 ；马只能向右走。当m,n给出后，同时给出马起始的 位置和终点的位置，试找出从起点到终点所有路径的 数目，并求最短路径。 这样的问题思路都是有相通之处的：首先表示出用二 维数组表示出棋盘，然后将其生成有向图，并用链队 列进行广度优先搜索或深度优先搜索，最后逆路径而 得最短路径。 Thank you!