13.4最短路径问题

1、13.4 课题学习课题学习 最短路径问题最短路径问题第第10周周2015年年11月月2日日 前面我们研究过一些关于前面我们研究过一些关于“两点的所有连线中，线两点的所有连线中，线 段最短段最短”、“连接直线外一点与直线上各点的所有线段连接直线外一点与直线上各点的所有线段中，垂线段最短中，垂线段最短”等的问题，我们称它们为最短路径问等的问题，我们称它们为最短路径问 题题 下面我们就下面我们就“将军饮马问题将军饮马问题”和造桥选址问题一起和造桥选址问题一起来来看看吧！看看吧！引言：引言：问题问题1相传，古希腊亚历山大里亚城里有一位久相传，古希腊亚历山大里亚城里有一位久负盛名的学者，名叫海伦有一天，

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

3、题抽象为数学问题吗？ BAl想一想想一想这是一个实际问题，你打算首先做什么？这是一个实际问题，你打算首先做什么？ 将将A，B 两地抽象为两个点，将河两地抽象为两个点，将河l 抽象为一条直抽象为一条直 线线 BAl想一想想一想你能用自己的语言说明这个问题的意思，并把它抽象你能用自己的语言说明这个问题的意思，并把它抽象为数学问题吗？为数学问题吗？ （1）从）从A 地出发，到河边地出发，到河边l 饮马，然后到饮马，然后到B 地；地； （2）在河边饮马的地点有无穷多处，）在河边饮马的地点有无穷多处，现在的问题是怎样找出使现在的问题是怎样找出使两条线段长度之和为最两条线段长度之和为最 短的直线短的直线l

4、上的点上的点（3）设）设C 为直线上的一个动点，上面的问题就转化为：当为直线上的一个动点，上面的问题就转化为：当点点C 在在l 的什么位置时，的什么位置时，AC 与与CB 的和最小（如图）的和最小（如图） BAlC想一想想一想作法：作法：（1）作点）作点B 关于直线关于直线l 的对称点的对称点B；（2）连接）连接AB，与直线，与直线l 相交于相交于点点C 则点则点C 即为所求即为所求 问题问题2 如图，点如图，点A，B 在直线在直线l 的同侧，点的同侧，点C 是直是直线上的一个动点，当点线上的一个动点，当点C 在在l 的什么位置时，的什么位置时，AC 与与CB 的和最小？的和最小？ BlABC

5、想一想，做一做想一想，做一做证明：如图，在直线证明：如图，在直线l 上任取一点上任取一点C（与点（与点C 不不重合），连接重合），连接AC，BC，BC 由轴对称的性质知，由轴对称的性质知， BC = =BC，BC=BC AC + +BC = = AC + +BC = = AB， AC+ +BC = = AC+ +BC问题问题3 你能用所学的知识证明你能用所学的知识证明AC + +BC最短吗？最短吗？ BlABCC 在在ABC中中， ABAC+ +BC， AC + +BCAC+ +BC即即AC + +BC 最短最短想一想，做一做想一想，做一做若直线若直线l 上任意一点（与点上任意一点（与点C 不

6、重合）与不重合）与A，B 两点的距离两点的距离和都大于和都大于AC + +BC，就说明，就说明AC + + BC 最小最小 BlABCC追问追问1 1证明证明AC AC + +BC BC 最短时，为什么要在直线最短时，为什么要在直线l l 上上任取一点任取一点C C（与点（与点C C 不重合），证明不重合），证明AC AC + +BC BC ACAC+ +BCBC？这里的？这里的“C C”的作用是什么的作用是什么？ 想一想，做一做想一想，做一做 如图所示，要在街道旁修建一个牛奶站，向如图所示，要在街道旁修建一个牛奶站，向居民区居民区A A、B B提供牛奶，奶站应建在什么地方，才提供牛奶，奶站应

7、建在什么地方，才能使从能使从A A、B B到它的距离之和最短到它的距离之和最短 试一试试一试 居民居民B . 居民居民A .街道街道AMNB ABCD试一试试一试 L如图：如图：A为马厩，为马厩，B为帐篷，牧马人某一天要从马厩牵出为帐篷，牧马人某一天要从马厩牵出马，先到草地边某一处牧马，再到河边饮马，然后回到马，先到草地边某一处牧马，再到河边饮马，然后回到帐篷，请你帮他确定这一天的最短路线。帐篷，请你帮他确定这一天的最短路线。 作法：作法： 1.作点作点A关于直线关于直线 MN 的的 对称点对称点A , 2. 作点作点B关于直线关于直线L 的对称点点的对称点点B , 3.连接连接A B 分别交

8、直线分别交直线MN、L于点C、D， 则A-C-D-B最短ABMNE.作法：作法： 1.1.将点将点B B沿垂直与河岸沿垂直与河岸的方向平移一个河宽到的方向平移一个河宽到E E， 2.2.连接连接AEAE交河对岸交河对岸与点与点M,M,则点则点M M为建桥的位置，为建桥的位置，MNMN为所建的桥为所建的桥。P86 如图，如图，A.BA.B两地在一条河的两岸，现要在河上建一两地在一条河的两岸，现要在河上建一座桥座桥MNMN，桥造在何处才能使从，桥造在何处才能使从A A到到B B的路径的路径AMNBAMNB最短？最短？（假设河的两岸是平行的直线，桥要与河垂直）（假设河的两岸是平行的直线，桥要与河垂直）造桥选址问题造桥选址