最短路径问题——造桥选址问题学习教案

1、会计学1最短路径最短路径(ljng)问题问题造桥选址问题造桥选址问题第一页，共11页。13.4 课题学习 最短路径(ljng)问题二玉溪玉溪(y x)中学中学 汪前进汪前进第1页/共11页第二页，共11页。问题问题2（造桥选址（造桥选址(xun zh)问题）如图，问题）如图，A和和B两地在一两地在一条河的两岸，现要在河上建一座桥条河的两岸，现要在河上建一座桥MN，桥造在何处才，桥造在何处才能使从能使从A到到B的路径的路径AMNB最短？（假设河的两岸是平最短？（假设河的两岸是平行的直线，桥要与河垂直）行的直线，桥要与河垂直）第2页/共11页第三页，共11页。问题(wnt)：1、直接连接AB可以吗

2、？2、路径是哪些(nxi)线段之和？3、当桥的位置变化后，路径中哪些(nxi)是始终不变的？哪些(nxi)在变？4、路径最短就是哪些(nxi)线段之和最小？5、路径可以转化为其它哪些(nxi)线段之和？L2L1MNABA1第3页/共11页第四页，共11页。问题问题(wnt)解决解决如图，平移如图，平移A沿与河岸垂沿与河岸垂直的方向到直的方向到A1，使，使A1等于等于(dngy)河宽，连河宽，连接接A1交河岸于点，交河岸于点，建桥，此时路径建桥，此时路径最短最短.理由理由(lyu)；另任作桥，连接，；另任作桥，连接，.由平移性质可知，由平移性质可知，.AM+MN+BN转化为转化为，而，而转化为转

3、化为.在在中，由线段公理知中，由线段公理知A1N1+BN1A1B因此因此 AM+MN+BNA1MNBA第4页/共11页第五页，共11页。问题问题(wnt)延伸延伸一一如图，如图，A和和B两地之间有两地之间有两条河，现要在两条河上两条河，现要在两条河上各造一座桥各造一座桥MN和和PQ.桥桥分别建在何处才能使从分别建在何处才能使从A到到B的路径最短？（假定的路径最短？（假定河的两岸是平行的直线河的两岸是平行的直线(zhxin)，桥要与河岸垂，桥要与河岸垂直）直）第5页/共11页第六页，共11页。问题问题(wnt)解决解决沿垂直于河岸沿垂直于河岸(h n)方向方向依次把点移到、依次把点移到、点移到，

4、使点移到，使，；连接交于点相邻连接交于点相邻河岸河岸(h n)于点，建桥于点，建桥；连接交的对岸连接交的对岸于点，建桥；于点，建桥；从点到点的最短路径从点到点的最短路径为为MMN第6页/共11页第七页，共11页。问题问题(wnt)延延伸二伸二如图，如图，A和和B两地之间有两地之间有三条河，现要在两条河上三条河，现要在两条河上(h shn)各造一座桥各造一座桥MN、PQ和和GH.桥分别建桥分别建在何处才能使从在何处才能使从A到到B的的路径最短？（假定河的两路径最短？（假定河的两岸是平行的直线，桥要与岸是平行的直线，桥要与河岸垂直）河岸垂直）第7页/共11页第八页，共11页。问题问题(wnt)解解

5、决决沿垂直于河岸方向依次把沿垂直于河岸方向依次把A点平移至点平移至A、A、A3，使，使AAMN，AAPQ，A2A3 =GH ；连接连接A3B交于交于B点相邻河岸于点相邻河岸于H点，建点，建桥桥GH；连接连接A2G交第二交第二(d r)河与河与G对岸的对岸的P点，建桥点，建桥PQ；连接连接A1P交第一条河与交第一条河与A的对岸于的对岸于N点，点，建桥建桥MN.此时从此时从A到到B点路径最短点路径最短.第8页/共11页第九页，共11页。延伸延伸(ynshn)小结小结同样，当、两点之间有、同样，当、两点之间有、，条河时，我们，条河时，我们(w men)仍可以仍可以利用平移转化桥长来解决问题利用平移转化桥长来解决问题 例如：例如： 沿垂直于河岸方向平移沿垂直于河岸方向平移(pn y)点依点依次至、次至、3，An,平移平移(pn y)距离分别等于各自河宽，距离分别等于各自河宽，AnB交第交第n条河近条河近B点点河岸于河岸于Nn,建桥建桥MnNn,连接连接MnAn-1交第交第(n-1）条河）条河近近B点河岸与点河岸与Nn-1,建桥建桥Mn-1Nn-1，.，连接，连接M1A交第一条河近交第一条河近B点河岸于点河岸于N1，建桥，建桥M1N1,此时所走此时所走路径最短路径最短.第9页/