第28讲 最短线路.docx

第28讲 最短线路.docx

《第28讲 最短线路.docx》由会员分享，可在线阅读，更多相关《第28讲 最短线路.docx（9页珍藏版）》请在冰点文库上搜索。

第28讲最短线路

第28讲最短线路

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

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

　　如图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.5A、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所示.图上数字表示各街道长度.他从邮局出发走遍各街道，最后回到邮局，请你为他设计一条最优投递线路，并求出全程的路线长.