算法設(shè)計與分析 課件 第六章 回溯法6.3.4 路線選擇問題

計算機(jī)算法設(shè)計與分析第6章回溯法路線選擇問題在一個礦場有n個采礦區(qū)，礦場每天需要將各個礦區(qū)采的礦石運回處理。礦車從礦石處理車間出發(fā)，依次經(jīng)過每個采礦區(qū)一次將其采的礦石裝車，然后運回到礦石處理車間。礦場各個采礦區(qū)之間的距離已知。如何進(jìn)行路線選擇，使得礦石回收的運輸路線總長度最短。請用回溯算法求解礦石回收運輸路線選擇問題。路線選擇問題路線選擇問題是一個典型的TSP問題圖。設(shè)礦場各個采礦區(qū)的分布如圖所示。圖中結(jié)點A為礦石處理車間，結(jié)點B、C、D、E為四個采礦區(qū)，圖中頂點之間邊上權(quán)值表示兩個點之間的距離。排列樹定義v[1]~v[n]為問題的解向量，表示搜索過程中每一次選擇經(jīng)過的頂點。將頂點A~E映射為數(shù)字1~5，v[i]=j表示第i次選擇經(jīng)過的頂點為j。第二步：確定搜索結(jié)構(gòu)---排列樹

第一步：定義解向量第三步：確定剪枝函數(shù)v[1:n]有兩重含義：①v[1:i-1]代表前i-1步按順序經(jīng)過的頂點②v[i:n]代表還未經(jīng)過的頂點在第i次選擇經(jīng)過頂點時，只能在未經(jīng)過頂點序列v[i]~v[n]中進(jìn)行選擇。算法需要判斷當(dāng)前路徑長度是否優(yōu)于已經(jīng)找到的最優(yōu)回路長度作為剪枝函數(shù)，判斷當(dāng)路徑長度小于前面已知最優(yōu)值時，則繼續(xù)下一步探索，算法進(jìn)入排列樹下一層搜索，否則被剪枝處理。符號定義edge[n][n]：表示TSP問題圖的鄰接矩陣。v[n]：表示頂點序列，初值為{1,2,3,4,5}，將前面的圖中的頂點A,B,C,D,E映射為數(shù)字編號1,2,3,4,5。bestv[n]：存儲最優(yōu)路徑頂點序列。bestc：表示最優(yōu)路徑長度，初值為INF。cc：表述當(dāng)前路程長度，初值為0。路線選擇問題遞歸回溯偽碼Backtrack(i){if(i==n){if(當(dāng)前路徑長度+點n-1到n和點n到1的邊長<當(dāng)前最優(yōu)路徑長度)){

for(j

1;j<=n;j++)bestv[j]

v[j];

bestc

cc+edge[v[i-1]][v[i]]+edge[v[i]][1];

}}else{

for(j

i;j<=n;jif(當(dāng)前路徑+點i-1到j(luò)邊長<bestc){//搜索子樹

swap(v[i],v[j]);

cccc+

edge[v[i-1]][v[i]];

Backtrack(i+1);

cccc-

edge[v[i-1]][v[i]];

swap(v[i],v[j]);

}}//else}//函數(shù)Backtrack()從點i-1擴(kuò)展點i時，若i為葉子結(jié)點n，且edge[n-1][n]+edge[n][1]+cc<bestc則記錄最優(yōu)路徑，并將edge[n-1][n]+edge[n][1]+cc記錄為新的最優(yōu)路徑值bestc第i步從未經(jīng)過的頂點i~n中選擇一個j且i-1到j(luò)邊長+當(dāng)前路徑長度<bestc按排列樹框架處理遞歸過程時間復(fù)雜度分析回溯算法在最壞情況下需要訪問整個解空間排列樹全部結(jié)