《最短路径问题》课件.ppt

1、最短路径问题PPT课件 本课件仅供大家学习学习本课件仅供大家学习学习 学习完毕请自觉删除学习完毕请自觉删除 谢谢谢谢 本课件仅供大家学习学习本课件仅供大家学习学习 学习完毕请自觉删除学习完毕请自觉删除 谢谢谢谢最短路径问题平面中的最短路径 如图所示，从A地到B地有三条路可供选择，你会选走哪条路最近？你的理由是什么？两点之间 线段最短FEDCBA 问题：如图，点 A，B 分别是直线 l 异侧的两个点，在 l 上找到一个点，CA CB 最短 作法：连接点 A，B 与直线 l 相交于点 C （CA+CB）min=ABA.l.BC 问题 2：相传，古希腊亚历山大里亚城里有一位久负盛名的学者，名叫海伦。

2、有一天，一位将军专程拜访海伦，求教一个百思不得其解的问题：从图中的A 地出发，到一条笔直的河边l 饮马，然后到B 地。到河边什么地方饮马可使他所走的路线全程最短？BAl 精通数学、物理学的海伦稍加思索，利用轴对称的知识回答了这个问题。这个问题后来被称为“将军饮马 问题”。你能将这个问题抽象为数学问题吗？BAl将A，B 两地抽象为两个点，将河l 抽象为一条直线。BAl AC 作法：1、过点 A 作直线 l 的 对称点 A2、连接 AB，与直 线 l 相交于点 P3、连接点A,P此时（AP+PB）min P将A，B 两地抽象为两个点，将河l 抽象为一条直线。BAl A C证明：AP1+P1B=AP

3、1+P1B AB =AP+PB =AP+PB AP1+P1BAP+PB同理：AP2+P2BAP+PB故 （AP+PB）minP1P2P 问题 3：牧马营地在点P处，每天牧马人要赶着马群先到草地a上吃草，再到河边b饮水，最后回到营地，请你设计一条放牧路线，使其所走的总路程最短？b.Pa草地河b.Pa草地河 作法：1、作点P关于直线a的对称点P1，关于直线b对称点P22、连接P1P2，分别交直线 a,b于点A，B3、连接PA，PB，由对称轴的性质知，PA=P1A，PB=P2B先到点A处吃草，再到点B处饮水，最后回到营地，这时的放牧路线总路程最短，即(PB+BA+AP)minBP2AP1b.Pa草地

4、河 证明：PA1+A1B1+B1P =P1A1+A1B1+B1P2 P1A+AB+BP2 =PA+AB+BP PA1+A1B1+B1P PA+AB+BP故 （PA+AB+BP）minBP2AP1B1A1 问题 4：为了做好国庆期间的交通为了做好国庆期间的交通安全工作，某交警执勤小队从A处出发，先到公路 l1 上设卡检查，再到公路 l2 上设卡检查，最后再到达B地执行任务，他们如何走才能使总路程最短？l1l2.A.Bl1l2A.B 作法：1、作点 A 关于直线 l1 的对称点 A12、作点 B 关于直线 l2 的对称点 B13、连接 A1B1，分别交直线 l1,l2 于点 C，D，则沿路线ACD

5、B 走，才能使总路程最短先到点 C 处设卡检查，再到点 D 处设卡检查，最后回到 B 处执行任务，这时的路线总路程最短。即（AC+CD+DB）minA1C D B1l1l2A.B 证明：AE+EF+FB =A1E+EF+FB1 =A1E+EG+GF+FB1 A1G +GB1 =A1B1 =A1C+CD+DB1 =AC+CD+DBAE+EF+FBAC+CD+DB故 （AC+CD+DB）minA1C D B1E F G 问题 5：如图，A，B两地在一条河的两岸，现要在河上建一座桥MN，桥造在何处才能使从A到B的路径最短？（假设河的两岸是平行的直线，桥要与河垂直）作法：1、将点B沿垂直与河岸的方 向

6、平移一个河宽到E 2、连接AE交河对岸与点M,则 点M为建桥的位置，MN为 所建的桥。.A.BNM.EABNME 证明：AC+CD+DB =AC+CD+CE =AC+CE+CD AE+CD =AM+ME+CD =AM+NB+MN AC+CD+DB AM+NB+MN故（AM+NB+MN）minCD（2011年）A，B两所学校在一条东西走向公路的同旁，以公路所在直线为x轴建立如图所示的平面直角坐标系。(1)一辆汽车由西向东行驶，在行驶过程中是否存在一点C，使C点到A，B两校的距离相等？如果有，请用尺规作图找出该点，保留作图痕迹；(2)若在公路边建一游乐场P，使游乐场到两校距离之和最 小，通过作图在

7、图中找出所建 游乐场的位置 OA.Bxy 作法：（1）连接 A，B点，以A，B为圆心，任意半径画圆，交点为点M，N，连接MN，交x轴于点C，则点C就是所求点，即 CA=CB（2）过A点做 x 轴的对称点A1点，连接 A1B 交 x 轴于点 P，则点 P 就是所求点，即（AP+PB）minOA.BxyMNCPA1最短路径问题 立体图形中的最短路径 问题 6：如图 在一个底面周长为20cm,高AA为4cm的圆柱石凳上，若小明在吃东西时留下了一点食物在B处，恰好一只在A处的蚂蚁捕捉到这一信息，于是它想从A 处爬向B处，你们想一想，蚂蚁怎么走最近？BAA 蚂蚁蚂蚁AB的路的路线线BAAdABAABBA

8、OBAArO4怎样计算AB？在RtAAB中，利用勾股定理可得，222BAAAAB侧面展开图其中AA是圆柱体的高,AB是底面圆周长的一半(r)结论：圆柱体中的最短路径为展开图中一半矩形的对角线长。例：有一圆形油罐底面圆的周长为24m，高为6m，一只老鼠从距底面1m的A处爬行到对角B处吃食物，它爬行的最短路线长为多少？A.B分析：由于老鼠是沿着圆柱的表面爬行的，故需把圆柱展开成平面图形.根据两点之间线段最短，可以发现A、B分别在圆柱侧面展开图的宽1m处和长24m的中点处，即AB长为最短路线.(如图)解：AC=6 1=5 BC=24 =12 由勾股定理得 AB=13(m)BAC222169ABACB

9、C12问题 7：如图，是一个三级台阶，它的每一级的长、宽和高分别等于5cm，3cm和1cm，A和B是这个台阶的两个相对的端点，A点上有一只蚂蚁，想到B点去吃可口的食物.请你想一想，这只蚂蚁从A点出发，沿着台阶面爬到B点，最短线路是多少？BAABC531512 AB2=AC2+BC2=169 AB=13问题 8：如图，边长为1的正方体中，一只蚂蚁从顶点A出发沿着正方体的外表面爬到顶点B的最短距离是（）（A）3 （B）（C）2 （D）1AB分析：由于蚂蚁是沿正方体的外表面爬行的，故需把正方体展开成平面图形（如图）。CABC21B5左面和上面前面和上面前面和右面问题9：如图，一只蚂蚁从实心长方体的顶

10、点A出发，沿长方体的表面爬到对角顶点C1处（三条棱长如图所示），问怎样走路线最短？最短路线长为多少？ABA1B1DCD1C1214分析:根据题意分析蚂蚁爬行的路线有三种情况(如图),由勾股定理可求得图1中AC1爬行的路线最短.ABDCD 1C1421AC1=442 2+3+32 2=25=25 前面和上面前面和上面ABB1CA1C1412 AC1=662 2+1+12 2=37=37 前面和右面前面和右面AB1D1DA1C1412 AC1=552 2+2+22 2=29=29左面和上面左面和上面 1、如图是一个长方体木块，已知AB=5,BC=3,CD=4，假设一只蚂蚁在点A处，它要沿着木块侧面爬到点D处，则蚂蚁爬行的最短路径是 。ABCD54374 2、现要在如图所示的圆柱体侧面A点与B点之间缠一条金丝带（金丝带的宽度忽略不计），圆柱体高为6cm，底面圆周长为16cm，则所缠金丝带长度的最小值为 。AB10cm