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

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

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

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)前路徑+點(diǎn)i-1到j(luò)邊長(zhǎng)<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()從點(diǎn)i-1擴(kuò)展點(diǎn)i時(shí)，若i為葉子結(jié)點(diǎn)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)過(guò)的頂點(diǎn)i~n中選擇一個(gè)j且i-1到j(luò)邊長(zhǎng)+當(dāng)前路徑長(zhǎng)度<bestc按排列樹框架處理遞歸過(guò)程時(shí)間復(fù)雜度分析回溯算法在最壞情況下需要訪問(wèn)整個(gè)解空間排列樹全部結(jié)