算法設計與分析 課件 第一章 緒論1.3 例1.3_第1頁
算法設計與分析 課件 第一章 緒論1.3 例1.3_第2頁
算法設計與分析 課件 第一章 緒論1.3 例1.3_第3頁
算法設計與分析 課件 第一章 緒論1.3 例1.3_第4頁
算法設計與分析 課件 第一章 緒論1.3 例1.3_第5頁
已閱讀5頁，還剩3頁未讀， 繼續(xù)免費閱讀

下載本文檔

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

計算機算法設計與分析第一章緒論一個快遞小哥從快遞中心點出發(fā)，到周邊四個小區(qū)送快遞，要求經過每個小區(qū)且只能每個小區(qū)僅經過一次，最后回到快遞中心點。問快遞小哥應如何安排派送路線較好？例1.3快遞員路線安排問題起

終ABCDEA03456B30265C42043D56405E65350（1）問題分析與問題抽象，這是一個典型的TSP問題將小區(qū)抽象為下圖的頂點，兩個小區(qū)之間有路直達，則對應的兩個頂點之間有邊關聯(lián)，邊的權值為兩個小區(qū)之間的距離。則將快遞員路線安排問題抽象為從頂點A(設A為快遞中心)出發(fā)經過圖中其余頂點后回到頂點A的最短簡單回路問題。例1.3快遞員路線安排問題3365456542EBDCA（2）數學建模：例1.3快遞員路線安排問題3365456542EBDCA（3）方法一蠻力法：列出每一條可供選擇的路線，計算出每條路線的距離長度，最后從中選擇出一條最短路線。最短路程為：A-->B-->C-->E-->D-->A或者A-->D-->E-->C-->B-->A，最短路徑長度為:18。例1.3快遞員路線安排問題3365456542EBDCA（3）蠻力法算法效率分析：使用蠻力法列舉除出發(fā)小區(qū)外所有小區(qū)的排列，然后選取路徑最短的路線。n-1個小區(qū)的排列數為(n-1)!，當n=20時，遍歷路線總數約為1.216×1017，計算機以每秒1000萬條路線的檢索速度計算，則約需要386年才能完成。故蠻力法的時間復雜度太高，當頂點數過多時并不適用。例1.3快遞員路線安排問題（3）方法二貪心法：每次在選擇下一個小區(qū)時，只考慮當前情況。在沒有經過的小區(qū)中，選擇距離當前小區(qū)最近的一個，直到經過所有小區(qū)，最后回到快遞中心。A例1.3快遞員路線安排問題3365456542EBDCA貪心法的優(yōu)點是效率很高，只要n-1步判斷就能得到結果。但缺點是不一定能找到問題的最優(yōu)解。算法：貪心法—偽代碼描述輸入：小區(qū)數量n，鄰接矩陣e[i,j]，頂點v[i]，出發(fā)小區(qū)編號go_city，index當前小區(qū)編號。輸出：最短路線上的頂點信息，最短路徑長度min_l。Greedy(index):beginfori

1tondo ifi不是出發(fā)頂點go_citythen forj

1tondo if沒有經過小區(qū)jthen

篩選與當前出發(fā)點最短的頂點，并標記為cur_j endifendfor min_l

min_l+e[index,cur_j] index

cur_j//從出發(fā)點cur_j，繼續(xù)下一步求解

并置cur_j頂點為經過標記

endifend for

min_

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間，僅對用戶上傳內容的表現方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容，請與我們聯(lián)系，我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論