第一篇：迷宮最短路徑問題的計算機解法

文章編號:10060042(14)111;

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

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

量聲明

i = 0;/ / 此處開始給迷宮設置圍墻 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;

/ / 此處開始建立迷宮;并對標志數組初始化 while(i < = m){j = 1;while(j < = n)

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

/ / 隨機函數產生0 或1 并賦予迷宮 / / 可用Pat 值調整0 與1 的比例,然后打印迷

宮相應位置(略)

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

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

/ / 尋找最短路徑

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

top = 1;

/ / top 指向seat 數組中最新記入迷宮通行點的位置 f = 1;

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

成功找到最短路徑

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

{/ / 從f 所指的出發點出發,對八個方向搜索可

通行的位置

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 時間復雜性

這里選用漸進時間復雜度(Asymptotic

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

本問題的空間復雜度(Space Complexi2

ty)與算法密切相關,它不僅需要存儲空間來 寄存迷宮本身所用的信息,還需要一些對數 據進行操作的工作單元和存儲一些實現計算

所需信息的輔助空間。

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

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

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

參考文獻

[1 ]嚴蔚敏、吳偉民.數據結構[M].北京:清華大學

出版社,2002.[2 ]郭潔志.計算機軟件實踐[M].陜西:西北電訊出

版社,1985.[3 ]黃劉生、唐策善.數據結構[M].安徽:中國科學

技術大學出版社,2002.[4 ]王立柱.C/ C + + 與數據結構[M].北京:清華大

學出版社,2002.45

第17 卷第1 期

2004 年2 月

高等函授學報(自然科學版)

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

第二篇：最短路徑教案

13.4最短路徑問題

一、教學內容：本節課的主要內容是利用軸對稱研究某些最短路徑問題，最短路徑問題在現實生活中經常遇到，初中階段，主要以“兩點之間，線段最短”“連接直線外一點與直線上各點的所有連線中，垂線段最短”為知識基礎，有時還要借助軸對稱、平移、旋轉等變換進行研究。

本節課以數學史中的一個經典故事----“將軍飲馬問題”為載體開展對“最短路徑問題”的課題研究，讓學生經歷將實際問題抽象為數學的線段和最小問題，再利用軸對稱將線段和最小問題轉化為“兩點之間、線段最短”的問題。

二、教學目標

1、能利用軸對稱解決簡單的最短路徑問題

2、再談歲最短路徑的過程中，體會“軸對稱”的橋梁作用，感悟轉化的數學思想。

三、教學重難點

重點：利用軸對稱將最短路徑問題轉化為“兩點之間、線段最短”問題。難點：如何利用軸對稱將最短路徑問題轉化為線段和最小問題。

四、教學問題診斷

最短路徑問題從本質上說是最值問題，作為初中學生，在此前很少涉及最值問題，解決這方面問題的數學經驗尚顯不足，特別是面對具有實際背景的最值問題，更會感到陌生，無從下手。

解答“當點AB在直線l的同側時，如何在l上找到點C，使AC與BC的和最小”，需要將其轉化為“直線l異側的兩點，與直線l上的點的線段的和最小”的問題，為什么需要這樣轉化，怎樣通過軸對稱實現轉化，一些學生會存在理解上和操作上的困難。

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

教學時，教師可以讓學生首先思考“直線l異側的兩點，與直線l上的點的和最小”為學生搭建“腳手架”，在證明最短時，教師要適時點撥學生，讓學生體會任意的作用。

五、教學過程

教師引語：現實生活中經常會有這樣的生活經歷，比如學校雖然為我們鋪設了一些石板甬路，方便同學們的行走，但是很多時候我們卻并不在這些小路上行走，這樣做的目的是什么呢？（學生一起回答）如果用數學知識來解釋這種行為，那就是我們曾經學習的“兩點之間、線段最短”或“垂線段最短”，我們稱這樣的問題為最短路徑問題（板書課題）現實生活中經常涉及到最短路徑問題，這節課我們學習的主要任務就是最短路徑問題，并用所學知識探究數學史上著名的“將軍飲馬問題”。

1、情境引入

相傳，古希臘亞歷山大里亞城里有一位久負盛名的學者，名叫海倫，有一天，有一位將軍專門拜訪海倫，求教一個百思不得其解的問題：從圖中的A地出發，到一條筆直的河邊飲馬，然后到B地，到河邊什么地方飲馬，可使他所走的路線全程最短？精通數學、物理學的海倫稍加思索，利用軸對稱的知識回答了這個問題。這個問題后來被稱為“將軍飲馬問題”。

2、探究解決問題的方法

問題一：這是一個實際問題，我們首先把它抽象為數學問題，請同學們用自己的語言說明這個問題的意思。

師生活動：學生獨立思考后小組交換意見，然后嘗試回答，相互補充，最后達成共識，教師根據學生的回答寫出問題的板書：如圖，已知點A和點B在直線L的同側，在直線L上找一點C，使AC與BC的和最小。

設計意圖：讓學生將實際問題抽象為數學問題，即將最短路徑問題抽象為“線段和最小問題”。

問題二：由上面的問題我們可以聯想到下面的問題：A、B分別是直線L異側的兩點，如何在直線L上找到一點C，使AC與BC的和最小？

師生活動：學生獨立思考，畫圖分析并嘗試回答，教師補充。

問題三：對于第一個問題，如何將點B移到L的另一側，B′處，滿足直線L上的任一點C，都保持CB與CB′的長度相等？ 問題四：你能利用軸對稱的知識找到符合條件的點B′嗎？

師生活動：學生獨立考，嘗試畫圖，然后小組交流，學生代表匯報交流成果，師生共同補充：只要作出點B關于直線L的對稱點B′，就可以滿足CB=CB′,再利用問題二中的方法，連接AB′,則AB′與直線L的交點即為所求。

學生敘述，教師板書并畫圖，同時學生在練習本上畫圖。

設計意圖：通過搭建臺階，為學生探究問題提供“腳手架”將同側難以解決的問題提轉化為異側容易解決的問題，滲透轉化思想。

3、推理證明“最短”

問題五：你能用所學的知識證明AC+BC最短嗎？

師生活動：師生共同分析，然后學生說證明過程，教師板書。

證明：在直線L上任取一點C′（與點C不重合），連接AC′,BC′,B′C′.由軸對稱的性質可知，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最短。

問題六：這里任取一點C′的作用是什么？

師生活動：學生相互交流，教師適時點撥，最后達成共識：若直線L上任取一點C′與A、B兩點的距離之和都大于AC+BC，則說明AC+BC最短。

設計意圖：讓學生進一步體會做法的正確性，提高邏輯思維能力。

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

師生共同總結：首先作其中一點關于直線的對稱點，然后連接另一點與對稱點之間的線段，通過軸對稱將兩條線段和轉化到同一條線段上去，這條線段與直線的交點即為所求，整個過程利用了“軸對稱”和“兩點之間、線段最短“的知識。

設計意圖：讓學生在反思的過程中，體會軸對稱的“橋梁”作用，感悟轉化思想，豐富數學活動經驗。

4、鞏固練習

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

師生活動：學生分析解題思路，并相互補充，然后獨立完成畫圖，學生代表上臺講解。基本思路分析：此題中輪船的行走路線共有三段，其中PQ是必經路段，由“兩點之間，線段最短”需首先連接PQ，再將河岸BC看成一條直線，這樣問題就轉化為“點P、Q在直線BC同側，如何在BC上找一點R，使PR+QR最小”。

設計意圖：讓學生進一步鞏固解決最短路徑問題的基本策略和基本方法。

（2）如圖，∠XOY內有一點P，在射線OX上找出一點M，在射線OY上找出一點N，使PM+MN+NP最短．

分析：此題的出題背景就是角。本題主要利用了兩點之間線段最短的性質通過軸對稱圖形的性質確定三角形的另兩點．

分別以直線OX、OY為對稱軸，作點P的對應點P1與P2，連接P1P2交OX于M，交OY于N，則PM+MN+NP最短．

5、課堂小結：教師與學生一起回顧本節課所學主要內容，并請學生回答：（1）本節課研究問題的基本過程是什么？（2）軸對稱在所研究的問題中起到什么作用？

6、布置作業：《課時練》第49頁1、2、3、4、5、7、8、9

第三篇：ArcGIS網絡分析(最短路徑問題分析)

網絡分析（最短路徑問題分析）

一、實驗目的：

理解最短路徑分析的基本原理，學習利用arcgis軟件進行各種類型的最短路徑分析的操作。

二、實驗準備

1、實驗背景：

最短路徑分析是空間網絡分析中最基本的應用，而交通網絡中要素的設置對最短路徑的選擇有著很大的影響。實驗要求根據不同的權重，給出到達指定目的地的路徑選擇方案，并給出路徑長度。

? 在網絡中指定一個超市，要求分別求出在距離、時間限制上從家到超市的最佳路徑。

? 給定訪問順序，按要求找出從家經逐個地點達到目的地的最佳路徑。

2、實驗材料：

軟件：ArcGIS Desktop 9.x，實驗數據：文件夾ex6中，一個GeoDatabase地理數據庫：City.mdb，內含有城市交通網、超市分布圖，家庭住址以及網絡關系。

三、實驗內容及步驟

首先啟動ArcMap，選擇ex6city.mdb，再雙擊后選擇將整個要素數據集“city”加載進來，然后將“place”點狀要素以“HOME”字段屬性值進行符號化，1值是家，0值是超市。

第1步 無權重最佳路徑的選擇 ? 加載 “設施網絡分析”工具條（“視圖”>>“工具條”，勾選“設施網絡分析”），點選旗標和障礙工具板下拉箭頭，將旗標放在家和想要去的超市點上。

第2步 加權最佳路徑選擇

? 在設施網絡分析工具條上，點選旗標和障礙工具板下拉箭頭，將旗標放在家和想去的某個超市點上。

? 選擇“分析”下拉菜單，選擇“選項”按鈕，打開“分析選項”對話框，選擇“權重”標簽頁，在“邊權重”上，全部選擇長度“length”權重屬性。? 點選“追蹤任務”下拉菜單選擇“查找路徑”。單擊“執行”鍵，則以長度為比重為基礎的最短路徑將顯示出來，這條路徑的總成本將顯示在狀態列。

?? 上述是通過距離的遠近選擇而得到的最佳路徑，而不同類型的道路由于道路車流量的問題，有時候要選擇時間較短的路徑，同樣可以利用網絡分析進行獲得最佳路徑。

第3步 按要求和順序逐個對目的點的路徑的實現

? 在設施網絡分析工具條上，點選旗標和障礙工具板下拉箭頭，將旗標按照車輛訪問的順序逐個放在點上。

? 選擇“分析”下拉菜單，選擇“選項”按鈕，打開“分析選項”對話框，選擇“權重”標簽頁，在“邊權重”上，全部選擇長度“length”權重屬性。? 點選“追蹤任務”下拉菜單選擇“查找路徑”。單擊“執行”鍵，則從起點按順序逐一經過超市最后回到家的最短有效路徑將顯示出來，這條路徑的總成本將顯示在狀態列。

同樣是經過這11個地點，換成權重是時間的，由于道路車流量的不同，如在市中心車流量特別大，車速慢，故而為節約時間，所以使得路徑發生很大的改變。

第4步 阻強問題

這里的阻強是指網絡中的點狀要素或線狀要素因為實際中遇到的例如修路，或那個時段車輛飽和，十字路口發生事故等一些緣故而使得要素不可運行，這時原來獲得的最短路徑就需要進行修正，具體操作如下： 修路的情形出現，即某個路段不可運行，這在網絡中的表現是設置阻強，方法有兩種，一種是永久性的，直接將網絡邊要素的屬性修改成不可運行。選擇要進行設置的邊要素，將其屬性中的“Enabled”字段改成“False”即可；另一種是暫時性的，設置邊要素障礙。即利用邊要素障礙添加工具將邊設置。

?

4、心得體會 ：

第四篇：13．4 課題學習最短路徑問題

13．4

課題學習

最短路徑問題

能利用軸對稱解決簡單的最短路徑問題，體會圖形的變化在解決最值問題中的作用，感悟轉化思想．

利用軸對稱將最短路徑問題轉化為“兩點之間，線段最短”問題．

探索發現“最短路徑”的方案，確定最短路徑的作圖及說理．

一師一優課　一課一名師(設計者：)

一、創設情景，明確目標

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

前面我們研究過一些關于“兩點的所有連線中，線段最短”、“連接直線外一點與直線上各點的所有線段中，垂線段最短”等的問題，我們稱它們為最短路徑問題．現實生活中經常涉及到選擇最短路徑的問題，本節將利用數學知識探究數學史中著名的“將軍飲馬問題”．

二、自主學習，指向目標

自學教材第85

頁至87

頁，思考下列問題：

1．求直線異側的兩點與直線上一點所連線段的和最小的問題，只要連接這兩點，與直線的交點即為所求，其依據是兩點的所有連線中，線段最短．

2．求直線同側的兩點與直線上一點所連線段的和最小的問題，只要找到其中一個點關于這條直線的對稱點，連接對稱點與另一個點，則與該直線的交點即為所求．

3．在解決最短路徑問題時，我們通常利用軸對稱、平移等變化把已知問題轉化為容易解決的問題，從而作出最短路徑的選擇．

三、合作探究，達成目標

探索最短路徑問題

活動一：相傳，古希臘亞歷山大里亞城里有一位久負盛名的學者，名叫海倫．有一天，一位將軍專程拜訪海倫，求教一個百思不得其解的問題：

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

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

精通數學、物理學的海倫稍加思索，利用軸對稱的知識回答了這個問題．這個問題后來被稱為“將軍飲馬問題”．你能將這個問題抽象為數學問題嗎？

追問1　這是一個實際問題，你打算首先做什么？答：將A，B

兩地抽象為兩個點，將河l

抽象為一條直線．

追問2　你能用自己的語言說明這個問題的意思，并把它抽象為數學問題嗎？

答：(1)從A

地出發，到河邊l

飲馬，然后到B

地；

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

連接起來的兩條線段的長度之和，就是從A

地到飲馬地，再回到B

地的路程之和；(3)現在的問題是怎樣找出使兩條線段長度之和為最短的直線l上的點．設C

為直線上的一個動點，上面的問題就轉化為：當點C

在l的什么位置時，AC

與CB的和最小(如圖)．問題2：如圖，點A，B

在直線l的同側，點C

是直線上的一個動點，當點C

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

追問1：對于問題2，如何將點B“移”到l的另一側B′處，滿足直線l

上的任意一點C，都保持CB

與CB′的長度相等？

追問2：你能利用軸對稱的有關知識，找到上問中符合條件的點B′嗎？

展示點評：作法：

(1)作點B

關于直線l的對稱點B′；

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

交于點C.則點C

即為所求．

問題3　你能用所學的知識證明AC

＋BC最短嗎？

證明：如圖，在直線l上任取一點C′(與點C

不重合)，連接AC′，BC′，B′C′.由軸對稱的性質知，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

最短時，為什么要在直線l

上任取一點C′(與點C

不重合)，證明AC

＋BC

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

反思小結：運用軸對稱變換及性質將不在一條直線上的兩條線段轉化到一條直線上，然后用“兩點之間線段最短”解決問題．利用三角形的三邊關系，若直線l上任意一點(與點C

不重合)與A，B

兩點的距離和都大于AC

＋BC，就說明AC

＋BC

最小.C′的代表的是除點C以外直線l上的任意一點．

針對訓練：

1．如圖，A、B是河流

同側的兩個村莊，現要在河邊修一個抽水站向兩村供水，問抽水站修在什么地方才能使所需的管道最短？請在圖中表示出來．

答：如下圖，作點B關于l的對稱點B′，連接AB′交l于點P，點P即為所求．

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

上，再返回P處，請畫出旅游船的最短路徑．

答：作Q關于直線BC的對稱點Q′，連接PQ′交BC于R，∴旅游船線路：P—Q—R—P.選址造橋問題

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

展示點評：從A到B要走的路線是A→M→N→B，如圖所示，而MN是定值，于是要使路程最短，只要AM＋BN最短即可．

第五篇：八年級數學最短路徑問題

八年級數學最短路徑問題

一、兩點在一條直線異側

例：已知：如圖，A，B在直線L的兩側，在L上求一點P，使得PA+PB最小。

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

二、兩點在一條直線同側

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

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

例：已知：如圖A是銳角∠MON內部任意一點，在∠MON的兩邊OM，ON上各取一點B，C，組成三角形ABC，使三角形周長最小.練習1：已知：如圖A是銳角∠MON內部任意一點，在∠MON的兩邊OM，ON上各取一點B，C，組成三角形ABC周長最小值為OA.求∠MON的度數。

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

提高訓練

一、題中出現一個動點。

1.當題中只出現一個動點時,可作定點關于動點所在直線的對稱點,利用兩點之間線段最短,或三角形兩邊之和小于第三邊求出最值.例：如圖，在正方形ABCD中，點E為AB上一定點，且BE=10,CE=14,P為BD上一動點，求PE+PC最小值。

二、題中出現兩個動點。當題中出現兩個定點和兩個動點時,應作兩次定點關于動點所在直線的對稱點.利用兩點之間線段最短求出最值。

例：如圖，在直角坐標系中有四個點, A(-8,3),B(-4,5)C(0，n),D(m,0),當四邊形ABCD周長最短時,求 C、D的坐標。

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

．

三、題中出現三個動點時。

在求解時應注意兩點：(1)作定點關于動點所在直線的對稱點,(2)同時要考慮點點,點線,線線之間的最短問題.例：如圖，在菱形ABCD中,AB=2,∠BAD=60°,E,F,P分別為AB,BC,AC上動點, 求PE+PF最小值 例：如圖，∠AOB=45°，角內有一動點P，PO=10，在AO，BO上有兩動點Q，R，求△PQR周長的最小值。

練習1如圖，∠AOB=30°，角內有一定點P，PO=20cm，在AO，BO上有兩動點C、D，求△PCD周長的最小值。