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

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

第一步：定義解向量第三步：確定剪枝函數(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]中進行選擇。算法需要判斷當前路徑長度是否優(yōu)于已經(jīng)找到的最優(yōu)回路長度作為剪枝函數(shù)，判斷當路徑長度小于前面已知最優(yōu)值時，則繼續(xù)下一步探索，算法進入排列樹下一層搜索，否則被剪枝處理。符號定義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：表述當前路程長度，初值為0。路線選擇問題遞歸回溯偽碼Backtrack(i){if(i==n){if(當前路徑長度+點n-1到n和點n到1的邊長<當前最優(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(當前路徑+點i-1到j邊長<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擴展點i時，若i為葉子結點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邊長+當前路徑長度<bestc按排列樹框架處理遞歸過程時間復雜度分析回溯算法在最壞情況下需要訪問整個解空間排列樹全部結