haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 小学教育 > 学科竞赛学科竞赛

最短路线问题

发布时间:2013-12-08 11:34:09  

在日常生活、工作中,经常会遇到有关行 程路线的问题。比如:邮递员送信,要穿 遍所有的街道,为了少走冤枉路,需要选 择一条最短的路线;旅行者希望寻求最佳 旅行路线,以求能够走最近的路而达到目 的地,等等。这样的问题,就是我们所要 研究学习的“最短路线问题”。

?

?
?

例[1] 假如直线AB是一条公路,公路两旁有甲乙两个村子,如下图1。 现在要在公路上修建一个公共汽车站,让这两个村子的人到汽车站的 路线之和最短。问:车站应该建在什么地方? 图1图 甲
A B

?

?
? ?



分析 如果只考虑甲村的人距离公路AB最近,只要由甲村向公路AB画一条垂直线,交AB于C点,那么C 点是甲村到公路AB最近的点,但是乙村到C点就较远了。
?

?

反过来,由乙村向公路AB画垂线,交AB于D点,那么D点是乙村到公路AB最近的点。但是这时甲村 到公路AB的D点又远了。 因为本题要求我们在公路AB上取的建站点,能够兼顾甲村和乙村的人到这个车站来不走冤枉路(既 路程之和最短),根据我们的经验:两个地点之间走直线最近,所以,只要在甲村乙村间连一条直 线,这条直线与公路AB交点P,就是所求的公共汽车站的建站点了(图2)。

?

?

解 用直线把甲村、乙村连起来。因为甲村乙村在公路的两侧,所以这条连线必与公路AB有一个交 点,设这个交点为P,那么在P点建立汽车站,就能使甲村乙村的人到汽车站所走的路程之和最短。

? ?

乙村

甲村

A

B

?

?

分析:找到甲村关于AB的对称点C,连接C和乙村交AB 的那一点即为汽车站。

?
? ?

分析 为了叙述的方便,我们在各交叉点标上字母(见图)。
小明家 我们从小明家出发,顺序往前推。由于从小明家到A、B、C、D各处都是沿直线行走,所以都只有一种走法。我们 分别在交叉点处标上“1”。而从小明家到E处,就有先到A或先到D的两种走法,正好是两个对角上标的数1+1的和。 从小明家到F点,则有3条路线,又正好是两个对角上标的数1+2的和。 标在各交叉点的数,就是依次顺序推出的到各交叉点能有多少种不同的路线的数。从中我们可以看出,每个格内上 右角与下左角两个对角上的数的和,正好等于下右角上的数。 小明家 A 1 B 1 C 1 D 1 E F 2F G 3G H 4H

?

?

? ? ?

4I

?
? ? ?

J J2

5 K K5

9 L L9

1 M13 学校

解 从小明家到学校有13条不同的路线。如图7所示。
?

如图4—6,从甲地到乙地最近的道路有几条?

? 每个格左上角与右下角所标的数 ? 字和即为这格

右上角应标的数字
我们称这种方法为对角线 法,也叫标号法


网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com