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

1、,授课人：张春涛,13.4 最短路径问题,A,B,. 将军骑马从城堡A出发，到一条笔直的小河边 饮马，然后到军营B。将军问：到河边的什么地方饮马可使他所走的路径最短？,将军饮马问题 ：,A,C,问题一：将军骑马从城堡A出发， 到一条笔直的小河边 饮马 。问：在河边的什么位置饮马,将军所走的路径最短？,问题一：在直线 上找一点C，使AC最短？,直线外一点与直线上所有点的连线中，垂线段最短,A,B,两点之间线段最短,问题二：将军骑马从城堡A出发，到军营B去，途中经过一条笔直的小河 。 将军问：在小河的什么地方饮马可使他所走的路径最短？,问题二：在直线 上找一点C，使CA+CB最小 ？,C,. 将军

2、骑马从城堡A出发，到一条笔直的小河边 饮马，然后到军营B。将军问：到河边的什么地方饮马可使他所走的路径最短？,A,B,A,C,探究一：将军饮马问题,巩固训练：已知：P、Q是ABC的边AB、AC 上的点，你能在BC上确定一点R， 使PQR的周长最短吗？,你学会了吗？,如图：一位将军骑马从城堡A出发，先骑马去草地边OM的某处吃草，再骑马去河边ON喝水，最后回到城堡A， 问：这位将军怎样走路程最短？,O,M,N,探究二：将军饮马问题,数学问题：在射线OM、ON上分别找一点 P、Q，使AP+PQ+QA最短,A,能力训练： 已知P是BAC的边AB上的点， 你能在AC、AB上分别确定一点Q和R， 使 PQ

3、+QR 最短吗？,A,C,P,B,造桥选址问题的延伸探索,造桥选址问题,如图，A和B两地在一条河的两岸，现要在河上造一座桥MN.乔早在何处才能使从A到B的路径AMNB最短？（假定河的两岸是平行的直线，桥要与河垂直）,思维分析,1、如图假定任选位置造桥，连接和，从A到B的路径是AM+MN+BN，那么怎样确定什么情况下最短呢？,2、利用线段公理解决问题我们遇到了什么障碍呢？,问题解决,A1,M,N,如图，平移A到A1，使A1等于河宽，连接A1交河岸于作桥，此时路径最短.,理由；另任作桥，连接，.,由平移性质可知，.,AM+MN+BN转化为，而转化为.,在中，由线段公理知A1N1+BN1A1B,因此

4、 AM+MN+BN,问题延伸一,如图，A和B两地之间有两条河，现要在两条河上各造一座桥MN和PQ.桥分别建在何处才能使从A到B的路径最短？（假定河的两岸是平行的直线，桥要与河岸垂直）,思维分析,如图，问题中所走总路径是AM+MN+NP+PQ+,桥MN和PQ在中间，且方向不能改变，仍无法直接利用“两点之间，线段最短”解决问题，只有利用平移变换转移到两侧或同一侧先走桥长.,平移的方法有三种：两个桥长都平移到A点处、都平移到B点处、MN平移到A点处，PQ平移到B点处,思维方法一,1、沿垂直于第一条河岸的方向平移A点至AA1使AA1=MN，此时问题转化为问题基本题型两点（A1、B点）和一条河建桥（PQ

5、）,2、利用基本问题的解决方法确定桥PQ： （1）在沿垂直于第二条河岸的方向平移A1至A2， 使A1A2=PQ. （2）连接A2B交A2的对岸Q点，在点处建桥PQ.,3、确定PQ的位置，也确定了BQ和PQ，此时问题可转化为由A点、P点和第一条河确定桥MN的位置.,连接A1P交的对岸于点，在点处建桥,问题解决,沿垂直于河岸方向依次把点、，使，； 连接交于点相邻河岸于点，建桥； 连接交的对岸于点，建桥； 从点到点的最短路径为MMN,思维方法二,沿垂直于第一条河岸方向平移点至点，沿垂直于第二条河岸方向平移点至点，连接A1B1 分别交A、B的对岸于N、P两点，建桥MN和PQ.,最短路径AM+MN+NP

6、+PQ+QB转化为AA1+A1B1+BB1.,思维方法三,沿垂直于河岸方向依次把B点平移至B、B，使BBPQ，BBMN； 连接BA交于A点相邻河岸于M点，建桥MN； 连接BN交B的对岸于P点，建桥PQ； 从点到点的最短路径为MMNNP转化为AB2+B2B1+B1B,问题延伸二,如图，A和B两地之间有三条河，现要在两条河上各造一座桥MN、PQ和GH.桥分别建在何处才能使从A到B的路径最短？（假定河的两岸是平行的直线，桥要与河岸垂直）,思维分析,如图，问题中所走总路径是AM+MN+NP+PQ+G+GH+HB,桥MN、PQ和GH在中间，且方向不能改变，仍无法直接利用“两点之间，线段最短”解决问题，只

7、有利用平移变换转移到两侧或同一侧先走桥长.,平移的方法有四种：三个桥长都平移到A点处；都平移到B点处；MN、PQ平移到A点处；PQ、GH平移到B点处,问题解决,沿垂直于河岸方向依次把A点平移至A、A、A3，使AAMN，AAPQ，A2A3 =GH ； 连接A3B交于B点相邻河岸于H点，建桥GH； 连接A2G交第二河与G对岸的P点，建桥PQ； 连接A1P交第一条河与A的对岸于N点，建桥MN. 此时从A到B点路径最短.,沿垂直于河岸方向依次把A点平移至A、A、A3，使AAMN，AAPQ，A2A3 =GH ； 连接A3B交于B点相邻河岸于H点，建桥GH； 连接A2G交第二河与G对岸的P点，建桥PQ； 连接A1P交第一条河与A的对岸于N点，建桥MN. 此时从A到B点路径最短.,问题解决,沿垂直于河岸方向依次把A点平移至A，使AAMN，平移B点至B1、B2 ,使BB1GH，B1B2 =PQ ； 连接A1B2交第一条河与A点相对河岸于N点，交第二条河与N相邻河岸于P点，建桥MN、PQ； 连接B1Q交第三条河与Q相邻河岸的G点，建桥GH； 此时从A到B点路径最短.,问题解决,沿