134_课题学习_最短路径问题 (2).ppt

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

1、13.4 课题学习课题学习 最短路径问题最短路径问题造桥选址问题造桥选址问题如图，如图，A和和B两地在一条河的两岸，现要在两地在一条河的两岸，现要在河上造一座桥河上造一座桥MN.桥造在何处才能使从桥造在何处才能使从A到到B的路径的路径AMNB最短？（假定河的两岸是平行最短？（假定河的两岸是平行的直线，桥要与河的直线，桥要与河垂直垂直）BA思维分析思维分析BA 1、如图假定任选位置造桥、如图假定任选位置造桥11，连接，连接1和和1，从，从A到到B的路径是的路径是AM1+M1N1+BN1，那么怎样确定什么情况下，那么怎样确定什么情况下最最短短呢？呢？11absikao11A1NBAabM问题解决问

2、题解决BAA1MN如图，平移如图，平移A到到A1，使，使A1等于河宽，连接等于河宽，连接A1交交河岸于作桥，此时河岸于作桥，此时路径最路径最短短.理由；另任作桥理由；另任作桥，连接，连接，.由平移性质可知，由平移性质可知，.AM+MN+BN转化为转化为，而，而转转化为化为.在在中，由线段公理知中，由线段公理知A1N1+BN1A1B因此因此 AM+MN+BN作法：作法：1.1.将点将点B B沿垂直与河岸的方向平移一个河宽到沿垂直与河岸的方向平移一个河宽到E E，2.2.连接连接AEAE交河对岸与点交河对岸与点M,M,则点则点M M为建桥的位置，为建桥的位置，MNMN为所建的桥为所建的桥。证证明明

3、：由由平平移移的的性性质质，得得 BNEM BNEM 且且BN=EM,BN=EM,MN=CD,MN=CD,BDBDCE,CE,BD=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+

4、MNAC+CE+MNAE+MN,AE+MN,即即AC+CD+DB AC+CD+DB AM+MN+BNAM+MN+BN所以桥的位置建在所以桥的位置建在CDCD处，处，ABAB两地的路程最短。两地的路程最短。ABMNECD问题问题延伸一延伸一如图，如图，A和和B两地两地之间之间有两有两条河，现要在条河，现要在两两条条河上河上各各造一座桥造一座桥MN和和PQ.桥分别建桥分别建在何处在何处才能使从才能使从A到到B的路径的路径最短？（假定河的两最短？（假定河的两岸是平行的直线，桥岸是平行的直线，桥要与河要与河岸岸垂直）垂直）思维分析思维分析如图，问题中所走总路径是如图，问题中所走总路径是AM+MN+NP

5、+PQ+桥桥MN和和PQ在中间，且方向不在中间，且方向不能改变，仍无法直接利用能改变，仍无法直接利用“两两点之间，线段最短点之间，线段最短”解决问题，解决问题，只有利用平移变换转移到两侧只有利用平移变换转移到两侧或同一侧先走桥长或同一侧先走桥长.平移的方法有三种：两个桥长都平移平移的方法有三种：两个桥长都平移到到A点处、都平移到点处、都平移到B点处、点处、MN平移平移到到A点处，点处，PQ平移到平移到B点处点处思维方法一思维方法一 1、沿垂直于第一条河岸的方向平移、沿垂直于第一条河岸的方向平移A点至点至AA1使使AA1=MN，此时问题转化为问题基本题，此时问题转化为问题基本题型两点（型两点（A

6、1、B点）和一条河建桥（点）和一条河建桥（PQ）2、利用基本问题的解决方法确定桥、利用基本问题的解决方法确定桥PQ：（1）在沿垂直于第二条河岸的方向平移）在沿垂直于第二条河岸的方向平移A1至至A2，使使A1A2=PQ.（2）连接）连接A2B交交A2的对岸的对岸Q点，在点处建桥点，在点处建桥PQ.3、确定、确定PQ的位置，也确定了的位置，也确定了BQ和和PQ，此时问题可，此时问题可转化为由转化为由A点、点、P点和第一条河确定桥点和第一条河确定桥MN的位置的位置.连接连接A1P交的对岸于点，在点处建桥交的对岸于点，在点处建桥问题解决问题解决沿垂直于河岸方向依次把沿垂直于河岸方向依次把点、，使点、，

7、使，；连接交于点相邻连接交于点相邻河岸于点，建桥；河岸于点，建桥；连接交的对岸连接交的对岸于点，建桥；于点，建桥；从点到点的最短路径从点到点的最短路径为为MMN思维方法二思维方法二 沿垂直于第一条河岸方沿垂直于第一条河岸方向平移点至点，沿向平移点至点，沿垂直于第二条河岸方向平移垂直于第二条河岸方向平移点至点，连接点至点，连接A1B1 分别交分别交A、B的对岸于的对岸于N、P两点，建桥两点，建桥MN和和PQ.最短路径最短路径AM+MN+NP+PQ+QB转化为转化为AA1+A1B1+BB1.思维方法三思维方法三沿垂直于河岸方向依次把沿垂直于河岸方向依次把B点平移至点平移至B、B，使，使BBPQ，B

8、BMN；连接连接BA交于交于A点相邻河点相邻河岸于岸于M点，建桥点，建桥MN；连接连接BN交交B的对岸于的对岸于P点，建桥点，建桥PQ；从点到点的最短路径从点到点的最短路径为为MMNNP转化转化为为AB2+B2B1+B1B问题问题延伸二延伸二如图，如图，A和和B两地两地之间之间有三有三条河，现要在条河，现要在两两条条河上河上各各造一座桥造一座桥MN、PQ和和GH.桥分别建桥分别建在在何处才能使从何处才能使从A到到B的的路径最短？（假定河路径最短？（假定河的两岸是平行的直线，的两岸是平行的直线，桥要与河桥要与河岸岸垂直）垂直）思维分析思维分析如图，问题中所走总路径是如图，问题中所走总路径是AM+

9、MN+NP+PQ+G+GH+HB桥桥MN、PQ和和GH在中间，且方在中间，且方向不能改变，仍无法直接利用向不能改变，仍无法直接利用“两点之间，线段最短两点之间，线段最短”解决解决问题，只有利用平移变换转移问题，只有利用平移变换转移到两侧或同一侧先走桥长到两侧或同一侧先走桥长.平移的方法有四种：三个桥长都平移平移的方法有四种：三个桥长都平移到到A点处；都平移到点处；都平移到B点处；点处；MN、PQ平移到平移到A点处；点处；PQ、GH平移到平移到B点处点处问题解决问题解决沿垂直于河岸方向依次把沿垂直于河岸方向依次把A点平点平移至移至A、A、A3，使，使AAMN，AAPQ，A2A3=GH；连接连接A

10、3B交于交于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.此

11、时从此时从A到到B点路径最短点路径最短.问题解决问题解决沿垂直于河岸方向依次把沿垂直于河岸方向依次把A点平移点平移至至A，使，使AAMN，平移，平移B点至点至B1、B2,使使BB1GH，B1B2=PQ；连接连接A1B2交第一条河与交第一条河与A点相对河点相对河岸于岸于N点，交第二条河与点，交第二条河与N相邻河岸相邻河岸于于P点，建桥点，建桥MN、PQ；连接连接B1Q交第三条河与交第三条河与Q相邻河岸相邻河岸的的G点，建桥点，建桥GH；此时从此时从A到到B点路径最短点路径最短.问题解决问题解决沿垂直于河岸方向依次把沿垂直于河岸方向依次把A点平移点平移至至A、A2，使，使AAMN，平移，平移B点至

12、点至B1,使使BB1GH；连接连接AB交第三条河与点相对交第三条河与点相对河岸于点，交第二条河与相邻河岸于点，交第二条河与相邻河岸于点，建桥、河岸于点，建桥、PQ；连接连接1交第一条河与相邻河岸交第一条河与相邻河岸的点，建桥；的点，建桥；此时从此时从A到到B点路径最短点路径最短.问题解决问题解决延伸小结延伸小结同样，当、两点之间有、同样，当、两点之间有、，条河时，我们仍可以利用，条河时，我们仍可以利用平移转化桥长来解决问题平移转化桥长来解决问题 例如例如：沿垂直于河岸方向平移点依次至沿垂直于河岸方向平移点依次至、3，An,平移距离分平移距离分别等于各自河宽，别等于各自河宽，AnB交第交第n条河近条河近B点河岸于点河岸于Nn,建桥建桥MnNn,连接连接MnAn-1交第交第(n-1）条河近）条河近B点河岸与点河岸与Nn-1,建桥建桥Mn-1Nn-1，.，连接，连接M1A交第一条河近交第一条河近B点河岸于点河岸于N1，建桥，建桥M1N1,此时所走路径最短此时所走路径最短.BAM1N1AM1+M1N1+N1B