第一篇：八年級(jí)數(shù)學(xué)最短路徑問(wèn)題

八年級(jí)數(shù)學(xué)最短路徑問(wèn)題

一、兩點(diǎn)在一條直線(xiàn)異側(cè)

例：已知：如圖，A，B在直線(xiàn)L的兩側(cè)，在L上求一點(diǎn)P，使得PA+PB最小。

練習(xí)、如圖，A.B兩地在一條河的兩岸，現(xiàn)要在河上建一座橋MN，橋造在何處才能使從A到B的路徑AMNB最短？（假設(shè)河的兩岸是平行的直線(xiàn)，橋要與河垂直）

二、兩點(diǎn)在一條直線(xiàn)同側(cè)

例：圖所示，要在街道旁修建一個(gè)奶站，向居民區(qū)A、B提供牛奶，奶站應(yīng)建在什么地方，才能使從A、B到它的距離之和最短．

練習(xí)：如圖，A、B是兩個(gè)蓄水池，都在河流a的同側(cè)，為了方便灌溉作物，?要在河邊建一個(gè)抽水站，將河水送到A、B兩地，問(wèn)該站建在河邊什么地方，?可使所修的渠道最短，試在圖中確定該點(diǎn)。三、一點(diǎn)在兩相交直線(xiàn)內(nèi)部

例：已知：如圖A是銳角∠MON內(nèi)部任意一點(diǎn)，在∠MON的兩邊OM，ON上各取一點(diǎn)B，C，組成三角形ABC，使三角形周長(zhǎng)最小.練習(xí)1：已知：如圖A是銳角∠MON內(nèi)部任意一點(diǎn)，在∠MON的兩邊OM，ON上各取一點(diǎn)B，C，組成三角形ABC周長(zhǎng)最小值為OA.求∠MON的度數(shù)。

練習(xí)2：某班舉行晚會(huì)，桌子擺成兩直條(如圖中的AO，BO)，AO桌面上擺滿(mǎn)了桔子，OB桌面上擺滿(mǎn)了糖果，坐在C處的學(xué)生小明先拿桔子再拿糖果，然后回到座位，請(qǐng)你幫助他設(shè)計(jì)一條行走路線(xiàn)，使其所走的總路程最短？

提高訓(xùn)練

一、題中出現(xiàn)一個(gè)動(dòng)點(diǎn)。

1.當(dāng)題中只出現(xiàn)一個(gè)動(dòng)點(diǎn)時(shí),可作定點(diǎn)關(guān)于動(dòng)點(diǎn)所在直線(xiàn)的對(duì)稱(chēng)點(diǎn),利用兩點(diǎn)之間線(xiàn)段最短,或三角形兩邊之和小于第三邊求出最值.例：如圖，在正方形ABCD中，點(diǎn)E為AB上一定點(diǎn)，且BE=10,CE=14,P為BD上一動(dòng)點(diǎn)，求PE+PC最小值。

二、題中出現(xiàn)兩個(gè)動(dòng)點(diǎn)。當(dāng)題中出現(xiàn)兩個(gè)定點(diǎn)和兩個(gè)動(dòng)點(diǎn)時(shí),應(yīng)作兩次定點(diǎn)關(guān)于動(dòng)點(diǎn)所在直線(xiàn)的對(duì)稱(chēng)點(diǎn).利用兩點(diǎn)之間線(xiàn)段最短求出最值。

例：如圖，在直角坐標(biāo)系中有四個(gè)點(diǎn), A(-8,3),B(-4,5)C(0，n),D(m,0),當(dāng)四邊形ABCD周長(zhǎng)最短時(shí),求 C、D的坐標(biāo)。

練習(xí)1如圖，∠AOB=30°，點(diǎn)M、N分別在邊OA、OB上，且OM=1，ON=3，點(diǎn)P、Q分別在邊OB、OA上，則MP+PQ+QN的最小值是

．

三、題中出現(xiàn)三個(gè)動(dòng)點(diǎn)時(shí)。

在求解時(shí)應(yīng)注意兩點(diǎn)：(1)作定點(diǎn)關(guān)于動(dòng)點(diǎn)所在直線(xiàn)的對(duì)稱(chēng)點(diǎn),(2)同時(shí)要考慮點(diǎn)點(diǎn),點(diǎn)線(xiàn),線(xiàn)線(xiàn)之間的最短問(wèn)題.例：如圖，在菱形ABCD中,AB=2,∠BAD=60°,E,F,P分別為AB,BC,AC上動(dòng)點(diǎn), 求PE+PF最小值 例：如圖，∠AOB=45°，角內(nèi)有一動(dòng)點(diǎn)P，PO=10，在AO，BO上有兩動(dòng)點(diǎn)Q，R，求△PQR周長(zhǎng)的最小值。

練習(xí)1如圖，∠AOB=30°，角內(nèi)有一定點(diǎn)P，PO=20cm，在AO，BO上有兩動(dòng)點(diǎn)C、D，求△PCD周長(zhǎng)的最小值。

第二篇：最短路徑教案

13.4最短路徑問(wèn)題

一、教學(xué)內(nèi)容：本節(jié)課的主要內(nèi)容是利用軸對(duì)稱(chēng)研究某些最短路徑問(wèn)題，最短路徑問(wèn)題在現(xiàn)實(shí)生活中經(jīng)常遇到，初中階段，主要以“兩點(diǎn)之間，線(xiàn)段最短”“連接直線(xiàn)外一點(diǎn)與直線(xiàn)上各點(diǎn)的所有連線(xiàn)中，垂線(xiàn)段最短”為知識(shí)基礎(chǔ)，有時(shí)還要借助軸對(duì)稱(chēng)、平移、旋轉(zhuǎn)等變換進(jìn)行研究。

本節(jié)課以數(shù)學(xué)史中的一個(gè)經(jīng)典故事----“將軍飲馬問(wèn)題”為載體開(kāi)展對(duì)“最短路徑問(wèn)題”的課題研究，讓學(xué)生經(jīng)歷將實(shí)際問(wèn)題抽象為數(shù)學(xué)的線(xiàn)段和最小問(wèn)題，再利用軸對(duì)稱(chēng)將線(xiàn)段和最小問(wèn)題轉(zhuǎn)化為“兩點(diǎn)之間、線(xiàn)段最短”的問(wèn)題。

二、教學(xué)目標(biāo)

1、能利用軸對(duì)稱(chēng)解決簡(jiǎn)單的最短路徑問(wèn)題

2、再談歲最短路徑的過(guò)程中，體會(huì)“軸對(duì)稱(chēng)”的橋梁作用，感悟轉(zhuǎn)化的數(shù)學(xué)思想。

三、教學(xué)重難點(diǎn)

重點(diǎn)：利用軸對(duì)稱(chēng)將最短路徑問(wèn)題轉(zhuǎn)化為“兩點(diǎn)之間、線(xiàn)段最短”問(wèn)題。難點(diǎn)：如何利用軸對(duì)稱(chēng)將最短路徑問(wèn)題轉(zhuǎn)化為線(xiàn)段和最小問(wèn)題。

四、教學(xué)問(wèn)題診斷

最短路徑問(wèn)題從本質(zhì)上說(shuō)是最值問(wèn)題，作為初中學(xué)生，在此前很少涉及最值問(wèn)題，解決這方面問(wèn)題的數(shù)學(xué)經(jīng)驗(yàn)尚顯不足，特別是面對(duì)具有實(shí)際背景的最值問(wèn)題，更會(huì)感到陌生，無(wú)從下手。

解答“當(dāng)點(diǎn)AB在直線(xiàn)l的同側(cè)時(shí)，如何在l上找到點(diǎn)C，使AC與BC的和最小”，需要將其轉(zhuǎn)化為“直線(xiàn)l異側(cè)的兩點(diǎn)，與直線(xiàn)l上的點(diǎn)的線(xiàn)段的和最小”的問(wèn)題，為什么需要這樣轉(zhuǎn)化，怎樣通過(guò)軸對(duì)稱(chēng)實(shí)現(xiàn)轉(zhuǎn)化，一些學(xué)生會(huì)存在理解上和操作上的困難。

在證明“最短”時(shí)，需要在直線(xiàn)上任取一點(diǎn)（與所求做的點(diǎn)不重合），證明所連線(xiàn)段和大于所求作的線(xiàn)段和，這種思路和方法，一些學(xué)生想不到。

教學(xué)時(shí)，教師可以讓學(xué)生首先思考“直線(xiàn)l異側(cè)的兩點(diǎn)，與直線(xiàn)l上的點(diǎn)的和最小”為學(xué)生搭建“腳手架”，在證明最短時(shí)，教師要適時(shí)點(diǎn)撥學(xué)生，讓學(xué)生體會(huì)任意的作用。

五、教學(xué)過(guò)程

教師引語(yǔ)：現(xiàn)實(shí)生活中經(jīng)常會(huì)有這樣的生活經(jīng)歷，比如學(xué)校雖然為我們鋪設(shè)了一些石板甬路，方便同學(xué)們的行走，但是很多時(shí)候我們卻并不在這些小路上行走，這樣做的目的是什么呢？（學(xué)生一起回答）如果用數(shù)學(xué)知識(shí)來(lái)解釋這種行為，那就是我們?cè)?jīng)學(xué)習(xí)的“兩點(diǎn)之間、線(xiàn)段最短”或“垂線(xiàn)段最短”，我們稱(chēng)這樣的問(wèn)題為最短路徑問(wèn)題（板書(shū)課題）現(xiàn)實(shí)生活中經(jīng)常涉及到最短路徑問(wèn)題，這節(jié)課我們學(xué)習(xí)的主要任務(wù)就是最短路徑問(wèn)題，并用所學(xué)知識(shí)探究數(shù)學(xué)史上著名的“將軍飲馬問(wèn)題”。

1、情境引入

相傳，古希臘亞歷山大里亞城里有一位久負(fù)盛名的學(xué)者，名叫海倫，有一天，有一位將軍專(zhuān)門(mén)拜訪(fǎng)海倫，求教一個(gè)百思不得其解的問(wèn)題：從圖中的A地出發(fā)，到一條筆直的河邊飲馬，然后到B地，到河邊什么地方飲馬，可使他所走的路線(xiàn)全程最短？精通數(shù)學(xué)、物理學(xué)的海倫稍加思索，利用軸對(duì)稱(chēng)的知識(shí)回答了這個(gè)問(wèn)題。這個(gè)問(wèn)題后來(lái)被稱(chēng)為“將軍飲馬問(wèn)題”。

2、探究解決問(wèn)題的方法

問(wèn)題一：這是一個(gè)實(shí)際問(wèn)題，我們首先把它抽象為數(shù)學(xué)問(wèn)題，請(qǐng)同學(xué)們用自己的語(yǔ)言說(shuō)明這個(gè)問(wèn)題的意思。

師生活動(dòng)：學(xué)生獨(dú)立思考后小組交換意見(jiàn)，然后嘗試回答，相互補(bǔ)充，最后達(dá)成共識(shí)，教師根據(jù)學(xué)生的回答寫(xiě)出問(wèn)題的板書(shū)：如圖，已知點(diǎn)A和點(diǎn)B在直線(xiàn)L的同側(cè)，在直線(xiàn)L上找一點(diǎn)C，使AC與BC的和最小。

設(shè)計(jì)意圖：讓學(xué)生將實(shí)際問(wèn)題抽象為數(shù)學(xué)問(wèn)題，即將最短路徑問(wèn)題抽象為“線(xiàn)段和最小問(wèn)題”。

問(wèn)題二：由上面的問(wèn)題我們可以聯(lián)想到下面的問(wèn)題：A、B分別是直線(xiàn)L異側(cè)的兩點(diǎn)，如何在直線(xiàn)L上找到一點(diǎn)C，使AC與BC的和最??？

師生活動(dòng)：學(xué)生獨(dú)立思考，畫(huà)圖分析并嘗試回答，教師補(bǔ)充。

問(wèn)題三：對(duì)于第一個(gè)問(wèn)題，如何將點(diǎn)B移到L的另一側(cè)，B′處，滿(mǎn)足直線(xiàn)L上的任一點(diǎn)C，都保持CB與CB′的長(zhǎng)度相等？ 問(wèn)題四：你能利用軸對(duì)稱(chēng)的知識(shí)找到符合條件的點(diǎn)B′嗎？

師生活動(dòng)：學(xué)生獨(dú)立考，嘗試畫(huà)圖，然后小組交流，學(xué)生代表匯報(bào)交流成果，師生共同補(bǔ)充：只要作出點(diǎn)B關(guān)于直線(xiàn)L的對(duì)稱(chēng)點(diǎn)B′，就可以滿(mǎn)足CB=CB′,再利用問(wèn)題二中的方法，連接AB′,則AB′與直線(xiàn)L的交點(diǎn)即為所求。

學(xué)生敘述，教師板書(shū)并畫(huà)圖，同時(shí)學(xué)生在練習(xí)本上畫(huà)圖。

設(shè)計(jì)意圖：通過(guò)搭建臺(tái)階，為學(xué)生探究問(wèn)題提供“腳手架”將同側(cè)難以解決的問(wèn)題提轉(zhuǎn)化為異側(cè)容易解決的問(wèn)題，滲透轉(zhuǎn)化思想。

3、推理證明“最短”

問(wèn)題五：你能用所學(xué)的知識(shí)證明AC+BC最短嗎？

師生活動(dòng)：師生共同分析，然后學(xué)生說(shuō)證明過(guò)程，教師板書(shū)。

證明：在直線(xiàn)L上任取一點(diǎn)C′（與點(diǎn)C不重合），連接AC′,BC′,B′C′.由軸對(duì)稱(chēng)的性質(zhì)可知，BC=B′C,BC′=B′C′.∴AC+BC=AC+ B′C=AB′, AC′+ BC′= AC′+ B′C′

在△AB′C′中，AB′＜AC′+ B′C′

∴AC+BC＜ AC′+ BC′ 即AC+BC最短。

問(wèn)題六：這里任取一點(diǎn)C′的作用是什么？

師生活動(dòng)：學(xué)生相互交流，教師適時(shí)點(diǎn)撥，最后達(dá)成共識(shí)：若直線(xiàn)L上任取一點(diǎn)C′與A、B兩點(diǎn)的距離之和都大于AC+BC，則說(shuō)明AC+BC最短。

設(shè)計(jì)意圖：讓學(xué)生進(jìn)一步體會(huì)做法的正確性，提高邏輯思維能力。

問(wèn)題七：回顧前面的探究過(guò)程，我們是通過(guò)怎樣的過(guò)程、借助什么解決問(wèn)題的？

師生共同總結(jié)：首先作其中一點(diǎn)關(guān)于直線(xiàn)的對(duì)稱(chēng)點(diǎn)，然后連接另一點(diǎn)與對(duì)稱(chēng)點(diǎn)之間的線(xiàn)段，通過(guò)軸對(duì)稱(chēng)將兩條線(xiàn)段和轉(zhuǎn)化到同一條線(xiàn)段上去，這條線(xiàn)段與直線(xiàn)的交點(diǎn)即為所求，整個(gè)過(guò)程利用了“軸對(duì)稱(chēng)”和“兩點(diǎn)之間、線(xiàn)段最短“的知識(shí)。

設(shè)計(jì)意圖：讓學(xué)生在反思的過(guò)程中，體會(huì)軸對(duì)稱(chēng)的“橋梁”作用，感悟轉(zhuǎn)化思想，豐富數(shù)學(xué)活動(dòng)經(jīng)驗(yàn)。

4、鞏固練習(xí)

（1）如圖，一艘旅游船從大橋AB的P處前往山腳下的Q處接游客，然后將游客送往河岸BC上，再回到P處，請(qǐng)畫(huà)出旅游船的最短路徑。

師生活動(dòng)：學(xué)生分析解題思路，并相互補(bǔ)充，然后獨(dú)立完成畫(huà)圖，學(xué)生代表上臺(tái)講解?；舅悸贩治觯捍祟}中輪船的行走路線(xiàn)共有三段，其中PQ是必經(jīng)路段，由“兩點(diǎn)之間，線(xiàn)段最短”需首先連接PQ，再將河岸BC看成一條直線(xiàn)，這樣問(wèn)題就轉(zhuǎn)化為“點(diǎn)P、Q在直線(xiàn)BC同側(cè)，如何在BC上找一點(diǎn)R，使PR+QR最小”。

設(shè)計(jì)意圖：讓學(xué)生進(jìn)一步鞏固解決最短路徑問(wèn)題的基本策略和基本方法。

（2）如圖，∠XOY內(nèi)有一點(diǎn)P，在射線(xiàn)OX上找出一點(diǎn)M，在射線(xiàn)OY上找出一點(diǎn)N，使PM+MN+NP最短．

分析：此題的出題背景就是角。本題主要利用了兩點(diǎn)之間線(xiàn)段最短的性質(zhì)通過(guò)軸對(duì)稱(chēng)圖形的性質(zhì)確定三角形的另兩點(diǎn)．

分別以直線(xiàn)OX、OY為對(duì)稱(chēng)軸，作點(diǎn)P的對(duì)應(yīng)點(diǎn)P1與P2，連接P1P2交OX于M，交OY于N，則PM+MN+NP最短．

5、課堂小結(jié)：教師與學(xué)生一起回顧本節(jié)課所學(xué)主要內(nèi)容，并請(qǐng)學(xué)生回答：（1）本節(jié)課研究問(wèn)題的基本過(guò)程是什么？（2）軸對(duì)稱(chēng)在所研究的問(wèn)題中起到什么作用？

6、布置作業(yè)：《課時(shí)練》第49頁(yè)1、2、3、4、5、7、8、9

第三篇：ArcGIS網(wǎng)絡(luò)分析(最短路徑問(wèn)題分析)

網(wǎng)絡(luò)分析（最短路徑問(wèn)題分析）

一、實(shí)驗(yàn)?zāi)康模?/p>

理解最短路徑分析的基本原理，學(xué)習(xí)利用arcgis軟件進(jìn)行各種類(lèi)型的最短路徑分析的操作。

二、實(shí)驗(yàn)準(zhǔn)備

1、實(shí)驗(yàn)背景：

最短路徑分析是空間網(wǎng)絡(luò)分析中最基本的應(yīng)用，而交通網(wǎng)絡(luò)中要素的設(shè)置對(duì)最短路徑的選擇有著很大的影響。實(shí)驗(yàn)要求根據(jù)不同的權(quán)重，給出到達(dá)指定目的地的路徑選擇方案，并給出路徑長(zhǎng)度。

? 在網(wǎng)絡(luò)中指定一個(gè)超市，要求分別求出在距離、時(shí)間限制上從家到超市的最佳路徑。

? 給定訪(fǎng)問(wèn)順序，按要求找出從家經(jīng)逐個(gè)地點(diǎn)達(dá)到目的地的最佳路徑。

2、實(shí)驗(yàn)材料：

軟件：ArcGIS Desktop 9.x，實(shí)驗(yàn)數(shù)據(jù)：文件夾ex6中，一個(gè)GeoDatabase地理數(shù)據(jù)庫(kù)：City.mdb，內(nèi)含有城市交通網(wǎng)、超市分布圖，家庭住址以及網(wǎng)絡(luò)關(guān)系。

三、實(shí)驗(yàn)內(nèi)容及步驟

首先啟動(dòng)ArcMap，選擇ex6city.mdb，再雙擊后選擇將整個(gè)要素?cái)?shù)據(jù)集“city”加載進(jìn)來(lái)，然后將“place”點(diǎn)狀要素以“HOME”字段屬性值進(jìn)行符號(hào)化，1值是家，0值是超市。

第1步 無(wú)權(quán)重最佳路徑的選擇 ? 加載 “設(shè)施網(wǎng)絡(luò)分析”工具條（“視圖”>>“工具條”，勾選“設(shè)施網(wǎng)絡(luò)分析”），點(diǎn)選旗標(biāo)和障礙工具板下拉箭頭，將旗標(biāo)放在家和想要去的超市點(diǎn)上。

第2步 加權(quán)最佳路徑選擇

? 在設(shè)施網(wǎng)絡(luò)分析工具條上，點(diǎn)選旗標(biāo)和障礙工具板下拉箭頭，將旗標(biāo)放在家和想去的某個(gè)超市點(diǎn)上。

? 選擇“分析”下拉菜單，選擇“選項(xiàng)”按鈕，打開(kāi)“分析選項(xiàng)”對(duì)話(huà)框，選擇“權(quán)重”標(biāo)簽頁(yè)，在“邊權(quán)重”上，全部選擇長(zhǎng)度“l(fā)ength”權(quán)重屬性。? 點(diǎn)選“追蹤任務(wù)”下拉菜單選擇“查找路徑”。單擊“執(zhí)行”鍵，則以長(zhǎng)度為比重為基礎(chǔ)的最短路徑將顯示出來(lái)，這條路徑的總成本將顯示在狀態(tài)列。

?? 上述是通過(guò)距離的遠(yuǎn)近選擇而得到的最佳路徑，而不同類(lèi)型的道路由于道路車(chē)流量的問(wèn)題，有時(shí)候要選擇時(shí)間較短的路徑，同樣可以利用網(wǎng)絡(luò)分析進(jìn)行獲得最佳路徑。

第3步 按要求和順序逐個(gè)對(duì)目的點(diǎn)的路徑的實(shí)現(xiàn)

? 在設(shè)施網(wǎng)絡(luò)分析工具條上，點(diǎn)選旗標(biāo)和障礙工具板下拉箭頭，將旗標(biāo)按照車(chē)輛訪(fǎng)問(wèn)的順序逐個(gè)放在點(diǎn)上。

? 選擇“分析”下拉菜單，選擇“選項(xiàng)”按鈕，打開(kāi)“分析選項(xiàng)”對(duì)話(huà)框，選擇“權(quán)重”標(biāo)簽頁(yè)，在“邊權(quán)重”上，全部選擇長(zhǎng)度“l(fā)ength”權(quán)重屬性。? 點(diǎn)選“追蹤任務(wù)”下拉菜單選擇“查找路徑”。單擊“執(zhí)行”鍵，則從起點(diǎn)按順序逐一經(jīng)過(guò)超市最后回到家的最短有效路徑將顯示出來(lái)，這條路徑的總成本將顯示在狀態(tài)列。

同樣是經(jīng)過(guò)這11個(gè)地點(diǎn)，換成權(quán)重是時(shí)間的，由于道路車(chē)流量的不同，如在市中心車(chē)流量特別大，車(chē)速慢，故而為節(jié)約時(shí)間，所以使得路徑發(fā)生很大的改變。

第4步 阻強(qiáng)問(wèn)題

這里的阻強(qiáng)是指網(wǎng)絡(luò)中的點(diǎn)狀要素或線(xiàn)狀要素因?yàn)閷?shí)際中遇到的例如修路，或那個(gè)時(shí)段車(chē)輛飽和，十字路口發(fā)生事故等一些緣故而使得要素不可運(yùn)行，這時(shí)原來(lái)獲得的最短路徑就需要進(jìn)行修正，具體操作如下： 修路的情形出現(xiàn)，即某個(gè)路段不可運(yùn)行，這在網(wǎng)絡(luò)中的表現(xiàn)是設(shè)置阻強(qiáng)，方法有兩種，一種是永久性的，直接將網(wǎng)絡(luò)邊要素的屬性修改成不可運(yùn)行。選擇要進(jìn)行設(shè)置的邊要素，將其屬性中的“Enabled”字段改成“False”即可；另一種是暫時(shí)性的，設(shè)置邊要素障礙。即利用邊要素障礙添加工具將邊設(shè)置。

?

4、心得體會(huì) ：

第四篇：13．4 課題學(xué)習(xí)最短路徑問(wèn)題

13．4

課題學(xué)習(xí)

最短路徑問(wèn)題

能利用軸對(duì)稱(chēng)解決簡(jiǎn)單的最短路徑問(wèn)題，體會(huì)圖形的變化在解決最值問(wèn)題中的作用，感悟轉(zhuǎn)化思想．

利用軸對(duì)稱(chēng)將最短路徑問(wèn)題轉(zhuǎn)化為“兩點(diǎn)之間，線(xiàn)段最短”問(wèn)題．

探索發(fā)現(xiàn)“最短路徑”的方案，確定最短路徑的作圖及說(shuō)理．

一師一優(yōu)課　一課一名師(設(shè)計(jì)者：)

一、創(chuàng)設(shè)情景，明確目標(biāo)

如圖所示，從A地到B地有三條路可供選擇，走哪條路最近？你的理由是什么？

前面我們研究過(guò)一些關(guān)于“兩點(diǎn)的所有連線(xiàn)中，線(xiàn)段最短”、“連接直線(xiàn)外一點(diǎn)與直線(xiàn)上各點(diǎn)的所有線(xiàn)段中，垂線(xiàn)段最短”等的問(wèn)題，我們稱(chēng)它們?yōu)樽疃搪窂絾?wèn)題．現(xiàn)實(shí)生活中經(jīng)常涉及到選擇最短路徑的問(wèn)題，本節(jié)將利用數(shù)學(xué)知識(shí)探究數(shù)學(xué)史中著名的“將軍飲馬問(wèn)題”．

二、自主學(xué)習(xí)，指向目標(biāo)

自學(xué)教材第85

頁(yè)至87

頁(yè)，思考下列問(wèn)題：

1．求直線(xiàn)異側(cè)的兩點(diǎn)與直線(xiàn)上一點(diǎn)所連線(xiàn)段的和最小的問(wèn)題，只要連接這兩點(diǎn)，與直線(xiàn)的交點(diǎn)即為所求，其依據(jù)是兩點(diǎn)的所有連線(xiàn)中，線(xiàn)段最短．

2．求直線(xiàn)同側(cè)的兩點(diǎn)與直線(xiàn)上一點(diǎn)所連線(xiàn)段的和最小的問(wèn)題，只要找到其中一個(gè)點(diǎn)關(guān)于這條直線(xiàn)的對(duì)稱(chēng)點(diǎn)，連接對(duì)稱(chēng)點(diǎn)與另一個(gè)點(diǎn)，則與該直線(xiàn)的交點(diǎn)即為所求．

3．在解決最短路徑問(wèn)題時(shí)，我們通常利用軸對(duì)稱(chēng)、平移等變化把已知問(wèn)題轉(zhuǎn)化為容易解決的問(wèn)題，從而作出最短路徑的選擇．

三、合作探究，達(dá)成目標(biāo)

探索最短路徑問(wèn)題

活動(dòng)一：相傳，古希臘亞歷山大里亞城里有一位久負(fù)盛名的學(xué)者，名叫海倫．有一天，一位將軍專(zhuān)程拜訪(fǎng)海倫，求教一個(gè)百思不得其解的問(wèn)題：

從圖中的A地出發(fā)，到一條筆直的河邊l

飲馬，然后到B地．到河邊什么地方飲馬可使他所走的路線(xiàn)全程最短？

精通數(shù)學(xué)、物理學(xué)的海倫稍加思索，利用軸對(duì)稱(chēng)的知識(shí)回答了這個(gè)問(wèn)題．這個(gè)問(wèn)題后來(lái)被稱(chēng)為“將軍飲馬問(wèn)題”．你能將這個(gè)問(wèn)題抽象為數(shù)學(xué)問(wèn)題嗎？

追問(wèn)1　這是一個(gè)實(shí)際問(wèn)題，你打算首先做什么？答：將A，B

兩地抽象為兩個(gè)點(diǎn)，將河l

抽象為一條直線(xiàn)．

追問(wèn)2　你能用自己的語(yǔ)言說(shuō)明這個(gè)問(wèn)題的意思，并把它抽象為數(shù)學(xué)問(wèn)題嗎？

答：(1)從A

地出發(fā)，到河邊l

飲馬，然后到B

地；

(2)在河邊飲馬的地點(diǎn)有無(wú)窮多處，把這些地點(diǎn)與A，B

連接起來(lái)的兩條線(xiàn)段的長(zhǎng)度之和，就是從A

地到飲馬地，再回到B

地的路程之和；(3)現(xiàn)在的問(wèn)題是怎樣找出使兩條線(xiàn)段長(zhǎng)度之和為最短的直線(xiàn)l上的點(diǎn)．設(shè)C

為直線(xiàn)上的一個(gè)動(dòng)點(diǎn)，上面的問(wèn)題就轉(zhuǎn)化為：當(dāng)點(diǎn)C

在l的什么位置時(shí)，AC

與CB的和最小(如圖)．問(wèn)題2：如圖，點(diǎn)A，B

在直線(xiàn)l的同側(cè)，點(diǎn)C

是直線(xiàn)上的一個(gè)動(dòng)點(diǎn)，當(dāng)點(diǎn)C

在l的什么位置時(shí)，AC與CB的和最小？

追問(wèn)1：對(duì)于問(wèn)題2，如何將點(diǎn)B“移”到l的另一側(cè)B′處，滿(mǎn)足直線(xiàn)l

上的任意一點(diǎn)C，都保持CB

與CB′的長(zhǎng)度相等？

追問(wèn)2：你能利用軸對(duì)稱(chēng)的有關(guān)知識(shí)，找到上問(wèn)中符合條件的點(diǎn)B′嗎？

展示點(diǎn)評(píng)：作法：

(1)作點(diǎn)B

關(guān)于直線(xiàn)l的對(duì)稱(chēng)點(diǎn)B′；

(2)連接AB′，與直線(xiàn)l

交于點(diǎn)C.則點(diǎn)C

即為所求．

問(wèn)題3　你能用所學(xué)的知識(shí)證明AC

＋BC最短嗎？

證明：如圖，在直線(xiàn)l上任取一點(diǎn)C′(與點(diǎn)C

不重合)，連接AC′，BC′，B′C′.由軸對(duì)稱(chēng)的性質(zhì)知，BC

＝B′C，BC′＝B′C′.∴

AC

＋BC＝

AC

＋B′C

＝

AB′，AC′＋BC′＝

AC′＋B′C′.在△AB′C′中，AB′＜AC′＋B′C′，∴

AC

＋BC＜AC′＋BC′.即

AC

＋BC

最短.小組討論：證明AC

＋BC

最短時(shí)，為什么要在直線(xiàn)l

上任取一點(diǎn)C′(與點(diǎn)C

不重合)，證明AC

＋BC

＜AC′＋BC′？這里的“C′”的作用是什么？

反思小結(jié)：運(yùn)用軸對(duì)稱(chēng)變換及性質(zhì)將不在一條直線(xiàn)上的兩條線(xiàn)段轉(zhuǎn)化到一條直線(xiàn)上，然后用“兩點(diǎn)之間線(xiàn)段最短”解決問(wèn)題．利用三角形的三邊關(guān)系，若直線(xiàn)l上任意一點(diǎn)(與點(diǎn)C

不重合)與A，B

兩點(diǎn)的距離和都大于AC

＋BC，就說(shuō)明AC

＋BC

最小.C′的代表的是除點(diǎn)C以外直線(xiàn)l上的任意一點(diǎn)．

針對(duì)訓(xùn)練：

1．如圖，A、B是河流

同側(cè)的兩個(gè)村莊，現(xiàn)要在河邊修一個(gè)抽水站向兩村供水，問(wèn)抽水站修在什么地方才能使所需的管道最短？請(qǐng)?jiān)趫D中表示出來(lái)．

答：如下圖，作點(diǎn)B關(guān)于l的對(duì)稱(chēng)點(diǎn)B′，連接AB′交l于點(diǎn)P，點(diǎn)P即為所求．

2．如圖，一個(gè)旅游船從大橋AB的P處前往山腳下的Q處接游客，然后將游客送往河岸BC

上，再返回P處，請(qǐng)畫(huà)出旅游船的最短路徑．

答：作Q關(guān)于直線(xiàn)BC的對(duì)稱(chēng)點(diǎn)Q′，連接PQ′交BC于R，∴旅游船線(xiàn)路：P—Q—R—P.選址造橋問(wèn)題

活動(dòng)二：(造橋選址問(wèn)題)如圖，A和B兩地在一條河的兩岸，現(xiàn)要在河上造一座橋MN，橋造在何處可使從A到B的路徑AMNB最短？(假定河的兩岸是平行的直線(xiàn)，橋要與河垂直．)

展示點(diǎn)評(píng)：從A到B要走的路線(xiàn)是A→M→N→B，如圖所示，而MN是定值，于是要使路程最短，只要AM＋BN最短即可．

第五篇：迷宮最短路徑問(wèn)題的計(jì)算機(jī)解法

文章編號(hào):10060042(14)111;

/ / 假設(shè)迷宮入口的出發(fā)點(diǎn)存于seat [thepath(int m ,int n)/ / 0 < m ≤M

2{/ / 變量聲明部分———對(duì)所用其它變量完成變

量聲明

i = 0;/ / 此處開(kāi)始給迷宮設(shè)置圍墻 while(i < = n + 1)

{maze[0 ] [i ] = 1;maze[m + 1 ] [i ] = 1;i = i + 1;} i = 1;

while(i < = m + 1)

{maze[i ] [0 ] = 1;maze [i ] [ n + 1 ] = 1;i = i + 1;} i = 1;

/ / 此處開(kāi)始建立迷宮;并對(duì)標(biāo)志數(shù)組初始化 while(i < = m){j = 1;while(j < = n)

{maze [i ] [j ] = random(1);

/ / 隨機(jī)函數(shù)產(chǎn)生0 或1 并賦予迷宮 / / 可用Pat 值調(diào)整0 與1 的比例,然后打印迷

宮相應(yīng)位置(略)

status [i ] [j ] = 0;j = j + 1;} i = i + 1;}

/ / 讀入dire 數(shù)組;按順時(shí)針建立八個(gè)方向上的位移(略);

/ / 尋找最短路徑

if(maze [1 ] [1 ] = = 0 & & maze [m] [ n ] = = 0)/ / 出入口都可通行

top = 1;

/ / top 指向seat 數(shù)組中最新記入迷宮通行點(diǎn)的位置 f = 1;

/ / f 指向seat 數(shù)組中存放即將作為新出發(fā)點(diǎn)的位置 j = 0;/ / j = 0 ,表示找不到最短路徑;j = 1 ,表示

成功找到最短路徑

while(f < = top)/ / 以下為Critical Loop 循環(huán) {i = 1;while(i < = 8)

{/ / 從f 所指的出發(fā)點(diǎn)出發(fā),對(duì)八個(gè)方向搜索可

通行的位置

x = seat [f ] [0 ] + dire[i ] [1 ];y = seat [f ] [1 ] + dire[i ] [2 ];if(x = = m & & y = = n){/ / 找到最短路徑,打印輸出 printf(“%d , %d n”,m ,n);while(f!=thepath

6.算法分析 6.1 時(shí)間復(fù)雜性

這里選用漸進(jìn)時(shí)間復(fù)雜度(Asymptotic

Time Complexity)。作為問(wèn)題的基本操作的 原操作,應(yīng)是其重復(fù)執(zhí)行次數(shù)和算法的執(zhí)行 時(shí)間成正比的原操作,多數(shù)情況下它是最深 層循環(huán)內(nèi)的語(yǔ)句中的原操作,它的執(zhí)行次數(shù) 和包含它的語(yǔ)句的頻度(Frequency Count)相 同。因此,建立迷宮需要的時(shí)間為O(m 3 n)。在最壞情況下有m 3 n-1 個(gè)位置要進(jìn) 入seat 數(shù)組,所以尋找路徑也需要O(m 3 n),總的時(shí)間復(fù)雜性為O(m 3 n)。6.2 空間復(fù)雜性

本問(wèn)題的空間復(fù)雜度(Space Complexi2

ty)與算法密切相關(guān),它不僅需要存儲(chǔ)空間來(lái) 寄存迷宮本身所用的信息,還需要一些對(duì)數(shù) 據(jù)進(jìn)行操作的工作單元和存儲(chǔ)一些實(shí)現(xiàn)計(jì)算

所需信息的輔助空間。

其中,數(shù)組maze、status、seat 所需要的空 間都與m 3 n 成正比,其余都是常數(shù)。所以, 總的空間復(fù)雜性為O(m 3 n)。

此外,尚需說(shuō)明的是,所謂當(dāng)前位置“可 通”,指的是未曾走到過(guò)的通道,即要求該位 置不僅是通道,而且既不在當(dāng)前路徑上(否則 所求路徑就不是簡(jiǎn)單路徑),也不是曾經(jīng)納入 過(guò)路徑的通道(否則只能在死胡同內(nèi)轉(zhuǎn)圈)。一個(gè)迷宮的最短路徑可能不止一條,本 算法只給出首先找到的一條。首先找到哪一條最短路徑,與在任一位置上對(duì)八個(gè)方向的 搜索次序有關(guān),即與dire 數(shù)組元素值的排列 次序有關(guān)(如圖1 所示),調(diào)整dire 數(shù)組元素

值的排列次序,就可得到其它的最短路徑。

參考文獻(xiàn)

[1 ]嚴(yán)蔚敏、吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京:清華大學(xué)

出版社,2002.[2 ]郭潔志.計(jì)算機(jī)軟件實(shí)踐[M].陜西:西北電訊出

版社,1985.[3 ]黃劉生、唐策善.數(shù)據(jù)結(jié)構(gòu)[M].安徽:中國(guó)科學(xué)

技術(shù)大學(xué)出版社,2002.[4 ]王立柱.C/ C + + 與數(shù)據(jù)結(jié)構(gòu)[M].北京:清華大

學(xué)出版社,2002.45

第17 卷第1 期

2004 年2 月

高等函授學(xué)報(bào)(自然科學(xué)版)

Journal of Higher Correspondence Education(Natural Sciences)Vol.17 No.1 February 2004__