0027算法筆記——【回溯法】回溯法與裝載問題.docx

1、回溯法 (1)描述:回溯法是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達到目標。但當探索到某一步時，發(fā)現(xiàn)原先選擇并不優(yōu)或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術(shù)為回溯法。 (2)原理:回溯法在問題的解空間樹中，按深度優(yōu)先策略，從根結(jié)點出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點時，先判斷該結(jié)點是否包含問題的解。如果肯定不包含，則跳過對該結(jié)點為根的子樹的搜索，逐層向其祖先結(jié)點回溯；否則，進入該子樹，繼續(xù)按深度優(yōu)先策略搜索。 回溯法的基本做法是搜索，或是一種組織得井井有條的，能避免不必要搜索的窮舉式搜索法。這種方法適用于解一些組合數(shù)相當大的問題。有許多問題，當需要找出它的解集或者要求回答什么解是滿足某些約束條件的最佳解時，往往要使用回溯法。 (3)問題的解空間 問題的解向量：回溯法希望一個問題的解能夠表示成一個n元式(x1,x2,xn)的形式。 顯約束：對分量xi的取值限定。 隱約束：為滿足問題的解而對不同分量之間施加的約束。 解空間：對于問題的一個實例，解向量滿足顯式約束條件的所有多元組，構(gòu)成了該實例的一個解空間。 注意：同一個問題可以有多種表示，有些表示方法更簡單，所需表示的狀態(tài)空間更?。ù鎯α可?，搜索方法簡單）。 例1：n=3的01 背包問題的回溯法搜索過程。W=16,15,15 p=45,25,25 C=30 例2：旅行售貨員問題。某售貨員要到若干城市去推銷商品，已知各城市之間的路程（旅費），他要選定一條從駐地出發(fā)，經(jīng)過每個城市一遍，最后回到駐地的路線，使總的路程（總旅費）最小。 (4)生成問題狀態(tài)的基本方法 擴展結(jié)點:一個正在產(chǎn)生兒子的結(jié)點稱為擴展結(jié)點。 活結(jié)點:一個自身已生成但其兒子還沒有全部生成的節(jié)點稱做活結(jié)點。 死結(jié)點:一個所有兒子已經(jīng)產(chǎn)生的結(jié)點稱做死結(jié)點。 深度優(yōu)先的問題狀態(tài)生成法：如果對一個擴展結(jié)點R，一旦產(chǎn)生了它的一個兒子C，就把C當做新的擴展結(jié)點。在完成對子樹C（以C為根的子樹）的窮盡搜索之后，將R重新變成擴展結(jié)點，繼續(xù)生成R的下一個兒子（如果存在）。 寬度優(yōu)先的問題狀態(tài)生成法：在一個擴展結(jié)點變成死結(jié)點之前，它一直是擴展結(jié)點。 回溯法：為了避免生成那些不可能產(chǎn)生最佳解的問題狀態(tài)，要不斷地利用限界函數(shù)(bounding function)來處死那些實際上不可能產(chǎn)生所需解的活結(jié)點，以減少問題的計算量。具有限界函數(shù)的深度優(yōu)先生成法稱為回溯法。 (5)回溯法的基本思想 基本思想： 用回溯法解題的一個顯著特征是在搜索過程中動態(tài)產(chǎn)生問題的解空間。在任何時刻，算法只保存從根結(jié)點到當前擴展結(jié)點的路徑。如果解空間樹中從根結(jié)點到葉結(jié)點的最長路徑的長度為h(n)，則回溯法所需的計算空間通常為O(h(n)。而顯式地存儲整個解空間則需要O(2h(n)或O(h(n)!)內(nèi)存空間。 解題步驟： 1)針對所給問題，定義問題的解空間； 2)確定易于搜索的解空間結(jié)構(gòu)； 3)以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。 常用剪枝函數(shù)：用約束函數(shù)在擴展結(jié)點處剪去不滿足約束的子樹；用限界函數(shù)剪去得不到最優(yōu)解的子樹。 遞歸回溯： 回溯法對解空間作深度優(yōu)先搜索，因此，在一般情況下用遞歸方法實現(xiàn)回溯法。cppview plaincopy1. voidbacktrack(intt)2. 3. if(tn)4. output(x);/已到葉子結(jié)點，輸出結(jié)果5. else6. for(inti=f(n,t);i0)5. if(f(n,t)=g(n,t)6. for(inti=f(n,t);in)output(x);4. else5. for(inti=0;in)output(x);4. else5. for(inti=t;ic1時，以結(jié)點z為根的子樹中所有結(jié)點都不滿足約束條件，因而該子樹中的解均為不可行解，故可將該子樹剪去。（該約束函數(shù)去除不可行解，得到所有可行解）。 可以引入一個上界函數(shù)，用于剪去不含最優(yōu)解的子樹，從而改進算法在平均情況下的運行效率。設z是解空間樹第i層上的當前擴展結(jié)點。cw是當前載重量；bestw是當前最優(yōu)載重量；r是剩余集裝箱的重量，即r=。定義上界函數(shù)為cw+r。在以z為根的子樹中任一葉結(jié)點所相應的載重量均不超過cw+r。因此，當cw+r=bestw時，可將z的右子樹剪去。 遞歸回溯具體代碼如下：cppview plaincopy1. #includestdafx.h2. #include3. usingnamespacestd;4. 5. template6. classLoading7. 8. /friendTypeMaxLoading(Type,Type,int,int);9. /private:10. public:11. voidBacktrack(inti);12. intn,/集裝箱數(shù)13. *x,/當前解14. *bestx;/當前最優(yōu)解15. Type*w,/集裝箱重量數(shù)組16. c,/第一艘輪船的載重量17. cw,/當前載重量18. bestw,/當前最優(yōu)載重量19. r;/剩余集裝箱重量20. ;21. 22. template23. voidLoading:Backtrack(inti);24. 25. template26. TypeMaxLoading(Typew,Typec,intn,intbestx);27. 28. intmain()29. 30. intn=3,m;31. intc=50,c2=50;32. 33. intw4=0,10,40,40;34. intbestx4;35. 36. m=MaxLoading(w,c,n,bestx);37. 38. cout輪船的載重量分別為：endl;39. coutc(1)=c,c(2)=c2endl;40. 41. cout待裝集裝箱重量分別為：endl;42. coutw(i)=;43. for(inti=1;i=n;i+)44. 45. coutwi;46. 47. coutendl;48. 49. cout回溯選擇結(jié)果為：endl;50. coutm(1)=mendl;51. coutx(i)=;52. 53. for(inti=1;i=n;i+)54. 55. coutbestxi;56. 57. coutendl;58. 59. intm2=0;60. for(intj=1;j=n;j+)61. 62. m2=m2+wj*(1-bestxj);63. 64. coutm(2)=m2c2)67. 68. cout因為m(2)大于c(2),所以原問題無解！endl;69. 70. return0;71. 72. 73. template74. voidLoading:Backtrack(inti)/搜索第i層結(jié)點75. 76. if(in)/到達葉結(jié)點77. 78. if(cwbestw)79. 80. for(intj=1;j=n;j+)81. 82. bestxj=xj;/更新最優(yōu)解83. bestw=cw;84. 85. 86. return;87. 88. 89. r-=wi;90. if(cw+wibestw)99. 100. xi=0;/搜索右子樹101. Backtrack(i+1);102. 103. r+=wi;104. 105. 106. template107. TypeMaxLoading(Typew,Typec,intn,intbestx)/返回最優(yōu)載重量108. 109. LoadingX;110. /初始化X111. X.x=newintn+1;112. X.w=w;113. X.c=c;114. X.n=n;115. X.bestx=bestx;116. X.bestw=0;117. X.cw=0;118. /初始化r119. X.r=0;120. 121. for(inti=1;i=n;i+)122. 123. X.r+=wi;124. 125. 126. X.Backtrack(1);127. deleteX.x;128. returnX.bestw;129. 迭代回溯具體代碼如下：cppview plaincopy1. #includestdafx.h2. #include3. usingnamespacestd;4. 5. template6. TypeMaxLoading(Typew,Typec,intn,intbestx);7. 8. intmain()9. 10. intn=3,m;11. intc=50,c2=50;12. intw4=0,10,40,40;13. intbestx4;14. 15. m=MaxLoading(w,c,n,bestx);16. 17. cout輪船的載重量分別為：endl;18. coutc(1)=c,c(2)=c2endl;19. 20. cout待裝集裝箱重量分別為：endl;21. coutw(i)=;22. for(inti=1;i=n;i+)23. 24. coutwi;25. 26. coutendl;27. 28. cout回溯選擇結(jié)果為：endl;29. coutm(1)=mendl;30. coutx(i)=;31. 32. for(inti=1;i=n;i+)33. 34. coutbestxi;35. 36. coutendl;37. 38. intm2=0;39. for(intj=1;j=n;j+)40. 41. m2=m2+wj*(1-bestxj);42. 43. coutm(2)=m2c2)46. 47. cout因為m(2)大于c(2),所以原問題無解！endl;48. 49. return0;50. 51. 52. 53. template54. TypeMaxLoading(Typew,Typec,intn,intbestx)/迭代回溯法，返回最優(yōu)載重量及其相應解，初始化根結(jié)點55. 56. inti=1;/當前層，x1:i-1為當前路徑57. int*x=newintn+1;58. 59. Typebestw=0,/當前最優(yōu)載重量60. cw=0,/當前載重量61. r=0;/剩余集裝箱重量62. 63. for(intj=1;j=n;j+)64. 65. r+=wj;66. 67. 68. while(true)/搜索子樹69. 70. while(i=n&cw+win)/到達葉結(jié)點79. 80. for(intj=1;j=n;j+)81. 82. bestxj=