迷宫最短路径问题的计算机解法

第一篇：迷宫最短路径问题的计算机解法

文章编号:10060042(14)111;

/ / 假设迷宫入口的出发点存于seat [thepath(int m ,int n)/ / 0 < m ≤M

2{/ / 变量声明部分———对所用其它变量完成变

量声明

i = 0;/ / 此处开始给迷宫设置围墙 while(i < = n + 1)

{maze[0 ] [i ] = 1;maze[m + 1 ] [i ] = 1;i = i + 1;} i = 1;

while(i < = m + 1)

{maze[i ] [0 ] = 1;maze [i ] [ n + 1 ] = 1;i = i + 1;} i = 1;

/ / 此处开始建立迷宫;并对标志数组初始化 while(i < = m){j = 1;while(j < = n)

{maze [i ] [j ] = random(1);

/ / 随机函数产生0 或1 并赋予迷宫 / / 可用Pat 值调整0 与1 的比例,然后打印迷

宫相应位置(略)

status [i ] [j ] = 0;j = j + 1;} i = i + 1;}

/ / 读入dire 数组;按顺时针建立八个方向上的位移(略);

/ / 寻找最短路径

if(maze [1 ] [1 ] = = 0 & & maze [m] [ n ] = = 0)/ / 出入口都可通行

top = 1;

/ / top 指向seat 数组中最新记入迷宫通行点的位置 f = 1;

/ / f 指向seat 数组中存放即将作为新出发点的位置 j = 0;/ / j = 0 ,表示找不到最短路径;j = 1 ,表示

成功找到最短路径

while(f < = top)/ / 以下为Critical Loop 循环 {i = 1;while(i < = 8)

{/ / 从f 所指的出发点出发,对八个方向搜索可

通行的位置

x = seat [f ] [0 ] + dire[i ] [1 ];y = seat [f ] [1 ] + dire[i ] [2 ];if(x = = m & & y = = n){/ / 找到最短路径,打印输出 printf(“%d , %d n”,m ,n);while(f!=thepath

6.算法分析 6.1 时间复杂性

这里选用渐进时间复杂度(Asymptotic

Time Complexity)。作为问题的基本操作的 原操作,应是其重复执行次数和算法的执行 时间成正比的原操作,多数情况下它是最深 层循环内的语句中的原操作,它的执行次数 和包含它的语句的频度(Frequency Count)相 同。因此,建立迷宫需要的时间为O(m 3 n)。在最坏情况下有m 3 n-1 个位置要进 入seat 数组,所以寻找路径也需要O(m 3 n),总的时间复杂性为O(m 3 n)。6.2 空间复杂性

本问题的空间复杂度(Space Complexi2

ty)与算法密切相关,它不仅需要存储空间来 寄存迷宫本身所用的信息,还需要一些对数 据进行操作的工作单元和存储一些实现计算

所需信息的辅助空间。

其中,数组maze、status、seat 所需要的空 间都与m 3 n 成正比,其余都是常数。所以, 总的空间复杂性为O(m 3 n)。

此外,尚需说明的是,所谓当前位置“可 通”,指的是未曾走到过的通道,即要求该位 置不仅是通道,而且既不在当前路径上(否则 所求路径就不是简单路径),也不是曾经纳入 过路径的通道(否则只能在死胡同内转圈)。一个迷宫的最短路径可能不止一条,本 算法只给出首先找到的一条。首先找到哪一条最短路径,与在任一位置上对八个方向的 搜索次序有关,即与dire 数组元素值的排列 次序有关(如图1 所示),调整dire 数组元素

值的排列次序,就可得到其它的最短路径。

参考文献

[1 ]严蔚敏、吴伟民.数据结构[M].北京:清华大学

出版社,2002.[2 ]郭洁志.计算机软件实践[M].陕西:西北电讯出

版社,1985.[3 ]黄刘生、唐策善.数据结构[M].安徽:中国科学

技术大学出版社,2002.[4 ]王立柱.C/ C + + 与数据结构[M].北京:清华大

学出版社,2002.45

第17 卷第1 期

2004 年2 月

高等函授学报(自然科学版)

Journal of Higher Correspondence Education(Natural Sciences)Vol.17 No.1 February 2004__

第二篇：最短路径教案

13.4最短路径问题

一、教学内容：本节课的主要内容是利用轴对称研究某些最短路径问题，最短路径问题在现实生活中经常遇到，初中阶段，主要以“两点之间，线段最短”“连接直线外一点与直线上各点的所有连线中，垂线段最短”为知识基础，有时还要借助轴对称、平移、旋转等变换进行研究。

本节课以数学史中的一个经典故事----“将军饮马问题”为载体开展对“最短路径问题”的课题研究，让学生经历将实际问题抽象为数学的线段和最小问题，再利用轴对称将线段和最小问题转化为“两点之间、线段最短”的问题。

二、教学目标

1、能利用轴对称解决简单的最短路径问题

2、再谈岁最短路径的过程中，体会“轴对称”的桥梁作用，感悟转化的数学思想。

三、教学重难点

重点：利用轴对称将最短路径问题转化为“两点之间、线段最短”问题。难点：如何利用轴对称将最短路径问题转化为线段和最小问题。

四、教学问题诊断

最短路径问题从本质上说是最值问题，作为初中学生，在此前很少涉及最值问题，解决这方面问题的数学经验尚显不足，特别是面对具有实际背景的最值问题，更会感到陌生，无从下手。

解答“当点AB在直线l的同侧时，如何在l上找到点C，使AC与BC的和最小”，需要将其转化为“直线l异侧的两点，与直线l上的点的线段的和最小”的问题，为什么需要这样转化，怎样通过轴对称实现转化，一些学生会存在理解上和操作上的困难。

在证明“最短”时，需要在直线上任取一点（与所求做的点不重合），证明所连线段和大于所求作的线段和，这种思路和方法，一些学生想不到。

教学时，教师可以让学生首先思考“直线l异侧的两点，与直线l上的点的和最小”为学生搭建“脚手架”，在证明最短时，教师要适时点拨学生，让学生体会任意的作用。

五、教学过程

教师引语：现实生活中经常会有这样的生活经历，比如学校虽然为我们铺设了一些石板甬路，方便同学们的行走，但是很多时候我们却并不在这些小路上行走，这样做的目的是什么呢？（学生一起回答）如果用数学知识来解释这种行为，那就是我们曾经学习的“两点之间、线段最短”或“垂线段最短”，我们称这样的问题为最短路径问题（板书课题）现实生活中经常涉及到最短路径问题，这节课我们学习的主要任务就是最短路径问题，并用所学知识探究数学史上著名的“将军饮马问题”。

1、情境引入

相传，古希腊亚历山大里亚城里有一位久负盛名的学者，名叫海伦，有一天，有一位将军专门拜访海伦，求教一个百思不得其解的问题：从图中的A地出发，到一条笔直的河边饮马，然后到B地，到河边什么地方饮马，可使他所走的路线全程最短？精通数学、物理学的海伦稍加思索，利用轴对称的知识回答了这个问题。这个问题后来被称为“将军饮马问题”。

2、探究解决问题的方法

问题一：这是一个实际问题，我们首先把它抽象为数学问题，请同学们用自己的语言说明这个问题的意思。

师生活动：学生独立思考后小组交换意见，然后尝试回答，相互补充，最后达成共识，教师根据学生的回答写出问题的板书：如图，已知点A和点B在直线L的同侧，在直线L上找一点C，使AC与BC的和最小。

设计意图：让学生将实际问题抽象为数学问题，即将最短路径问题抽象为“线段和最小问题”。

问题二：由上面的问题我们可以联想到下面的问题：A、B分别是直线L异侧的两点，如何在直线L上找到一点C，使AC与BC的和最小？

师生活动：学生独立思考，画图分析并尝试回答，教师补充。

问题三：对于第一个问题，如何将点B移到L的另一侧，B′处，满足直线L上的任一点C，都保持CB与CB′的长度相等？ 问题四：你能利用轴对称的知识找到符合条件的点B′吗？

师生活动：学生独立考，尝试画图，然后小组交流，学生代表汇报交流成果，师生共同补充：只要作出点B关于直线L的对称点B′，就可以满足CB=CB′,再利用问题二中的方法，连接AB′,则AB′与直线L的交点即为所求。

学生叙述，教师板书并画图，同时学生在练习本上画图。

设计意图：通过搭建台阶，为学生探究问题提供“脚手架”将同侧难以解决的问题提转化为异侧容易解决的问题，渗透转化思想。

3、推理证明“最短”

问题五：你能用所学的知识证明AC+BC最短吗？

师生活动：师生共同分析，然后学生说证明过程，教师板书。

证明：在直线L上任取一点C′（与点C不重合），连接AC′,BC′,B′C′.由轴对称的性质可知，BC=B′C,BC′=B′C′.∴AC+BC=AC+ B′C=AB′, AC′+ BC′= AC′+ B′C′

在△AB′C′中，AB′＜AC′+ B′C′

∴AC+BC＜ AC′+ BC′ 即AC+BC最短。

问题六：这里任取一点C′的作用是什么？

师生活动：学生相互交流，教师适时点拨，最后达成共识：若直线L上任取一点C′与A、B两点的距离之和都大于AC+BC，则说明AC+BC最短。

设计意图：让学生进一步体会做法的正确性，提高逻辑思维能力。

问题七：回顾前面的探究过程，我们是通过怎样的过程、借助什么解决问题的？

师生共同总结：首先作其中一点关于直线的对称点，然后连接另一点与对称点之间的线段，通过轴对称将两条线段和转化到同一条线段上去，这条线段与直线的交点即为所求，整个过程利用了“轴对称”和“两点之间、线段最短“的知识。

设计意图：让学生在反思的过程中，体会轴对称的“桥梁”作用，感悟转化思想，丰富数学活动经验。

4、巩固练习

（1）如图，一艘旅游船从大桥AB的P处前往山脚下的Q处接游客，然后将游客送往河岸BC上，再回到P处，请画出旅游船的最短路径。

师生活动：学生分析解题思路，并相互补充，然后独立完成画图，学生代表上台讲解。基本思路分析：此题中轮船的行走路线共有三段，其中PQ是必经路段，由“两点之间，线段最短”需首先连接PQ，再将河岸BC看成一条直线，这样问题就转化为“点P、Q在直线BC同侧，如何在BC上找一点R，使PR+QR最小”。

设计意图：让学生进一步巩固解决最短路径问题的基本策略和基本方法。

（2）如图，∠XOY内有一点P，在射线OX上找出一点M，在射线OY上找出一点N，使PM+MN+NP最短．

分析：此题的出题背景就是角。本题主要利用了两点之间线段最短的性质通过轴对称图形的性质确定三角形的另两点．

分别以直线OX、OY为对称轴，作点P的对应点P1与P2，连接P1P2交OX于M，交OY于N，则PM+MN+NP最短．

5、课堂小结：教师与学生一起回顾本节课所学主要内容，并请学生回答：（1）本节课研究问题的基本过程是什么？（2）轴对称在所研究的问题中起到什么作用？

6、布置作业：《课时练》第49页1、2、3、4、5、7、8、9

第三篇：ArcGIS网络分析(最短路径问题分析)

网络分析（最短路径问题分析）

一、实验目的：

理解最短路径分析的基本原理，学习利用arcgis软件进行各种类型的最短路径分析的操作。

二、实验准备

1、实验背景：

最短路径分析是空间网络分析中最基本的应用，而交通网络中要素的设置对最短路径的选择有着很大的影响。实验要求根据不同的权重，给出到达指定目的地的路径选择方案，并给出路径长度。

 在网络中指定一个超市，要求分别求出在距离、时间限制上从家到超市的最佳路径。

 给定访问顺序，按要求找出从家经逐个地点达到目的地的最佳路径。

2、实验材料：

软件：ArcGIS Desktop 9.x，实验数据：文件夹ex6中，一个GeoDatabase地理数据库：City.mdb，内含有城市交通网、超市分布图，家庭住址以及网络关系。

三、实验内容及步骤

首先启动ArcMap，选择ex6city.mdb，再双击后选择将整个要素数据集“city”加载进来，然后将“place”点状要素以“HOME”字段属性值进行符号化，1值是家，0值是超市。

第1步 无权重最佳路径的选择  加载 “设施网络分析”工具条（“视图”>>“工具条”，勾选“设施网络分析”），点选旗标和障碍工具板下拉箭头，将旗标放在家和想要去的超市点上。

第2步 加权最佳路径选择

 在设施网络分析工具条上，点选旗标和障碍工具板下拉箭头，将旗标放在家和想去的某个超市点上。

 选择“分析”下拉菜单，选择“选项”按钮，打开“分析选项”对话框，选择“权重”标签页，在“边权重”上，全部选择长度“length”权重属性。 点选“追踪任务”下拉菜单选择“查找路径”。单击“执行”键，则以长度为比重为基础的最短路径将显示出来，这条路径的总成本将显示在状态列。

 上述是通过距离的远近选择而得到的最佳路径，而不同类型的道路由于道路车流量的问题，有时候要选择时间较短的路径，同样可以利用网络分析进行获得最佳路径。

第3步 按要求和顺序逐个对目的点的路径的实现

 在设施网络分析工具条上，点选旗标和障碍工具板下拉箭头，将旗标按照车辆访问的顺序逐个放在点上。

 选择“分析”下拉菜单，选择“选项”按钮，打开“分析选项”对话框，选择“权重”标签页，在“边权重”上，全部选择长度“length”权重属性。 点选“追踪任务”下拉菜单选择“查找路径”。单击“执行”键，则从起点按顺序逐一经过超市最后回到家的最短有效路径将显示出来，这条路径的总成本将显示在状态列。

同样是经过这11个地点，换成权重是时间的，由于道路车流量的不同，如在市中心车流量特别大，车速慢，故而为节约时间，所以使得路径发生很大的改变。

第4步 阻强问题

这里的阻强是指网络中的点状要素或线状要素因为实际中遇到的例如修路，或那个时段车辆饱和，十字路口发生事故等一些缘故而使得要素不可运行，这时原来获得的最短路径就需要进行修正，具体操作如下： 修路的情形出现，即某个路段不可运行，这在网络中的表现是设置阻强，方法有两种，一种是永久性的，直接将网络边要素的属性修改成不可运行。选择要进行设置的边要素，将其属性中的“Enabled”字段改成“False”即可；另一种是暂时性的，设置边要素障碍。即利用边要素障碍添加工具将边设置。



4、心得体会 ：

第四篇：13．4 课题学习最短路径问题

13．4

课题学习

最短路径问题

能利用轴对称解决简单的最短路径问题，体会图形的变化在解决最值问题中的作用，感悟转化思想．

利用轴对称将最短路径问题转化为“两点之间，线段最短”问题．

探索发现“最短路径”的方案，确定最短路径的作图及说理．

一师一优课　一课一名师(设计者：)

一、创设情景，明确目标

如图所示，从A地到B地有三条路可供选择，走哪条路最近？你的理由是什么？

前面我们研究过一些关于“两点的所有连线中，线段最短”、“连接直线外一点与直线上各点的所有线段中，垂线段最短”等的问题，我们称它们为最短路径问题．现实生活中经常涉及到选择最短路径的问题，本节将利用数学知识探究数学史中著名的“将军饮马问题”．

二、自主学习，指向目标

自学教材第85

页至87

页，思考下列问题：

1．求直线异侧的两点与直线上一点所连线段的和最小的问题，只要连接这两点，与直线的交点即为所求，其依据是两点的所有连线中，线段最短．

2．求直线同侧的两点与直线上一点所连线段的和最小的问题，只要找到其中一个点关于这条直线的对称点，连接对称点与另一个点，则与该直线的交点即为所求．

3．在解决最短路径问题时，我们通常利用轴对称、平移等变化把已知问题转化为容易解决的问题，从而作出最短路径的选择．

三、合作探究，达成目标

探索最短路径问题

活动一：相传，古希腊亚历山大里亚城里有一位久负盛名的学者，名叫海伦．有一天，一位将军专程拜访海伦，求教一个百思不得其解的问题：

从图中的A地出发，到一条笔直的河边l

饮马，然后到B地．到河边什么地方饮马可使他所走的路线全程最短？

精通数学、物理学的海伦稍加思索，利用轴对称的知识回答了这个问题．这个问题后来被称为“将军饮马问题”．你能将这个问题抽象为数学问题吗？

追问1　这是一个实际问题，你打算首先做什么？答：将A，B

两地抽象为两个点，将河l

抽象为一条直线．

追问2　你能用自己的语言说明这个问题的意思，并把它抽象为数学问题吗？

答：(1)从A

地出发，到河边l

饮马，然后到B

地；

(2)在河边饮马的地点有无穷多处，把这些地点与A，B

连接起来的两条线段的长度之和，就是从A

地到饮马地，再回到B

地的路程之和；(3)现在的问题是怎样找出使两条线段长度之和为最短的直线l上的点．设C

为直线上的一个动点，上面的问题就转化为：当点C

在l的什么位置时，AC

与CB的和最小(如图)．问题2：如图，点A，B

在直线l的同侧，点C

是直线上的一个动点，当点C

在l的什么位置时，AC与CB的和最小？

追问1：对于问题2，如何将点B“移”到l的另一侧B′处，满足直线l

上的任意一点C，都保持CB

与CB′的长度相等？

追问2：你能利用轴对称的有关知识，找到上问中符合条件的点B′吗？

展示点评：作法：

(1)作点B

关于直线l的对称点B′；

(2)连接AB′，与直线l

交于点C.则点C

即为所求．

问题3　你能用所学的知识证明AC

＋BC最短吗？

证明：如图，在直线l上任取一点C′(与点C

不重合)，连接AC′，BC′，B′C′.由轴对称的性质知，BC

＝B′C，BC′＝B′C′.∴

AC

＋BC＝

AC

＋B′C

＝

AB′，AC′＋BC′＝

AC′＋B′C′.在△AB′C′中，AB′＜AC′＋B′C′，∴

AC

＋BC＜AC′＋BC′.即

AC

＋BC

最短.小组讨论：证明AC

＋BC

最短时，为什么要在直线l

上任取一点C′(与点C

不重合)，证明AC

＋BC

＜AC′＋BC′？这里的“C′”的作用是什么？

反思小结：运用轴对称变换及性质将不在一条直线上的两条线段转化到一条直线上，然后用“两点之间线段最短”解决问题．利用三角形的三边关系，若直线l上任意一点(与点C

不重合)与A，B

两点的距离和都大于AC

＋BC，就说明AC

＋BC

最小.C′的代表的是除点C以外直线l上的任意一点．

针对训练：

1．如图，A、B是河流

同侧的两个村庄，现要在河边修一个抽水站向两村供水，问抽水站修在什么地方才能使所需的管道最短？请在图中表示出来．

答：如下图，作点B关于l的对称点B′，连接AB′交l于点P，点P即为所求．

2．如图，一个旅游船从大桥AB的P处前往山脚下的Q处接游客，然后将游客送往河岸BC

上，再返回P处，请画出旅游船的最短路径．

答：作Q关于直线BC的对称点Q′，连接PQ′交BC于R，∴旅游船线路：P—Q—R—P.选址造桥问题

活动二：(造桥选址问题)如图，A和B两地在一条河的两岸，现要在河上造一座桥MN，桥造在何处可使从A到B的路径AMNB最短？(假定河的两岸是平行的直线，桥要与河垂直．)

展示点评：从A到B要走的路线是A→M→N→B，如图所示，而MN是定值，于是要使路程最短，只要AM＋BN最短即可．

第五篇：八年级数学最短路径问题

八年级数学最短路径问题

一、两点在一条直线异侧

例：已知：如图，A，B在直线L的两侧，在L上求一点P，使得PA+PB最小。

练习、如图，A.B两地在一条河的两岸，现要在河上建一座桥MN，桥造在何处才能使从A到B的路径AMNB最短？（假设河的两岸是平行的直线，桥要与河垂直）

二、两点在一条直线同侧

例：图所示，要在街道旁修建一个奶站，向居民区A、B提供牛奶，奶站应建在什么地方，才能使从A、B到它的距离之和最短．

练习：如图，A、B是两个蓄水池，都在河流a的同侧，为了方便灌溉作物，•要在河边建一个抽水站，将河水送到A、B两地，问该站建在河边什么地方，•可使所修的渠道最短，试在图中确定该点。三、一点在两相交直线内部

例：已知：如图A是锐角∠MON内部任意一点，在∠MON的两边OM，ON上各取一点B，C，组成三角形ABC，使三角形周长最小.练习1：已知：如图A是锐角∠MON内部任意一点，在∠MON的两边OM，ON上各取一点B，C，组成三角形ABC周长最小值为OA.求∠MON的度数。

练习2：某班举行晚会，桌子摆成两直条(如图中的AO，BO)，AO桌面上摆满了桔子，OB桌面上摆满了糖果，坐在C处的学生小明先拿桔子再拿糖果，然后回到座位，请你帮助他设计一条行走路线，使其所走的总路程最短？

提高训练

一、题中出现一个动点。

1.当题中只出现一个动点时,可作定点关于动点所在直线的对称点,利用两点之间线段最短,或三角形两边之和小于第三边求出最值.例：如图，在正方形ABCD中，点E为AB上一定点，且BE=10,CE=14,P为BD上一动点，求PE+PC最小值。

二、题中出现两个动点。当题中出现两个定点和两个动点时,应作两次定点关于动点所在直线的对称点.利用两点之间线段最短求出最值。

例：如图，在直角坐标系中有四个点, A(-8,3),B(-4,5)C(0，n),D(m,0),当四边形ABCD周长最短时,求 C、D的坐标。

练习1如图，∠AOB=30°，点M、N分别在边OA、OB上，且OM=1，ON=3，点P、Q分别在边OB、OA上，则MP+PQ+QN的最小值是

．

三、题中出现三个动点时。

在求解时应注意两点：(1)作定点关于动点所在直线的对称点,(2)同时要考虑点点,点线,线线之间的最短问题.例：如图，在菱形ABCD中,AB=2,∠BAD=60°,E,F,P分别为AB,BC,AC上动点, 求PE+PF最小值 例：如图，∠AOB=45°，角内有一动点P，PO=10，在AO，BO上有两动点Q，R，求△PQR周长的最小值。

练习1如图，∠AOB=30°，角内有一定点P，PO=20cm，在AO，BO上有两动点C、D，求△PCD周长的最小值。