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

《《最短路径问题》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、最短路径问题平面中的最短路径立体图形中的最短路径最短路径问题平面中的最短路径如图所示，从A地到B地有三条路可供选择，你会选走哪条路最近？你的理由是什么？两点之间线段最短思考①②③问题１：如图，点A，B分别是直线l异侧的两个点，在l上找到一个点，CA＋CB最短作法：连接点A，B与直线l相交于点C（CA+CB）min=ABA.l.BC一、一线+两点（异侧）问题2：相传，古希腊亚历山大里亚城里有一位久负盛名的学者，名叫海伦。有一天，一位将军专程拜访海伦，求教一个百思不得其解的问题：从图中的A地出发，到一条笔直的河边

2、l饮马，然后到B地。到河边什么地方饮马可使他所走的路线全程最短？◇BAl二、一线+两点（同侧）精通数学、物理学的海伦稍加思索，利用轴对称的知识回答了这个问题。这个问题后来被称为“将军饮马问题”。你能将这个问题抽象为数学问题吗？BAl二、一线+两点（同侧）将A，B两地抽象为两个点，将河l抽象为一条直线。B··AlA′·C作法：1、过点A作直线l的对称点A′2、连接A′B，与直线l相交于点P3、连接点A,P此时（AP+PB）min二、一线+两点（同侧）P将A，B两地抽象为两个点，将河l抽象为一条直线。B··AlA

3、′·C证明：∵AP1+P1B=A′P1+P1B>A′B=A′P+PB=AP+PB∴AP1+P1B>AP+PB同理：AP2+P2B>AP+PB故（AP+PB）min二、一线+两点（同侧）P1P2P问题3：牧马营地在点P处，每天牧马人要赶着马群先到草地a上吃草，再到河边b饮水，最后回到营地，请你设计一条放牧路线，使其所走的总路程最短？b.Pa草地河三、两线+一点b.Pa草地河作法：1、作点P关于直线a的对称点P1，关于直线b对称点P22、连接P1P2，分别交直线a,b于点A，B3、连接PA，PB，由对称轴的性质知

4、，PA=P1A，PB=P2B∴先到点A处吃草，再到点B处饮水，最后回到营地，这时的放牧路线总路程最短，即(PB+BA+AP)minBP2AP1三、两线+一点三、两线+一点b.Pa草地河证明：∵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上设卡检查，

5、最后再到达B地执行任务，他们如何走才能使总路程最短？l1l2.A.B四、两线+两点l1l2A..B作法：1、作点A关于直线l1的对称点A12、作点B关于直线l2的对称点B13、连接A1B1，分别交直线l1,l2于点C，D，则沿路线A→C→D→B走，才能使总路程最短∴先到点C处设卡检查，再到点D处设卡检查，最后回到B处执行任务，这时的路线总路程最短。即（AC+CD+DB）minA1CDB1四、两线+两点l1l2A..B证明：∵AE+EF+FB=A1E+EF+FB1=A1E+EG+GF+FB1>A1G+GB1=A

6、1B1=A1C+CD+DB1=AC+CD+DB∴AE+EF+FB>AC+CD+DB故（AC+CD+DB）minA1CDB1EFG四、两线+两点问题5：如图，A，B两地在一条河的两岸，现要在河上建一座桥MN，桥造在何处才能使从A到B的路径最短？（假设河的两岸是平行的直线，桥要与河垂直）作法：1、将点B沿垂直与河岸的方向平移一个河宽到E2、连接AE交河对岸与点M,则点M为建桥的位置，MN为所建的桥。四、两线+两点.A.BNM.EABNME证明：∵AC+CD+DB=AC+CD+CE=AC+CE+CD>AE+CD=A

7、M+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，使游乐场到两校距离之和最小，通过作图在图中找出所建游乐场的位置．中考连接OA..Bxy作法：（1）连接A，B点，以A，B为圆心，任意半径

8、画圆，交点为点M，N，连接MN，交x轴于点C，则点C就是所求点，即CA=CB（2）过A点做x轴的对称点A1点，连接A1B交x轴于点P，则点P就是所求点，即（AP+PB）min中考连接OA..BxyMNCPA1最短路径问题立体图形中的最短路径问题6：如图在一个底面周长为20cm,高AA′为4cm的圆柱石凳上，若小明在吃东西时留下了一点食物在B处，恰好一只在A处的蚂蚁捕捉到这一信息，于是它想从A处爬向B