算法設(shè)計與分析 課件 第一章 緒論1.3 例1.3

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

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

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

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

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

min_l+e[index,cur_j] index

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

并置cur_j頂點為經(jīng)過標(biāo)記

endifend for

min_