最短路径问题公开课精.ppt

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

1、最短路径问题公开课第1页，本讲稿共25页AB .将军骑马从将军骑马从城堡城堡A A出发，到一条出发，到一条笔直的小河笔直的小河边边 饮马，然后到饮马，然后到军营军营B B。将军问：到河边的。将军问：到河边的什什么地方么地方饮马可使他所走的饮马可使他所走的路径最短路径最短？将军饮马问题将军饮马问题：第2页，本讲稿共25页AC问题一：问题一：将军骑马从城堡将军骑马从城堡A A出发，出发，到一到一条笔直的小河边条笔直的小河边 饮马饮马 。问：在河边的。问：在河边的什么位置什么位置饮马饮马,将军所走的路径最短？将军所走的路径最短？问题一：问题一：在直线在直线 上找一点上找一点C C，使，使ACAC最短

2、？最短？直线外直线外一点一点与与直线直线上所有点的连线中上所有点的连线中，垂线，垂线段最短段最短第3页，本讲稿共25页AB两点两点之间线段最短之间线段最短问题二：问题二：将军骑马从将军骑马从城堡城堡A A出发，到出发，到军营军营B B去，去，途途中经过一条中经过一条笔直的小河笔直的小河 。将军问：在小河的将军问：在小河的什么地方什么地方饮马可使他所走的饮马可使他所走的路径最短路径最短？问题二：问题二：在直线在直线 上找一点上找一点C C，使，使CA+CBCA+CB最小最小？C第4页，本讲稿共25页 .将军骑马从将军骑马从城堡城堡A A出发，到一条出发，到一条笔直的小河边笔直的小河边 饮马，然后

3、到饮马，然后到军营军营B B。将军问：到河边的。将军问：到河边的什么地方什么地方饮饮马可使他所走的马可使他所走的路径最短路径最短？ABAC探究一：将军饮马问题探究一：将军饮马问题 第5页，本讲稿共25页巩固训练：已知：巩固训练：已知：P P、Q Q是是ABCABC的边的边ABAB、ACAC 上的点，你能在上的点，你能在BCBC上确定一点上确定一点R R，使使PQRPQR的周长最短吗？的周长最短吗？你学会了吗？你学会了吗？第6页，本讲稿共25页草地草地河边河边城堡城堡 如图：一位将军骑马从城堡如图：一位将军骑马从城堡A A出发，先骑马去出发，先骑马去草地边草地边OMOM的的某处吃草，再骑马去某处

4、吃草，再骑马去河边河边ONON喝水，最后回到城堡喝水，最后回到城堡A A，问：这位将军怎样走路程最短？问：这位将军怎样走路程最短？OMN探究二：将军饮马问题探究二：将军饮马问题数学问题：在射线数学问题：在射线OM、ON上分别找一点上分别找一点P、Q，使，使AP+PQ+QA最短最短A第7页，本讲稿共25页能力训练能力训练：已知已知P P是是BACBAC的边的边A AB B上的点，上的点，你能在你能在ACAC、ABAB上分别确定一点上分别确定一点Q Q和和R R，使使 PQPQ+Q+QR R 最短吗？最短吗？ACPB第8页，本讲稿共25页第9页，本讲稿共25页造桥选址问题造桥选址问题如图，如图，A

5、和和B两地在一条河的两岸，现要在河上造两地在一条河的两岸，现要在河上造一座桥一座桥MN.乔早在何处才能使从乔早在何处才能使从A到到B的路径的路径AMNB最短？（假定河的两岸是平行的直线，桥最短？（假定河的两岸是平行的直线，桥要与河垂直）要与河垂直）BA第10页，本讲稿共25页思维分析思维分析BA 1、如图假定任选位置造、如图假定任选位置造桥，连接和，桥，连接和，从从A到到B的路径是的路径是AM+MN+BN，那么怎样确，那么怎样确定什么情况下最短呢？定什么情况下最短呢？2、利用线段公理解决问题我们遇到、利用线段公理解决问题我们遇到了什么障碍呢？了什么障碍呢？第11页，本讲稿共25页问题解决问题解

6、决BAA1MN如图，平移如图，平移A到到A1，使，使A1等于河宽，连接等于河宽，连接A1交河岸交河岸于作桥，此时路径于作桥，此时路径最短最短.理由；另任作桥理由；另任作桥，连接，连接，.由平移性质可知，由平移性质可知，.AM+MN+BN转化为转化为，而，而转化为转化为.在在中，由线段公理知中，由线段公理知A1N1+BN1A1B因此因此 AM+MN+BN第12页，本讲稿共25页问题延伸一问题延伸一如图，如图，A和和B两地之间有两地之间有两条河，现要在两条河两条河，现要在两条河上各造一座桥上各造一座桥MN和和PQ.桥分别建在何处才能使桥分别建在何处才能使从从A到到B的路径最短？的路径最短？（假定河

7、的两岸是平行（假定河的两岸是平行的直线，桥要与河岸垂的直线，桥要与河岸垂直）直）第13页，本讲稿共25页思维分析思维分析如图，问题中所走总路径是如图，问题中所走总路径是AM+MN+NP+PQ+桥桥MN和和PQ在中间，且方向不能在中间，且方向不能改变，仍无法直接利用改变，仍无法直接利用“两点之两点之间，线段最短间，线段最短”解决问题，只有解决问题，只有利用平移变换转移到两侧或同一利用平移变换转移到两侧或同一侧先走桥长侧先走桥长.平移的方法有三种：两个桥长都平移到平移的方法有三种：两个桥长都平移到A点点处、都平移到处、都平移到B点处、点处、MN平移到平移到A点处，点处，PQ平移到平移到B点处点处第

8、14页，本讲稿共25页思维方法一思维方法一 1、沿垂直于第一条河岸的方向平移、沿垂直于第一条河岸的方向平移A点至点至AA1使使AA1=MN，此时问题转化为问题基本题型，此时问题转化为问题基本题型两点（两点（A1、B点）和一条河建桥（点）和一条河建桥（PQ）第15页，本讲稿共25页2、利用基本问题的解决方法确定桥、利用基本问题的解决方法确定桥PQ：（1）在沿垂直于第二条河岸的方向平移）在沿垂直于第二条河岸的方向平移A1至至A2，使使A1A2=PQ.（2）连接）连接A2B交交A2的对岸的对岸Q点，在点处建桥点，在点处建桥PQ.第16页，本讲稿共25页3、确定、确定PQ的位置，也确定了的位置，也确定

9、了BQ和和PQ，此时问题可，此时问题可转化为由转化为由A点、点、P点和第一条河确定桥点和第一条河确定桥MN的位置的位置.连接连接A1P交的对岸于点，在点处建桥交的对岸于点，在点处建桥第17页，本讲稿共25页问题解决问题解决沿垂直于河岸方向依次把沿垂直于河岸方向依次把点、，使点、，使，；，；连接交于点相邻连接交于点相邻河岸于点，建桥；河岸于点，建桥；连接交的对岸于连接交的对岸于点，建桥；点，建桥；从点到点的最短路径从点到点的最短路径为为MMN第18页，本讲稿共25页思维方法二思维方法二 沿垂直于第一条河岸方沿垂直于第一条河岸方向平移点至点，沿向平移点至点，沿垂直于第二条河岸方向平移垂直于第二条河

10、岸方向平移点至点，连接点至点，连接A1B1 分别交分别交A、B的对岸于的对岸于N、P两点，建桥两点，建桥MN和和PQ.最短路径最短路径AM+MN+NP+PQ+QB转转化为化为AA1+A1B1+BB1.第19页，本讲稿共25页思维方法三思维方法三沿垂直于河岸方向依次把沿垂直于河岸方向依次把B点平移至点平移至B、B，使，使BBPQ，BBMN；连接连接BA交于交于A点相邻河岸点相邻河岸于于M点，建桥点，建桥MN；连接连接BN交交B的对岸于的对岸于P点，点，建桥建桥PQ；从点到点的最短路径为从点到点的最短路径为MMNNP转化为转化为AB2+B2B1+B1B第20页，本讲稿共25页问题延伸二问题延伸二如

11、图，如图，A和和B两地之间有两地之间有三条河，现要在两条河三条河，现要在两条河上各造一座桥上各造一座桥MN、PQ和和GH.桥分别建在何处桥分别建在何处才能使从才能使从A到到B的路径最的路径最短？（假定河的两岸是短？（假定河的两岸是平行的直线，桥要与河平行的直线，桥要与河岸垂直）岸垂直）第21页，本讲稿共25页思维分析思维分析如图，问题中所走总路径是如图，问题中所走总路径是AM+MN+NP+PQ+G+GH+HB桥桥MN、PQ和和GH在中间，且方向在中间，且方向不能改变，仍无法直接利用不能改变，仍无法直接利用“两点两点之间，线段最短之间，线段最短”解决问题，只有解决问题，只有利用平移变换转移到两侧

12、或同一侧利用平移变换转移到两侧或同一侧先走桥长先走桥长.平移的方法有四种：三个桥长都平移到平移的方法有四种：三个桥长都平移到A点处；都平移到点处；都平移到B点处；点处；MN、PQ平平移到移到A点处；点处；PQ、GH平移到平移到B点处点处第22页，本讲稿共25页问题解决问题解决沿垂直于河岸方向依次把沿垂直于河岸方向依次把A点平移至点平移至A、A、A3，使，使AAMN，AAPQ，A2A3=GH；连接连接A3B交于交于B点相邻河岸于点相邻河岸于H点，建点，建桥桥GH；连接连接A2G交第二河与交第二河与G对岸的对岸的P点，点，建桥建桥PQ；连接连接A1P交第一条河与交第一条河与A的对岸于的对岸于N点，

13、建桥点，建桥MN.此时从此时从A到到B点路径最短点路径最短.第23页，本讲稿共25页沿垂直于河岸方向依次把沿垂直于河岸方向依次把A点点平移至平移至A、A、A3，使，使AAMN，AAPQ，A2A3=GH；连接连接A3B交于交于B点相邻河岸于点相邻河岸于H点，建桥点，建桥GH；连接连接A2G交第二河与交第二河与G对岸对岸的的P点，建桥点，建桥PQ；连接连接A1P交第一条河与交第一条河与A的对岸的对岸于于N点，建桥点，建桥MN.此时从此时从A到到B点路径最短点路径最短.问题解决问题解决第24页，本讲稿共25页沿垂直于河岸方向依次把沿垂直于河岸方向依次把A点平移点平移至至A，使，使AAMN，平移，平移B点点至至B1、B2,使使BB1GH，B1B2=PQ；连接连接A1B2交第一条河与交第一条河与A点相对点相对河岸于河岸于N点，交第二条河与点，交第二条河与N相相邻河岸于邻河岸于P点，建桥点，建桥MN、PQ；连接连接B1Q交第三条河与交第三条河与Q相邻河岸相邻河岸的的G点，建桥点，建桥GH；此时从此时从A到到B点路径最短点路径最短.问题解决问题解决第25页，本讲稿共25页