最短路径问题课件.ppt

《最短路径问题课件.ppt》由会员分享，可在线阅读，更多相关《最短路径问题课件.ppt（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、最短路径问题探究最短路径的实质：“化弯为直化弯为直” 如图所示，从如图所示，从A A地到地到B B地有三条路地有三条路可供选择，你会选走哪条路最近？可供选择，你会选走哪条路最近？你的理由是什么？你的理由是什么？ 两点之间两点之间,线段最短线段最短FEDCBA已知：如图，已知：如图，A，B在直线在直线L的两的两侧，在侧，在L上求一点上求一点P，使得，使得PA+PB最小。最小。 P连接连接AB,线段线段AB与直线与直线L的交点的交点P ，就是所求。，就是所求。问题问题1相传，古希腊亚历山大里亚城里有一位久相传，古希腊亚历山大里亚城里有一位久负盛名的学者，名叫海伦有一天，一位将军专程拜访负盛名的学者

2、，名叫海伦有一天，一位将军专程拜访海伦，求教一个百思不得其解的问题：海伦，求教一个百思不得其解的问题：从图中的从图中的A 地出发，到一条笔直的河边地出发，到一条笔直的河边l 饮马，然饮马，然后到后到B 地到河边什么地方饮马可使他所走的路线全程地到河边什么地方饮马可使他所走的路线全程最短？最短？探索新知探索新知BAl精通数学、物理学的海伦稍加思索，利用轴对称的精通数学、物理学的海伦稍加思索，利用轴对称的 知识回答了这个问题这个问题后来被称为知识回答了这个问题这个问题后来被称为“将军饮马将军饮马 问题问题”你能将这个问题抽象为数学问题吗？你能将这个问题抽象为数学问题吗？ 探索新知探索新知BAl将将

3、A，B 两地抽象为两个点，将河两地抽象为两个点，将河l 抽象为一条直抽象为一条直 线线 BAl问题问题2 如图，点如图，点A，B 在直线在直线l 的同侧，点的同侧，点C 是直是直 线上的一个动点，当点线上的一个动点，当点C 在在l 的什么位置时，的什么位置时，AC 与与CB 的和最小？的和最小？ BlA作法：作法：（1）作点）作点B 关于直线关于直线l 的对称的对称 点点B；（2）连接）连接AB，与直线，与直线l 相交相交 于点于点C 则点则点C 即为所求即为所求 如图，点如图，点A，B 在直线在直线l 的同侧，点的同侧，点C 是直是直线上的一个动点，当点线上的一个动点，当点C 在在l 的什么

4、位置时，的什么位置时，AC 与与CB 的和最小？的和最小？ BlABC你能用所学的知识证明你能用所学的知识证明AC + +BC最短吗？最短吗？ BlABC证明：证明：如图，在直线如图，在直线l 上任取一点上任取一点C（与点（与点C 不不重合），连接重合），连接AC，BC，BC 由轴对称的性质知，由轴对称的性质知， BC = =BC，BC=BC AC + +BC = = AC + +BC = = AB， AC+ +BC = = AC+ +BC你能用所学的知识证明你能用所学的知识证明AC + +BC最短吗？最短吗？ BlABCCBlABCC在在ABC中中， ABAC+ +BC， AC + +BCA

5、C+ +BC即即AC + +BC 最短最短已知：如图已知：如图A是锐角是锐角MON内部任意一点，内部任意一点，在在MON的两边的两边OM，ON上各取一点上各取一点B，C，组成三角形，使三角形周长最小，组成三角形，使三角形周长最小.BCDE分析：分析：当当ABAB、BCBC和和ACAC三条边的长度恰好能够体现在三条边的长度恰好能够体现在一条直线上时，三角形的周长最小一条直线上时，三角形的周长最小 已知：如图已知：如图A是锐角是锐角MON内部任意一点，内部任意一点，在在MON的两边的两边OM，ON上各取一点上各取一点B，C，组成三角形，使三角形周长最小，组成三角形，使三角形周长最小.分别作点分别作

6、点A关于关于OM，ON的对称的对称点点A，A；连接；连接A，A，分别交，分别交OM，ON于点于点B、点、点C，则点，则点B、点点C即为所求即为所求1. 如图，A.B两地在一条河的两岸，现要在河上建一座桥MN，桥造在何处才能使从A到B的路径AMNB最短？（假设河的两岸是平行的直线，桥要与河垂直）ABMNE作法：作法：1.1.将点将点B B沿垂直与河岸的方向平移一个河宽沿垂直与河岸的方向平移一个河宽到到E E， 2.2.连接连接AEAE交河对岸与点交河对岸与点M,M, 则点则点M M为建桥的位置，为建桥的位置，MNMN为所建的桥为所建的桥。证明：由平移的性质，得证明：由平移的性质，得 BNEM B

7、NEM 且且BN=EM, BN=EM, MN=CD, BD MN=CD, BDCE, BD=CE,CE, BD=CE,所以所以A.BA.B两地的距两地的距: :AM+MN+BN=AM+MN+EM=AE+MN,AM+MN+BN=AM+MN+EM=AE+MN,若桥的位置建在若桥的位置建在CDCD处，连接处，连接AC.CD.DB.CE,AC.CD.DB.CE,则则ABAB两地的距离为：两地的距离为：AC+CD+DB=AC+CD+CE=AC+CE+MN,AC+CD+DB=AC+CD+CE=AC+CE+MN,在在ACEACE中，中，AC+CEAC+CEAE,AE, AC+CE+MNAC+CE+MNAE+MN,AE+MN,即即AC+CD+DB AC+CD+DB AM+MN+BNAM+MN+BN所以桥的位置建在所以桥的位置建在CDCD处，处，ABAB两地的路程最短。两地的路程最短。ABMNECD