龙空技术网

神奇的最短路径问题,掌握了这个技巧,你也能成为学霸

优博数学 5051

前言:

如今大家对“数据结构找最短路径”大约比较讲究,同学们都需要了解一些“数据结构找最短路径”的相关知识。那么小编也在网上收集了一些有关“数据结构找最短路径””的相关文章,希望兄弟们能喜欢,朋友们一起来学习一下吧!

最短路径问题是小学数学应用问题难题,这类题一般会出现在奥数培优课堂上,从知识点上分析,这类题并没有超纲,但孩子普遍反映对这类题适应性不好,今天我就系统讲解一下最短路径问题。

将军在A地,要回B地的营地,在回营地之前,先要到一条河边给马喝水,请你帮他找到一条最短路线,在图中表示出来。

著名的将军饮马问题

这是一道典型的最短路径问题,也是著名的将军饮马问题。做这类题,我们首先要掌握两个基本性质:

①两点间线段最短。这个很好理解,从A地到B地,一定是直线距离最短。

②镜面反射中,入射角等于出射角。这个我们一会儿用具体的图形表示。

这道题我们可以做出A点关于这条河(图中的直线)的对称点A',然后连接A'B,与直线相交于点O,此O点即为将军饮马点。图示如下:

寻找对称点是突破口

题目做完了,但为什么O点就是我们要找的点呢?我们不妨换一个点来试试,比如下图中的O‘点。

三角形中两边之和大于第三边

我们来看一下上图,由于A'和A是关于直线对称的,因此,OA=OA',因此,将军饮马的距离OA+OB=OA'+OB=A'B。

而如果我们换一个点O‘,此时将军饮马的距离是O'A+O'B,根据对称性,O'A=O'A',因此,将军饮马的距离O'A+O'B=O'A'+O'B,显然,这里的距离要大于点A‘和点B的直线距离,所以说,我们通过寻找A关于直线的对称点A',再与B连线相交直线的点O才是将军应该饮马的合理地点。

看来,寻找对称点是解决最短路径问题的关键,那么我们再出一道最短路径问题,看看你会不会做?

有两个村庄A和B被一条河隔开,现在要架一座桥MN,使得由A到B的路程最短,桥应当架在什么地方?(河岸是平行的,桥垂直于两岸)

这道题和上一道题很相似,但也有不同,不同的地方是两点在河的两岸,同时,这条河是有宽度的,那么这道题应该怎么做呢?

显然,河上的桥长MN是不变的,这个距离我们不需要考虑,我们重点应该放到AM+BN上。

观察上图我们发现,AM和BN并不是平行的,如果两者平行会出现什么情况呢?我们再画一幅图来看看。

显然,AM+BN=AM+B'M=AB',是两个点之间的直线距离,因此,这样做会确保AB之间的距离最短。具体的,我们可以过B点向上做BB‘=MN,找到B'点后,连接AB',使其交河岸于点M,当然,也可以过A点向下做AA'=MN,找到A'点后,连接A'B,使其交河岸于点N,结果是一样的。

我们再来看一道类似的题目:要在两条街道AB、CD上设立两个邮箱,K处是邮局。邮递员从邮局出发,从两个邮箱里取出信件后再回到邮局,邮筒应当设在何处,才能使邮递员所走的路线最短?

这道题和例题一很相似,不同的是只有一个点,却有两条线,这道题的做法也是寻找对称点,从对称点出发解决问题,如下图所示:

我们来解释一下为什么通过做两次对称点,并连接两个对称点与AB、CD相交的M、N两点就是题目要求的点,看一下下图:

根据题意,邮递员走的路径就是KM+MN+NK,观察上图,根据对称性,KM=K'M,NK=NK'',因此,上图中KM+MN+NK=K'K'',是两点之间的最短距离。

总结一下:解决最短路径问题的一个重要的突破口就在于构造对称点,因为构造出对称点后,题目中的点与点之间距离和问题可以转化为两点之间的距离问题,通过两点之间直线距离最短这个重要的性质,就可以求得最短路径了。

标签: #数据结构找最短路径 #数据结构找最短路径的方法