蠻力動規(guī)貪心回溯法的01背包和TSP問題.doc

《蠻力動規(guī)貪心回溯法的01背包和TSP問題.doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、華北科技學院計算機學院綜合性實驗實驗報告課程名稱算法分析與設計實驗學期2014至2015學年第二學期學生所在系部計算機學院年級12級專業(yè)班級軟件B122班學生姓名周輝學號4任課教師王德志實驗成績計算機學院制《算法分析與設計》課程綜合性實驗報告開課實驗室：計算機基礎實驗室2015年05月28日實驗題目回溯法應用編程一、實驗目的：（1）掌握回溯算法求解圖問題和組合問題的方法和步驟。（2）理解回溯算法的基本思想。（3）提高學生的編程能力和分析問題、解決問題的能力。二、實驗設備及環(huán)境：微型計算機、VisualC++/JAVA三、實

2、驗內(nèi)容及要求：實驗內(nèi)容：（1）利用回溯算法，求解TSP問題。A.TSP問題偽代碼：輸入條件：城市個數(shù)n，鄰接矩陣a[][]。x[]為當前解，NoEdge=-1表示無窮大。x1[],y1[]為城市的坐標，cc為當前解，bestc為最優(yōu)解。BackTrack（t）回溯函數(shù)。（1）當t!=n時，BackTrack(1),表示從第一個城市出發(fā)。如果上一個節(jié)點和它此后的節(jié)點有邊,并且費用不高于現(xiàn)有的最優(yōu)費用(bestc==NoEdge表示第一次)，交換x[t]與x[i]的值，cc=cc+a[x[t-1]][x[t]],遞歸調(diào)用Bac

3、kTrack（i+1）。（2）當t==n時，bestx[i]=x[i],bestc=cc+a[x[n-1]][x[n]]+x[n][1].關(guān)鍵算法：voidBackTrack(intt){//t從2開始if(t==n){//到達第n個節(jié)點if(a[x[n-1]][x[n]]!=NoEdge&&(a[x[n]][1]!=NoEdge)&&(cc+a[x[n-1]][x[n]]+a[x[n]][1]

4、

5、bestc==NoEdge)){for(inti=1;i<=n;i++){bestx[i]=x[i];}bestc

6、=cc+a[x[n-1]][x[n]]+a[x[n]][1];//當前最優(yōu)解}}else{for(inti=t;i<=n;i++){//如果上一個節(jié)點和它此后的節(jié)點有邊,并且費用不高于現(xiàn)有的最優(yōu)費用(bestc==NoEdge表示第一次)if(a[x[t-1]][x[i]]!=NoEdge&&(cc+a[x[t-1]][x[i]]

7、

8、bestc==NoEdge)){swap(x[t],x[i]);//交換順序值cc+=a[x[t-1]][x[t]];BackTrack(t+1);//遞歸調(diào)用cc-=a[x[t-

9、1]][x[t]];swap(x[t],x[i]);}k++;}}}（2）利用回溯算法，求解0/1背包問題。B.01背包問題偽代碼：輸入條件：物品數(shù)n，背包重量C，物品重量w[i],價值v[i].（1）從n個物品中選取裝入背包的物品，物品i的重量為w[i]，價值為v[i]。物品的最高單位重量價值比為p[i]=v[i]/w[i];使用冒泡排序法將p[i]排序。(2)i=0,判斷第i個物品的重量是否小于背包重量。如果小于背包重量，將put[i]的值設為1，表示物品可放入背包。物品的總重量為cw=cw+w[i],總價值為cp=c

10、p+v[i],背包C的容量為C-w[i],隨后i++，繼續(xù)將下一個物品裝入背包（遞歸backtrack(i+1)）。直到第i個物品的重量裝入背包時的重量cw>C,此時進入右子樹，轉(zhuǎn)第三步。（3）此時判斷右子樹的最大價值是否大于當前最優(yōu)值bestp。若右子樹的最大價值大于當前最優(yōu)值。則遞歸backtrack(i+1)。當i>n的時候，則從backtrack(i+1)返回。（4）cw=cw-w[i],cp=cp-v[i],此時的cw

11、值bestp，循環(huán)次數(shù)k。關(guān)鍵代碼：//回溯函數(shù)publicvoidbacktrack(inti){if(i>n){//到達葉子節(jié)點bestp=cp;return;//返回上一節(jié)點}if(cw+w[i]<=C){//判斷物品w[i]是否能裝入背包中cw+=w[i];cp+=v[i];put[i]=1;//物品被裝入到背包中。k++;backtrack(i+1);//遞歸調(diào)用cw-=w[i];//返回上一個物品的重量cp-=v[i];//返回上一個物品的價值}if(bound(i+1)>bestp){//符合條件搜索右子樹k

12、++;backtrack(i+1);}}四、實驗結(jié)果及分析1、實驗運行過程及分析2、運行結(jié)果A、01背包問題當背包重量為200時當物品為4個的時候：當物品為10個的時候：TSP問題：當城市為4的時候：當城市為10的時候：01背包問題個算法的比較：TSP各算法的比較：3、心得體會通過這次的算法分析與設計的