最短路径.pptx

最短路径最短路径问题问题1如图，牧马人从A地出发，到一条笔直的河边l饮马，然后到B地.牧马人到河边的什么地方饮马，可使所走的路径最短？两种情形解决问题1问题2（造桥选址问题）如图，A和B两地在一条河的两岸，现要在河上造一座桥MN，桥造在何处可使从A到B的路径AMNB最短？（假定河的两岸是平行的直线，桥要与河垂直。）解决问题2练习1、如图1，台球桌上有一个黑球，一个白球，如何用球杆去击白球使其撞到AB边反弹后再撞到黑球?2、如图2，四边形ABCD中，∠BAD=120°，∠B=∠D=90°,在BC，CD上分别找一点M、N，当△AMN周长最小时，∠AMN+∠ANM的度数为多少？郧西县河夹镇初级中学造桥选址问题思维分析上述方法都能做到使AM+MN+BN不变呢？请检验.问题解决问题延伸一思维分析思维方法一2、利用基本问题的解决方法确定桥PQ：（1）在沿垂直于第二条河岸的方向平移A1至A2，使A1A2=PQ.（2）连接A2B交A2的对岸Q点，在点处建桥PQ.3、确定PQ的位置，也确定了BQ和PQ，此时问题可转化为由A点、P点和第一条河确定桥MN的位置.问题解决思维方法二思维方法三问题延伸二思维分析问题解决沿垂直于河岸方向依次把A点平移至A１、A２、A3，使AA１＝MN，A１A２＝PQ，A2A3=GH；连接A3B交于B点相邻河岸于H点，建桥GH；连接A2G交第二河与G对岸的P点，建桥PQ；连接A1P交第一条河与A的对岸于N点，建桥MN.此时从A到B点路径最短.沿垂直于河岸方向依次把A点平移至A１，使AA１＝MN，平移B点至B1、B2,使BB1＝GH，B1B2=PQ；连接A1B2交第一条河与A点相对河岸于N点，交第二条河与N相邻河岸于P点，建桥MN、PQ；连接B1Q交第三条河与Q相邻河岸的G点，建桥GH；此时从A到B点路径最短.沿垂直于河岸方向依次把A点平移至A１、A2，使AA１＝MN，Ａ１Ａ２＝ＰＱ，平移B点至B1,使BB1＝GH；连接A２B１交第三条河与Ｂ点相对河岸于Ｇ点，交第二条河与Ｇ相邻河岸于Ｑ点，建桥ＧＨ、PQ；连接Ａ1Ｐ交第一条河与Ｐ相邻河岸的Ｎ点，建桥ＭＮ；此时从A到B点路径最短.