资源描述：
《第十五讲 最短路线问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第十五讲最短路线问题本文由GTX2004贡献doc文档可能在WAP端浏览体验不佳。建议您优先选择TXT，或下载源文件到本机查看。小学奥数:小学奥数:最短路线在日常生活,工作中,经常会遇到有关行程路线的问题.比如:邮递员送信,要穿遍所有的街道,为了少走冤枉路,需要选择一条最短的路线;旅行者希望寻求最佳旅行路线,以求能够走最近的路而达到目的地,等等.这样的问题,就是我们所要研究学习的"最短路线问题".典型例题是一条公路,公路两旁有甲乙两个村子,例[1]假如直线AB是一条公路,公路两旁有甲乙两个村子,如下图1.现在要在公路上修建一个公共汽
2、车站,让这两个村子的人到.现在要在公路上修建一个公共汽车站,汽车站的路线之和最短.汽车站的路线之和最短.问:车站应该建在什么地方?车站应该建在什么地方?甲B乙图1甲B乙图2AA分析如果只考虑甲村的人距离公路AB最近,只要由甲村向公路AB画一条垂直线,交AB于C点,那么C点是甲村到公路AB最近的点,但是乙村到C点就较远了.反过来,由乙村向公路AB画垂线,交AB于D点,那么D点是乙村到公路AB最近的点.但是这时甲村到公路AB的D点又远了.因为本题要求我们在公路AB上取的建站点,能够兼顾甲村和乙村的人到这个车站来不走冤枉路(既路程之和最短
3、),根据我们的经验:两个地点之间走直线最近,所以,只要在甲村乙村间连一条直线,这条直线与公路AB交点P,就是所求的公共汽车站的建站点了(图2).解用直线把甲村,乙村连起来.因为甲村乙村在公路的两侧,用直线把甲村,乙村连起来.因为甲村乙村在公路的两侧,甲村乙村在公路的两侧所以这条连线必与公路AB有一个交点,设这个交点为P,那么在P有一个交点,,点建立汽车站,就能使甲村乙村的人到汽车站所走的路程之和最短.点建立汽车站,就能使甲村乙村的人到汽车站所走的路程之和最短.所示,例[2]一个邮递员投送信件的街道如图3所示,图上数字表示各段街道的千
4、米数.他从邮局出发,要走遍各街道,最后回到邮局.各段街道的千米数.他从邮局出发,要走遍各街道,最后回到邮局.问:走什么样的路线最合理?全程要走多少千米?走什么样的路线最合理?全程要走多少千米?124213分析选择最短的路线最合理.那么,什么路线最短呢?一笔画路线应该是最短的.邮递员从邮局出发,还要回到邮局,按一笔画问题,就是从偶点出发,回到偶点.因此,要能一笔把路线画出来,必须途径的各点全是偶点.但是图中有8个奇点,显然邮递员要走遍所有街道而又不走重复的路是不可能的.要使邮递员从邮局出发,仍回到邮局,必须使8个奇点都变成偶点,就是要
5、考虑应在哪些街道上重复走,也就是相当于在图上添哪些线段,能使奇点变成偶点.如果有不同的添法,就还要考虑哪一种添法能使总路程最短.为使8个奇点变成偶点,我们可以用图4的4种方法走重复的路12421132421线.3(a)1242112(b)42133(c)图4(d图4中添虚线的地方,就是重复走的路线.重复走的路程分别为:(a)3×4=12(千米)(b)3×2+2×2=10(千米)(c)2×4=8(千米)(d)3×2+4×2=14(千米)当然,重复走的路程最短,总路程就最短.从上面的计算不难找出最合理的路线了.解邮递员应按图4(c)所示
6、的路线走,这条路重复的路程最()所示的路线走,短,所以最合理.全程为:所以最合理.全程为:(1+2+4+2+1)×2+3×6+2×4++++)+×+×=20+18+8++=46(千米)(千米)例[3]图5中的线段表示的是小明从家到学校所能经过的所有街道.街道.小明上学走路的方向都是向东或向南,小明上学走路的方向都是向东或向南,因为他不想偏离学校的方向而走冤枉路.那么小明从家到学校可以有多少条不同的路线?方向而走冤枉路.那么小明从家到学校可以有多少条不同的路线?北小明家学校分析为了叙述的方便,我们在各交叉点标上字母(见图6).A小明家
7、BEFFFDE我们从小明家出发,顺序往前推.由于从小明家到A,B,C,D各处都是沿直线行走,所以都只有一种走法.我们分别在交叉点处标上"1".而从小明家到E处,就有先到A或先到D的两种走法,正好是两个对角上标的数1+1的和.从小明家到F点,则有3条路线,又正好是两个对角上标的数1+2的和.标在各交叉点的数,就是依次顺序推出的到各交叉点能有多少种不同的路线的数.从中我们可以看出,每个格内上右角与下左角两个对角上的数的和,正好等于下右角上的数.条不同的路线.所示.解从小明家到学校有13条不同的路线.如图7所示.北小明家A11D2E2MB
8、13F5NC14G9K学校413H图7小结寻找最短路线,不应该走"回头路".寻找最短路线,不应该走"回头路"要按照一定的逻辑次序来排列可能路线,既要做到不重复数,也不漏数.辑次序来排列可能路线,既要做到不重复数,也不漏数.对比较复杂的
