| 网站首页 | 数学 | 名师 | 奥数 | 下载 | 素材 | 交流 | 智力 | 专业 | 设计 | 中学 | 数学博览 | 
您现在的位置: 小学数学专业网 >> 奥数 >> 奥数课堂 >> 专题讲座 >> 正文 用户登录 新用户注册
最短线路
作者:佚名    奥数来源:本站原创    点击数:    更新时间:2009-2-3
查找本文相关资源   相关书籍
 最短线路

  同学们,对最短线路问题你一定很陌生吧.让我们先用一个历史故事向你介绍这个问题.

  古希腊亚里山大里亚城有一位久负盛名的学者,名叫海伦.有一天,有位将军不远千里专程前来向海伦求教一个百思不得其解的问题:

  如图28-1,从甲地出发到河边饮马,然后再到乙地军营视察,显然有许多走法.问走什么样的路线最短呢?精通数理的海伦稍加思索,便作了完善的回答.这个问题后来被人们称作“将军饮马”问题.

  事实上,不仅是将军有这样的烦恼,运动着的车、船、飞机,包括人们每天走路都要遇到这样的问题.古今中外的任何旅行者总希望寻求最佳的旅行路线,尽量走近道,少走冤枉路.我们把这类求近道的问题统称最短线路问题.

  啊!原来这就是最短线路问题,我们已经在小学教科书上几次接触过.

  比如,三年级(第六册)书上说:“从学校到电影院有三条路(图28-2),小云要看电影走哪条路最近?”;

  又如,四年级(第八册)书上说:“通过度量可以知道‘从直线外一点到这条直线所画的各线段中,以和这条直线垂直的线段为最短’.”

  另外,从某种意义上说,上节的一笔画问题也属这类问题.看来最短线路问题在生产、科研和日常生活中确实重要且应用广泛.

  但是.怎样走才是近道呢?这可不是件容易的事.它慢慢地引起了数学家的兴趣,并用数学这个强有力的工具解决了它.下面来看看数学家是怎样解决的.

问题28.1 假如直线AB是一条公路,在路两侧有甲、乙两个村子(如图28-3),现在要在公路上修一个公共汽车站,让这两村的人到车站的路线之和最短.问车站应修建在什么地方?

分析 如果只考虑甲村人距公路最近,由教材上的结论,只要由甲村向AB画一条垂线,交AB于C,那么C离甲村最近,但离乙村又远了.同样只考虑乙村近的线路乙—D—甲也不是最近的.怎样才能使甲、乙两村整体考虑时最近(即距离之和最短)呢?根据我们的经验:两个地点之间走直线最近.所以,在甲、乙之间连一条直线与AB相交于P点,则在P点建站就合要求了.

  注意:以上我们是凭经验作出的解答.但是数学家解决问题,总是要用一些公认的结论去对问题进行严格的证明才算正确,并把公认的结论称作公理.

  下面我们把解决最短线路问题时常用的公理列在下面.

  公理1 连接两点的所有线中,直线段最短.

  公理2 三角形的两边之和大于第三边.

  公理3 直线外一点到直线的所有线中垂线段最短.

  公理是从实践中总结出来的任何人都承认的原始道理.当然,有同学会想:“你那个公理我不承认行不行呢?”那可不行,比如图28-4(1)中,有一只鸡子在B点觅食,你在A点处放一些米,那么鸡子一定会沿直线AB跑过来吃食,决没有一只蠢鸡子沿B→C→A或沿B→D→A的路线跑过来.这表明:公理不但人类公认,连动物界也都遵循它.

  下面我们就用上述公理来解决一些最短线路问题.

问题28.2 如图28-5,点A、B位于直线l的同侧,

  在l上找一点P,使得AP+PB最小.

分析 这就是“将军饮马”问题,我们看看海伦是怎么解决的.海伦发现这是一个求折线和最短的问题.从上面的公理1只知道两点间直线段最短.那么,显然要把折线变成直线再解.如果直接连AB,与l不会相交.怎么办呢?由问题28.1得到启发:

  当A、B位于l的异侧时,就有交点了.于是我们就希望在l的另一侧找一点A′,使得连A′B与l相交于P点后(这时A′P+PB最短)线段A′P与AP一样长.由对称的知识可知道,A关于l的对称点就有资格扮演A′的角色.

如图28-5,先作A关于l的对称点A′,连接A′B与l相交于P点,则AP+PB就最小。那么这样作出的AP+PB是否真的最小呢?要证明它只需要在l上任取一点P′,证明AP′+P′A>AP+PB就行了.这点好证明:事实上因为A′、A关于l对称,有AP=A′P、AP′=A′P′,又由公理2

  AP′+P′B=A′P′+P′B>A′B

  =A′P+PB=AP+PB.

  原来海伦本解决本问题时,是利用作对称点把折线问题转化成直线问题求解的.后来这一方法已形成了思想,它在解决许多问题中都在起作用.现在人们把凡是用对称点来实现解题的思想方法叫对称原理.

问题28.3 在问题28.2中能否作B点关于l的对称点去解?

问题28.4 如图28-6(1)所示的是一个军港地图,海岸线AC和BC上停满了军舰.亨特将军要从军营X到指挥所Y去,但到Y点之前他要依次去AC和BC两岸视察军舰.说同学们给亨特将军设计一条跑线,使他尽快地在完成视察后到达Y点.

分析 显然,要尽快到达只要路径最短即可.我们的目的是要在AC和BC上各确定一点M、N,使得路线X→M→N→Y最短.假若先能用什么办法确定M、N中的一点,则确定另一点的方法与问题28.2相同.故关键是确定M、N中的一点.不妨先确定M点.试想若y点不在陆地上而在濒临BC岸的海中,则确定M的方法也与问题28.2相同.这是因为当Y在海中时,最短路X→M→Y已经通过了BC岸.似现在Y在陆地不在海中,我们自然想到用对称原理作Y关于BC的对称点Y′(Y′在海中).因为这时X到Y′的最短路X→M→Y′与BC相交于N点.而 X→M→N→Y 又与X→M→y′路程相同,故它是海足条件的最短路线.

先作Y关于BC的对你点 Y′,再作Y′关于AC的对称点 y″.连结X与Y″与AC交于M点,再连结M与Y′与BC相交于N点,则X→M→N→Y即为将军行动的最短路径.

  注意:本题实际上是把对称原理连续使用了两次:先作Y′关于AC的对称点Y″确定M点,后又作Y关于BC的对称点确定N.这样就确保了X→M→Y′ 即(X→M→N→Y)最短.

  在都市里的闹市区,如果我们仔细观察,马路上的人行横道线都是垂直穿过路面的(图28-7),从没看到过倾斜穿过的.这是为什么?原来闹市区来往的车辆很多,行人穿越马路时应力求距离最短、时间最少.我们在马路一边要过马路时,相当于一点(人)到马路对边(直线)的距离.由公理3知人行道必垂直路面,这就是穿马路原则.它在其它实际问题中也有许多应用,请看:

问题28.5 A、B两村之间有一条河流,河两岸大致平行,如图28-8.现在要在河上架一座桥与两岸垂直,这座桥应架在什么地方才能使A到B的路程为最近?

分析 本题实际上是要在两岸各找一点M、N,使得AM+MN+NB最短,同时要保证MN垂直于河岸,因此是要求最短的折线.但是只知道两点间直线段最短,所以要是能把四点的折线问题转化成两点间的直线段问题就好了.若注意到河宽MN为一定数,就看到了转化的希望.现在难度在于MN挡在A、B“中间”,无法直接在A、B间作直线段.于是自然会想到把MN平行移动到与A(或B)相连.这时,相应地也就相当于把A平移到了A′,这时A′、B之间就不再有桥相隔,因而就可直接连线段了.

如图28-8作AA′垂直于河岸.使AA′等于河宽.

  连接 A′B交另一岸于 N,以N为一端建桥MN,则路线A→M→N→B最短.

  请大家想一想问题28.5还有没有另外的解法?

问题28.6 有一地区有A、B、C、D四个村庄.现要建一所学校P,使P到A、B、C、D的距离之和最小,问P应建在什么地方?

可把村庄看成点.(1)当有一个点在其它三个点组成的三角形内部时,请读者自己思考.

  (2)当四个村庄如图28-9所示时,P建在四边形ABCD的对角线上时,PA+PB+PC+PD最小.

  这个证明请读者自己去完成.

问题28.7若问题28.6中只有A、B、C三个村庄,学校又该建在何处?

  这是个著名的问题.告诉你结论吧:若三角形内一点向它的三条边所张的角都是120°时,则该点到三顶点的距离之和就最小.由于本问题是费马1640年提出的,故此点叫费马点。

  求最短路线问题的另一个基本思路是:不走或少走重复的路线.在“一笔画图形”一节,我们讨论过这个问题.下面,再进一步研究一笔画理论的一个应用——邮递线路问题.

问题28.8 一个邮递员投送信件的街道如图

  28-10,其上标有各段街道的旅程.他从邮局出发,走遍各街道,最后回到邮局,问走什么样的路线最合理?

分析 显然,邮递线路问题就是一笔画问题中能回到起点的那种情况.故解决此问题是以一笔画的理论为基础的.

  比如当街道图有2n(n≥1)个奇点时,我们就要在奇点间走n条重复的路才能回到邮局.

  这就是一笔画问题中“在每两个奇点之间增加一条连线可使两个奇点同时变偶点”的结论的应用.

  当然邮递线路问题也有与一笔画问题不同之处,那就是它必须考虑每段线的长度.

  为了叙述方便,我们把添加重复线路后没有奇点的图叫作一个,而把线路总长度最短的解叫最优解.可以证明:最优解是存在的.但肯定了最优解存在问题只解决了一半,至于怎么找到最优解,数学家们得到了以下结论:

  如果一个街道图满足:

  (1)两(奇)点间重复的路不得多于一条;

  (2)图上每个(无重点的)闭合路径上,重复线长度之和不超过闭合路长的一半,那么,这样的解为最优解.

  由于篇幅所限,我们不打算去证明这个结论.显然,以上两条是为了确保总路程尽可能短.另外,如果一条重复的线越过一个奇点去与另一奇点相连一定不是最优解.

图28-10中有8个奇点,为使它们都成为偶点,必须要重复4段路线(用虚线表示).

  我们给出如图28-11的4个解(其实还有多个解).对图(1)、(2)、(4)均有闭合路径Ai→Bi→Ci→Di(i=1,2,3),重复路线长超过全路径长的一半.唯有图(3)是最优解.此路径全长32千米.

  找到了一个街道图的最短邮递路线,就会使邮递效率大大提高.

练习28

  1.图28-12中,a是地平面,A、B是两个空间观测站.在A站附近执行任务的“明星号”航天飞机要到地面携带仪器后再到B站执行任务.问飞机在什么地方着陆才使飞行路线最近?

  2.在问题28.4中若将军从 X到Y点之前先去BC岸,后去AC岸,请你设计一条最短路线.

  3.甲、乙两村间隔了宽度相同的两条河(见图28-13),为了使两村之间能道路相通,必须在两条河上各架一座桥,问在什么位置架桥才使行程最短?

  4.图28-14表示甲、乙、丙三个军事驻地.请问:供应军需的物资库应设在何处才最优?

  5.请你给问题28.5另一种解法.

  6.请证明问题28.5“解”中的路线最短.7.请证明问题28.6和问题28.7中的结论.8.一个邮递员投递的街区如图28-15所示.图上数字表示各街道长度.他从邮局出发走遍各街道,最后回到邮局,请你为他设计一条最优投递线路,并求出全程的路线长.

奥数录入:管理员    责任编辑:管理员 
  • 上一篇奥数:

  • 下一篇奥数: 没有了
  • 发表评论】【加入收藏】【告诉好友】【打印此文】【关闭窗口
    横式谜
    最短线路
    (只显示最新10条。评论内容只代表网友观点,与本站立场无关!)