系研一下學(xué)期-算法設(shè)計(jì)與分析課件ch6.backtracking

Chapter6(Zilei: 迭代回子集樹算法框排列樹算法框裝載問批處理作業(yè)調(diào)符號(hào)三角形問USTCn后問0-1背包問最大團(tuán)問圖的 問旅行售貨員問圓排列問電路板排列問連續(xù)郵資問USTC一種組織得井井有條的，能避免不必要搜索的窮舉式搜索適用于解一些組合數(shù)相當(dāng)大的問如果肯定不包含，則跳過對(duì)該結(jié)點(diǎn)為根的子樹的搜索，逐層向祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜USTC注意注意：要確定好組織結(jié)構(gòu)同一個(gè)問題可以有多種表示，有些表示方法更簡(jiǎn)單，所需表示狀態(tài)空間更小量少，搜索方法簡(jiǎn)單隱約束：為滿足問題的解而對(duì)不同分量之間n=3時(shí)的0-1背包問題用完全二叉樹表示的解空USTC擴(kuò)展結(jié)點(diǎn)：一個(gè)正在產(chǎn)生兒子的結(jié)點(diǎn)稱為擴(kuò)展結(jié)活結(jié)點(diǎn)：一個(gè)自身已生成但其兒子還沒有全部生成的節(jié)點(diǎn)稱做活結(jié)死結(jié)點(diǎn)：一個(gè)所有兒子已經(jīng)產(chǎn)生的結(jié)點(diǎn)稱做死結(jié)如果對(duì)一個(gè)擴(kuò)展結(jié)點(diǎn)R，一旦產(chǎn)生了它的一個(gè)兒子C，就把C當(dāng)做新在完成對(duì)子樹C（以C為根的子樹）的窮盡搜索之后，將R重新變成擴(kuò)展結(jié)點(diǎn)，繼續(xù)生成R的下一個(gè)兒子（如果存在）在一個(gè)擴(kuò)展結(jié)點(diǎn)變成死結(jié)點(diǎn)之前，它一直是擴(kuò)展結(jié)USTC(boundingfunction)來處死那些實(shí)際上不可能產(chǎn)生所需解的活結(jié)具有限界函數(shù)的深度優(yōu)先生成法USTC12USTC在任何時(shí)刻，算法只保存從根結(jié)點(diǎn)到當(dāng)前擴(kuò)展結(jié)點(diǎn)的路回溯法所需的計(jì)算空間通常O(h(n))而顯式 整個(gè)解空間則需要O(2h(n))或O(h(n)!)的內(nèi)存空USTCvoidbacktrack(int{if(t>n)output(x);for(inti=f(n,t);i<=g(n,t);i++){if(constraint(t)&&bound(t))}}進(jìn)入子節(jié)解賦子節(jié)點(diǎn)遍葉節(jié)USTCvoidvoiditerativeBacktrack{intwhile(t>0)iffor(inti=f(n,t);i<=g(n,t);i++)if(constraint(t)&&bound(t))if(solution(t))else elset--}14.USTC遍歷子集樹需O(2n)計(jì)算時(shí)

遍歷排列樹需要O(n!)計(jì)算時(shí)voidbacktrackvoidbacktrack(int{if(t>n)for(inti=0;i<=1;i++)if(legal(t)) voidbacktrack(int{if(t>n)for(inti=t;i<=n;i++)swap(x[t],if(legal(t))swap(x[t], 10.USTCiwi，且inw c c裝載問題要求確定是否有一個(gè)合理的裝載方案可將這個(gè)集裝箱裝上2艘輪船；如果有，找出一種裝載方案(1)首先將第一艘輪船盡可能裝(2)將剩余的集裝箱裝上第二艘輪USTCmaxmaxwixii1s.t.wixic1ixi{0,1},1innwinUSTCvoidbacktrack(inti)//搜索第i{if(in)//r-=if(cww[i]c)x[i]=cw+=backtrack(i+cw-= if(cwrbestw){//x[i]=backtrack(i+ r+=

USTCn個(gè)作業(yè)的集合{J1,J2,…,Jn}1處理，然后由機(jī)器2處理所有作業(yè)在機(jī)器2上完成處理時(shí)間和稱為該nnfF2ii1USTC機(jī)器機(jī)器作業(yè)2131作業(yè)23它們所相應(yīng)的完成時(shí)間和分別是USTC{if(i>n)for(intj=1;j<=n;bestx[j]=bestf= for(intj=i;j<=n;j++)if(f<bestf)Swap(x[i],Swap(x[i], f1-f- 21.friendFlow(int**,int,int //各作業(yè)所需的處理時(shí)//當(dāng)前作業(yè)調(diào)//當(dāng)前最優(yōu)作業(yè)調(diào)//機(jī)器2完成處理時(shí)//機(jī)器1完成處理時(shí)13.USTC14個(gè)“14個(gè)“組成的符號(hào)三角形，2號(hào)下面都是“+”，2個(gè)異號(hào)下面都是“n個(gè)符號(hào)n，計(jì)算有多少個(gè)不同“+”和“-”的n個(gè)符號(hào)n，計(jì)算有多少個(gè)不同“+”和“-”的個(gè)數(shù)相同 +USTC可行性約束函數(shù)：當(dāng)前符號(hào)三角形所包含的“個(gè)數(shù)與“-”n*(n+1)/4無解的判斷：n*(n+1)/2 +USTC{if((count>half)||(t*(t-1)/2-count>half))if(t>n)for(inti=0;i<2;i++)for(intj=2;j<=t;j++)p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-count+=p[j][t- for(intcount-=p[j][t-count- 18.

計(jì)算可行性約束需O(n時(shí)間，在情況下有為O(n2n)USTCn在n×n格的棋盤上放置彼此不受的n個(gè)皇后（按照國(guó)際線上的棋子）。nn×n格的棋盤上n個(gè)12345678QQQQQQQ1234678USTCn解向量：(x1x2ixi列顯約束：xi=1,2,不同列：xi

boolQueen::Place(int{for(intreturn voidQueen::Backtrack(int{if(t>n)for(inti=1;i<=n;i++)if(Place(t)) USTC{Typewcleftccw;//Typepb=//while(i<=n&&w[i]<=cleft)cleft-=b+=p[i];}if(i<=n)b+=p[i]/w[i]*cleft;returnb;15.nirUSTC團(tuán)UG的完全子G的最大團(tuán)是指G中所含頂點(diǎn)數(shù)最多的UV且對(duì)任意u,vU有(u,v)E，則UG的空子G的最大獨(dú)立集是G中所含頂點(diǎn)數(shù)最多的獨(dú)立USTCV1=V(u,v)E1當(dāng)且僅當(dāng)UUGUG1231234512345USTCvoidClique::Backtrack(int{//計(jì)算最大if(in)到達(dá)葉結(jié)for(intj=1;j<=n;j++)bestx[j]=x[j];bestn=cn; 檢查頂點(diǎn)i與當(dāng)前團(tuán)的連intOK=for(intj=1;j<i;if(x[j]&&a[i][j]==0)//i與j不相連OK0;break;}ifOK進(jìn)入左子樹x[i]=1;cn++;x[i]=0;cn--;}if(cnnibestn進(jìn)入右子x[i]=}}上界函數(shù)：有足夠多的可選擇頂大的1212345復(fù)雜度分需的計(jì)算時(shí)間顯然為O(n2n)USTC到一個(gè)更精確的上界函數(shù)，若cn+Si<=max則剪枝屬于找到的團(tuán)，此時(shí)有Si=Si+1+1，否則USTC的 是圖的m可 若一個(gè)圖最少需要m種顏色才能使圖中每條邊連接的2個(gè)頂點(diǎn)著不同顏色，則稱這個(gè)數(shù)m為該圖的色數(shù) 四色猜USTC的 USTCvoidColor::Backtrack(intvoidColor::Backtrack(int{if(t>n)for(inti=1;i<=n;cout<<x[i]<<'cout<< for(inti=1;i<=m;i++)if(Ok(t)) 14.boolColor::Ok(int{//檢查顏色可用for(intreturn}復(fù)雜度分圖m 問題的解空間樹中內(nèi)點(diǎn)個(gè)數(shù) 對(duì)于每一個(gè)內(nèi)結(jié)點(diǎn)，在情況，用Ok檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的每一USTCtemplate<classvoidTraveling<Type>::Backtrack(int{//獲得一個(gè)排if(i==n)if(a[x[n-1]][x[n]]!=NoEdge&&a[x[n]][1]!=NoEdge(cca[x[n-1]][x[na[x[n]][1bestc||bestcNoEdge)){//當(dāng)前排列更for(intj=1;j<=n;j++)bestx[j]=bestc=cc+a[x[n-1]][x[n]]+ else{//繼續(xù)遞for(intj=i;j<=n;//是否可進(jìn)入x[j]子樹(cca[x[i-1]][x[ibestc||bestcNoEdge可能有更優(yōu)解，搜索子Swap(x[i], 22.

cc-=a[x[i-Swap(x[i],

復(fù)雜度分算法backtrack 情況下可能需要更當(dāng)前O((n-1次，每次更新bestx需計(jì)算時(shí)間O(n)，從而整個(gè)算法的計(jì)算時(shí)間復(fù)雜性為USTC圓排列問題要求從n個(gè)圓的所有排列中找出有最小長(zhǎng)度的圓排2 2 USTCvoidvoidCircle::Backtrack(int{if(t>n)for(intj=t;j<=n;j++)Swap(r[t],float Swap(r[t], 14.floatCircle::Center(intfloatfloatif(valuex>temp) return 2.2.{//計(jì)算當(dāng)前圓排列的長(zhǎng)floatlow=0,high=0;for(inti=1;i<=n;i++){ifx[i]+r[i]>high)high=x[i]+r[i后端}}由于算法backtrack 情況下可能需要計(jì)算O(n!)次當(dāng)前圓排)為O((n+1)!)USTC 了n種不同面值的郵票，并且規(guī)定每張信封上最多只允許貼m張郵票的最佳設(shè)計(jì)——11開始，增量1的170USTC約定它們從小到大排x[1]=1是唯一的選已選定x[1:i-1]，最大連續(xù)郵資區(qū)間是接下來x[i]的可取值范圍是[x[i-USTC考慮到直接遞歸的求解復(fù)雜度太高，我們嘗試計(jì)算用不超過m張mmUSTC

1212213∞121∞∞∞ ??10??11for(intj=0;j<=x[i-2]*