短路徑問題--公開課.ppt

1、,授課人：張春濤,13.4 最短路徑問題,A,B,. 將軍騎馬從城堡A出發(fā)，到一條筆直的小河邊 飲馬，然后到軍營B。將軍問：到河邊的什么地方飲馬可使他所走的路徑最短？,將軍飲馬問題 ：,A,C,問題一：將軍騎馬從城堡A出發(fā)， 到一條筆直的小河邊 飲馬 。問：在河邊的什么位置飲馬,將軍所走的路徑最短？,問題一：在直線 上找一點C，使AC最短？,直線外一點與直線上所有點的連線中，垂線段最短,A,B,兩點之間線段最短,問題二：將軍騎馬從城堡A出發(fā)，到軍營B去，途中經(jīng)過一條筆直的小河 。 將軍問：在小河的什么地方飲馬可使他所走的路徑最短？,問題二：在直線 上找一點C，使CA+CB最小 ？,C,. 將軍

2、騎馬從城堡A出發(fā)，到一條筆直的小河邊 飲馬，然后到軍營B。將軍問：到河邊的什么地方飲馬可使他所走的路徑最短？,A,B,A,C,探究一：將軍飲馬問題,鞏固訓練：已知：P、Q是ABC的邊AB、AC 上的點，你能在BC上確定一點R， 使PQR的周長最短嗎？,你學會了嗎？,如圖：一位將軍騎馬從城堡A出發(fā)，先騎馬去草地邊OM的某處吃草，再騎馬去河邊ON喝水，最后回到城堡A， 問：這位將軍怎樣走路程最短？,O,M,N,探究二：將軍飲馬問題,數(shù)學問題：在射線OM、ON上分別找一點 P、Q，使AP+PQ+QA最短,A,能力訓練： 已知P是BAC的邊AB上的點， 你能在AC、AB上分別確定一點Q和R， 使 PQ

3、+QR 最短嗎？,A,C,P,B,造橋選址問題的延伸探索,造橋選址問題,如圖，A和B兩地在一條河的兩岸，現(xiàn)要在河上造一座橋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兩地之間有兩條河，現(xiàn)要在兩條河上各造一座橋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兩地之間有三條河，現(xiàn)要在兩條河上各造一座橋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點路徑最短.,問題解決,沿