算法設(shè)計(jì)復(fù)習(xí)資料

遞歸：直接或間接的調(diào)用自身算法稱為遞歸算法；用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)。分治法的設(shè)計(jì)思想是，將一個難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個擊破，分而治之。分治法（divide-and-conquer）的基本思想：A分割成k個更小規(guī)模的子問題。B對這k個子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為k個子問題，如此遞歸的進(jìn)行下去，直到問題規(guī)模足夠小，很容易求出其解為止。C將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。設(shè)計(jì)動態(tài)規(guī)劃算法的步驟（1）找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。（2）遞歸地定義最優(yōu)值。（3）以自底向上的方式計(jì)算出最優(yōu)值。（4）根據(jù)計(jì)算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。最優(yōu)子結(jié)構(gòu)性質(zhì)：矩陣連乘計(jì)算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。遞歸算法求解問題時，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計(jì)算多次。這種性質(zhì)稱為子問題的重疊性質(zhì)貪心算法：貪心算法總是作出在當(dāng)前看來最好的選擇，它并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。活動安排問題就是要在所給的活動集合中選出最大的相容活動子集合，是可以用貪心算法有效求解的很好例子。貪心算法：貪心算法求解的這類問題一般具有2個重要的性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達(dá)到。當(dāng)一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)貪心算法與動態(tài)規(guī)劃算法的差異：貪心算法和動態(tài)規(guī)劃算法都要求問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，這是2類算法的一個共同點(diǎn)。動態(tài)規(guī)劃算法通常以自底向上的方式解各子問題，而貪心算法則通常以自頂向下的方式進(jìn)行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。0-1背包問題：給定n種物品和一個背包。物品i的重量是Wi,其價值為Vi,背包的容量為C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大？單源最短路徑基本思想是，設(shè)置頂點(diǎn)集合S并不斷地作貪心選擇來擴(kuò)充這個集合。一個頂點(diǎn)屬于集合S當(dāng)且僅當(dāng)從源到該頂點(diǎn)的最短路徑長度已知。初始時，S中僅含有源。設(shè)u是G的某一個頂點(diǎn)，把從源到u且中間只經(jīng)過S中頂點(diǎn)的路稱為從源到u的特殊路徑，并用數(shù)組dist記錄當(dāng)前每個頂點(diǎn)所對應(yīng)的最短特殊路徑長度。Dijkstra算法每次從V-S中取出具有最短特殊路長度的頂點(diǎn)u,將u添加到S中，同時對數(shù)組dist作必要的修改。一旦S包含了所有V中頂點(diǎn)，dist就記錄了從源到所有其它頂點(diǎn)之間的最短路徑長度?；厮莘ǖ幕舅枷耄海?）針對所給問題，定義問題的解空間；（2）確定易于搜索的解空間結(jié)構(gòu)；（3）以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。常見的兩種分支限界法：（1）隊(duì)列式（FIFO）分支限界法。按照隊(duì)列先進(jìn)先出（FIFO）原則選取下一個節(jié)點(diǎn)為擴(kuò)展節(jié)點(diǎn)。（2）優(yōu)先隊(duì)列式分支限界法。按照優(yōu)先隊(duì)列中規(guī)定的優(yōu)先級選取優(yōu)先級最高的節(jié)點(diǎn)成為當(dāng)前擴(kuò)展節(jié)點(diǎn)。布線問題算法思想：解此問題的隊(duì)列式分支限界法從起始位置a開始將它作為第一個擴(kuò)展結(jié)點(diǎn)。與該擴(kuò)展結(jié)點(diǎn)相鄰并且可達(dá)的方格成為可行結(jié)點(diǎn)被加入到活結(jié)點(diǎn)隊(duì)列中，并且將這些方格標(biāo)記為1，即從起始方格a到這些方格的距離為1。接著，算法從活結(jié)點(diǎn)隊(duì)列中取出隊(duì)首結(jié)點(diǎn)作為下一個擴(kuò)展結(jié)點(diǎn)，并將與當(dāng)前擴(kuò)展結(jié)點(diǎn)相鄰且未標(biāo)記過的方格標(biāo)記為2,并存入活結(jié)點(diǎn)隊(duì)列。這個過程一直繼續(xù)到算法搜索到目標(biāo)方格b或活結(jié)點(diǎn)隊(duì)列為空時為止。即加入剪枝的廣度優(yōu)先搜索。隨機(jī)存儲機(jī)RAM它描述的形式計(jì)算機(jī)是一臺帶累加器計(jì)算機(jī)，他不允許程序修改其自身，RAM由只讀輸入帶、只寫輸入帶、程序存儲部件、內(nèi)存儲器和指令計(jì)數(shù)器5個部分組成。P類和NP類語言的定義P={L|L是一個能在多項(xiàng)式時間內(nèi)被一臺DTM所接受的一眼}NP+{L|L是一個能在多項(xiàng)式時間內(nèi)被一臺NDTM所接受的語言}由于一臺確定性圖靈機(jī)可看作是非確定性圖靈機(jī)的特例，所以可在多項(xiàng)式時間內(nèi)被非確定性圖靈機(jī)接受。故P屬于NPP類問題:是確定性計(jì)算模型下的易解問題類。NP類問題：是非確定性計(jì)算模型下的易驗(yàn)證問題類。NP完全類問題：即多項(xiàng)式復(fù)雜度的非確定性問題類；簡單的寫法是NP=P?問題就在這個問號上，到底是NP等于P,還是NP不等于P。算法的漸進(jìn)時間復(fù)雜性的含義？答：當(dāng)問題的規(guī)模n趨向無窮大時，影響算法效率的重要因素是T(n)的數(shù)量級，而其他因素僅是使時間復(fù)雜度相差常數(shù)倍，因此可以用T(n)的數(shù)量級(階)評價算法。時間復(fù)雜度T(n)的數(shù)量級(階)稱為漸進(jìn)時間復(fù)雜性。最壞情況下的時間復(fù)雜性和平均時間復(fù)雜性有什么不同？答：最壞情況下的時間復(fù)雜性和平均時間復(fù)雜性考察的是n固定時，不同輸入實(shí)例下的算法所耗時間。最壞情況下的時間復(fù)雜性取的輸入實(shí)例中最大的時間復(fù)雜度：W(n)=max{T(n，I)},lUDnA(n)=EP(l)T(n，I)lUDn平均時間復(fù)雜性是所有輸入實(shí)例的處理時間與各自概率的乘積和：釆用回溯法求解的問題，其解如何表示？有什么規(guī)定？問題的解可以表示為n元組：(x,x, x)，xeS,S為有窮集合，xeS, (x,x, x)具備1 2 n i ii i i 1 2 n完備性，即(x,x, X)是合理的，貝I」(x,x, x)(i〈n)—定合理。12 n 12 i簡述漸進(jìn)時間復(fù)雜性上界的定義。T(n)是某算法的時間復(fù)雜性函數(shù)，f(n)是一簡單函數(shù)，存在正整數(shù)No和C，n〉No，有T(n)〈f(n)，這種關(guān)系記作T(n)=0(f(n))?？焖倥判虻幕舅枷胧鞘裁础？焖倥判虻幕舅枷胧窃诖判虻腘個記錄中任意取一個記錄，把該記錄放在最終位置后，數(shù)據(jù)序列被此記錄分成兩部分。所有關(guān)鍵字比該記錄關(guān)鍵字小的放在前一部分，所有比它大的放置在后一部分，并把該記錄排在這兩部分的中間，這個過程稱作一次快速排序。之后重復(fù)上述過程，直到每一部分內(nèi)只有一個記錄為止。什么是直接遞歸和間接遞歸？消除遞歸一般要用到什么數(shù)據(jù)結(jié)構(gòu)？在定義一個過程或者函數(shù)的時候又出現(xiàn)了調(diào)用本過程或者函數(shù)的成分，既調(diào)用它自己本身，這稱為直接遞歸。如果過程或者函數(shù)P調(diào)用過程或者函數(shù)Q，Q又調(diào)用P,這個稱為間接遞歸。消除遞歸一般要用到棧這種數(shù)據(jù)結(jié)構(gòu)。哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。其壓縮率通常在20%?90%之間。哈夫曼編碼算法用字符在文件中出現(xiàn)的頻率表來建立一個用0，1串表示各字符的最優(yōu)表示方式。前綴碼：對每一個字符規(guī)定一個0,1串作為其代碼，并要求任一字符的代碼都不是其他字符代碼的前綴。二、遞歸與分治：二分搜索算法：publicstaticintbinarySearch(inta[],intx,intn){left二0; right二n-1;while(left<=right){intmiddle=(left+right)/2;if(x==a[middle])returnmiddle;if(x>a[middle])left二middle+1;elseright二middle-1;}return-1; }棋盤覆蓋publicvoidchessBoard(inttr,inttc,intdr,intdc,intsize){if(size==1)return;intt二tile++.s=size/2;if(dr<tr+s&&de<tc+s)chessBoard(tr,tc,dr,de,s);else{board]tr+s-l][tc+s-1]=t;chessBoard(tr,tc,tr+sT,tc+sT,s);}if(dr<tr+s&&dc>=tc+s)chessBoard(tr,tc+s,dr,dc,s);else{ board[tr+s-l][tc+s]=t;chessBoard(tr,tc+s,tr+sT,tc+s,s);}if(dr>=tr+s&&dc<tc+s)chessBoard(tr+s,tc,dr,dc,s);else{ board[tr+s][tc+s-1]=t;chessBoard(tr+s,tc,tr+s,tc+sT,s);}if(dr>=tr+s&&dc>=tc+s)chessBoard(tr+s,tc+s,dr,dc,s);else{ board[tr+s][tc+s]=t;chessBoard(tr+s,tc+s,tr+s,tc+s,s);}}三、動態(tài)規(guī)劃最長公共子序列voidLCSLength(intm,intn,char[]x,char[]y,int[][]c,int[][]b){inti,j;TOC\o"1-5"\h\zfor(i= 1; i <=m; i++)c[i][0] = 0;for (i = 1; i <= n; i++) c[0][i] =0;for (i = 1; i <= m; i++)for (j = 1; j <= n; j++) {if(x[i]==y[j]){ c[i][j]=c[i-l][j-l]+l;b[i][j]=1;}elseif(c[iT][j]〉=c[i][j—l]){ c[i][j]=c[iT][j];b[i][j]=2;}else{c[i][j]=c[i][j—1];b[i][j]=3;} } }構(gòu)造最長公共子序列voidLCS(inti,intj,char*x,int**b){if(i==0||j==0)return;if(b[i][j]==1){LCS(i—1,j—1,x,b);cout〈〈x[i];}elseif(b[i][j]==2)LCS(iT,j,x,b);elseLCS(i,j—1,x,b); }最優(yōu)裝載voidLoading(intx[],Typew[],Typec,intn){int*t二newint[n+1];Sort(w,t,n);for(inti二1;i〈二n;i++)x[i]=0;for(inti二1;i〈二n&&w[t[i]]〈二c;i++){x[t[i]]=1;c—二w[t[i]];}}五、回溯法裝載問題voidbacktrack(inti){if(i>n)r—二w[i];if(cw+w[i]〈二c){x[i]=1;cw+=w[i];backtrack(i+1);cw-=w[i]; }if(cw+r>bestw) {x[i]=0; backtrack(i+1); }r+=w[i];}批處理問題：voidFlowshop::Backtrack(inti){if(i>n){for(intj=1;j<=n;j++)bestx[j]=x[j];bestf二f;}elsefor(intj二i;j〈二n;j++){f1+=M[x[j]][1];f2[i]=((f2[i-1]〉f1)?f2[i-1]:f1)+M[x[j]][2];f+=f2[i];if(f<bestf){Swap(x[i],x[j]);Backtrack(i+1);Swap(x[i],x[j]);} f1-=M[x[j]][1];f-=f2[i];}}六、分支限界法單源最短路徑問題while(true){for(intj=1;j<=n;j++)if((c[E.i][j]〈inf)&&(E.length+c[E.i][j]〈dist[j])){//頂點(diǎn)i到頂點(diǎn)j可達(dá)，且滿足控制約束dist[j]=E.length+c[E.i][j];prev[j]=E.i;MinHeapNode〈Type〉N;N.i=j;N.length二dist[j];H.Insert(N);}try{H.DeleteMin(E);}catch(OutOfBounds){break;} }}求證：O(f(n))+O(g(n))=O(max{f(n),g(n)})。證明：對于任意f1(n)eO(f(n))，存在正常數(shù)cl和自然數(shù)nl,使得對所有n>n1，有f1(n)<clf(n)。類似地，對于任意gl(n)eO(g(n))，存在正常數(shù)c2和自然數(shù)n2，使得對所有n>n2，有g(shù)l(n)<c2g(n)。令c3=max{cl,c2}，n3=max{nl,n2}，h(n)=max{f(n),g(n)}。則對所有的n>n3，有fl(n)+gl(n)<clf(n)+c2g(n)<c3f(n)+c3g(n)=c3(f(n)+g(n))

<c32max{f(n),g(n)}=2c3h(n)=O(max{f(n),g(n)}).裝載問題貪心算法的證明比如所你是按每次裝入重量最小的作為貪心的選擇，那么設(shè)重量從小到大(x1,x2,...,xn)是最優(yōu)裝載問題的一個最優(yōu)解。設(shè)k=min{i|xi=1}.當(dāng)k=1的時候(x1,x2,...,xn)是一個滿足貪心性質(zhì)的最優(yōu)解。當(dāng)k>1，令y=1，yk=O,yi=xi,i不等于k,那么yi與對應(yīng)重量wi的乘積的和=w1-wk+wixi乘積的和，這個是小于等于本身wi*xi乘積的和的，小于容量c因此，(y1,y2,...,yn)也是最優(yōu)裝載問題的可行解。然而，xi的和與yi的和是相等的，也就是說，(y1,y2,...,yn)也是滿組貪心性質(zhì)的最優(yōu)解。矛盾。7.最長公共子序列問題：給定2個序列X二{xl,x2,…,xm}和Y二{yl,y2,…,yn}，找出X和Y的最長公共子序列。由最長公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關(guān)系。用

]記錄序列Xi和YJ的最長公共子序列的長度。其中，Xi={xl,x2,…,xi}；Yj二{yl,y2,…,yj}。當(dāng)i=0或j=0時，空序列是Xi和YJ的最長公共子序列。故此時C[i][j]=0o其它情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下：' 0 i=0,j=0c[i][j]=< c[i-l][j—1]+1 i,j>0；x=yijmax{c[i][j-1],c[i-1][j]}i,j>0;x豐yJ ij在程序中，b[i][j]記錄C[i][j]的值是由哪一個子問題的解得到的。請?zhí)顚懗绦蛑械目崭?，以使函?shù)LCSLength完成計(jì)算最優(yōu)值的功能。voidLCSLength(intm,voidLCSLength(intm,intn,char*x,char*y,int**c,int**b)inti,j;for(i=1;i<=m;i++)c[i][0]for(i=1;i<=n;i++)c[0][i]for(i=1;i<=m;i++)for(j=1::j<=n;j++){=0;=0;if(x[i]==y[j]){c[i][j]=c[i-l][j-l]+l;b[i][j]=l;}elseif(c[i-l][j]>=c[i][j-l]){c[i][j]=c[i-l][j];b[i][j]=2;}else{c[i][j]=c[i][j-l];b[i][j]=3;}}(1)函數(shù)LCS實(shí)現(xiàn)根據(jù)b的內(nèi)容打印出Xi和Yj的最長公共子序列。請?zhí)顚懗绦蛑械目崭?，以使函?shù)LCS完成構(gòu)造最長公共子序列的功能(請將b[i][j]的取值與(1)中您填寫的取值對應(yīng)，否則視為錯誤)。voidLCS(inti，intj，char*x,int**b){if(i==0||j==0)return;if(b[i][j]==1){LCS(i-1,j-1，x，b);cout<<x[i];}elseif(b[i][j]==2)LCS(iT,j，x，b);elseLCS(i，j-1，x，b);}1、⑴原理：在對問題求解時，總是做出在當(dāng)前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)I貪心算法不是對所有問題都能得到整體最優(yōu)解，但對范圍相當(dāng)廣泛的許多問題他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。(2)特性：貪心算法采用自頂向下，以迭代的方法做出相繼的貪心選擇，每做一次貪心選擇就將所求問題簡化為一個規(guī)模更小的子問題，通過每一步貪心選擇，可得到問題的一個最優(yōu)解，雖然每一步上都要保證能獲得局部最優(yōu)解，但由此產(chǎn)生的全局解有時不一定是最優(yōu)的，所以貪婪法不要回溯。能夠用貪心算法求解的問題一般具有兩個重要特性：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。貪心選擇性質(zhì)所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達(dá)到。這是貪心算法可行的第一個基本要素。貪心算法則通常以自頂向下的方式進(jìn)行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。對于一個具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問題的整體最優(yōu)解。證明的大致過程為：首先考察問題的一個整體最優(yōu)解，并證明可修改這個最優(yōu)解，使其以貪心選擇開始。做了貪心選擇后，原問題簡化為規(guī)模更小的類似子問題。然后用數(shù)學(xué)歸納法證明通過每一步做貪心選擇，最終可得到問題的整體最優(yōu)解。其中，證明貪心選擇后的問題簡化為規(guī)模更小的類似子問題的關(guān)鍵在于利用該問題的最優(yōu)子結(jié)構(gòu)性質(zhì)刃最優(yōu)子結(jié)構(gòu)性質(zhì)當(dāng)一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。⑶貪心算法與動態(tài)規(guī)劃算法的差異動態(tài)規(guī)劃和貪心算法都是一種遞推算法，均有最優(yōu)子結(jié)構(gòu)性質(zhì)，通過局部最優(yōu)解來推導(dǎo)全局最優(yōu)解。兩者之間的區(qū)別在于：貪心算法中作出的每步貪心決策都無法改變，因?yàn)樨澬牟呗允怯缮弦徊降淖顑?yōu)解推導(dǎo)下一步的最優(yōu)解，而上一部之前的最優(yōu)解則不作保留，貪心算法每一步的最優(yōu)解一定包含上一步的最優(yōu)解。動態(tài)規(guī)劃算法中全局最優(yōu)解中一定包含某個局部最優(yōu)解，但不一定包含前一個局部最優(yōu)解，因此需要記錄之前的所有最優(yōu)解。閻基本思路：1） 建立數(shù)學(xué)模型來描述問題。2） 把求解的問題分成若干個子問題。3） 對每一子問題求解，得到子問題的局部最優(yōu)解。4） 把子問題的解局部最優(yōu)解合成原來解問題的一個解。2、活動安排問題活動安排問題就是要在所給的活動集合中選出最大的相容活動子集合，是可以用貪心算法有效求解的很好例子。該問題要求高效地安排一系列爭用某一公共資源的活動。貪心算法提供了一個簡單、漂亮的方法使得盡可能多的活動能兼容地使用公共資源。問題描述T設(shè)有n個活動的集合E={1,2,…,n},其中每個活動都要求使用同一資源,如演講會場等，而在同一時間內(nèi)只有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間si和一個結(jié)束時間fi,且si<fio如果選擇了活動i,則它在半開時間區(qū)間［si,fi）內(nèi)占用資源。若區(qū)間［si,fi）與區(qū)間［sj,fj）不相交，則稱活動i與活動j是相容的。也就是說，當(dāng)si^fj或sj^fi時，活動i與活動j相容?；顒影才艈栴}就是要在所給的活動集合中選出最大的相容活動子集合。求解思路：將活動按照結(jié)束時間進(jìn)行從小到大排序。然后用i代表第i個活動，s［i］代表第i個活動開始時間，f［i］代表第i個活動的結(jié)束時間。按照從小到大排序,挑選出結(jié)束時間盡量早的活動，并且滿足后一個活動的起始時間晚于前一個活動的結(jié)束時間，全部找出這些活動就是最大的相容活動子集合。事實(shí)上系統(tǒng)一次檢查活動i是否與當(dāng)前已選擇的所有活動相容。若相容活動i加入已選擇活動的集合中，否則，不選擇活動i,而繼續(xù)下一活動與集合A中活動的相容性。若活動i與之相容，則i成為最近加入集合A的活動，并取代活動j的位置。下面給出求解活動安排問題的貪心算法，各活動的起始時間和結(jié)束時間存儲于數(shù)組s和f中，且按結(jié)束時間的非減序排列。如果所給的活動未按此序排列，可以用O（nlogn）的時間重排。具體代碼如下：〃4dl活動安排問題貪心算法#include"stdafx.h"#includeviostream>usingnamespacestd;templatevclassType〉voidGreedySelector(intn,Types[],Typef[],boolA[]);constintN=11;intmain(){〃下標(biāo)從1開始，存儲活動開始時間ints[]={0,1,3,0,5,3,5,6,8,8,2,12};〃下標(biāo)從1開始，存儲活動結(jié)束時間intf[]={0,4,5,6,7,8,9,10,11,12,13,14};boolA[N+1];coutvv"各活動的開始時間，結(jié)束時間分別為："vvendl;for(inti=1;iv=N;i++){coutv<"["<<ivv"]:"vv"("vvs[i]vv","vvf[i]vv")"vvendl;}GreedySelector(N,s,f,A);coutvv"最大相容活動子集為："vvendl;for(inti=1;iv=N;i++){if(A[i]){coutvv"["vvivv"]:"vv"("vvs[i]vv","vvf[i]vv")"vvendl;}}return0;}templatevclassType>voidGreedySelector(intn,Types[],Typef[],boolA[]){A[1]=true;intj=1;〃記錄最近一次加入A中的活動for(inti=2;iv=n;i++)〃依次檢查活動i是否與當(dāng)前已選擇的活動相容{if(s[i]>=f[j]){A[i]=true;j=i；}else{A[i]=false;}}}回溯法分配工作#includevstdio.h>#includevmath.h>/*名稱：swap功能：交換兩個整數(shù)輸入：輸出：作者：劉榮時間：2013/5/17備注：*/voidswap(int&x,int&y){inttemp=x;x=y;y=temp;}/*名稱：next功能：遞歸求解最優(yōu)方案輸入：輸出：作者：劉榮時間：2013/5/17備注:*/voidnext(inti,intn,intc[][3],int*x,int&bestv,int*bestx){intj,v;if(i>n)〃到達(dá)葉子節(jié)點(diǎn){v=0;for(intk=l;k<=n;k++){v+=c[k-1][x[k-1]];}if(v<bestv){bestv=v;for(intk=1;k<=n;k++){bestx[k-1]=x[k-1];〃記錄下最有方案}}return;}〃組合排列for(j=i;j<=n;j++){swap(x[i-1],x[j-1]);next(i+1,n,c,x,bestv,bestx);swap(x[i-1],x[j-1]);}}/*名稱：solve功能：開始求解，包括初始化輸入：輸出：作者：劉榮時間：2013/5/17備注:*/voidsolve(intn,intc[][3],int*bestx,int&bestv){inti;int*x=newint[n];for(i=1;i<=n;i++){x[i-1]=i-1;}bestv=0;for(i=1;i<=n;i++){bestv+=c[i-l][i-l];}next(1,n,c,x,bestv,bestx);}intmain(){intn=3;intc[][3]={{10,2,3},{2,3,4},{3,4,5}};int*bestx=newint[n];intbestv=0;solve(n,c,bestx,bestv);printf("最優(yōu)工作安排的時間:％d\n\r",bestv);printf(”最優(yōu)工作安排：\n\r");for(inti=1;i<=n;i++){printf("工作％小:第％小個人，”,i,bestx[i-1]+1);}return0;亙溯法對艇空間作深度優(yōu)先搜索，因此，在一般情況下用遞歸方法實(shí)現(xiàn)叵溯法[cpp]口面01.voidbackt-ack(intt)02?03.if(t>n)04.CUtpLlt(K)；"已到葉子結(jié)點(diǎn)，輸出結(jié)果阪else06.for(inti=f(n^t);i<=g(njt);i++){尊廠x[t]=h(i);if(ccn5t-aint(t)&.aboLind(t))backt-ack(t+l);10.>11.}f(n,t),g(n;t):表示芻前擴(kuò)展結(jié)點(diǎn)處未搜索過的子樹的起始編虧和終止編號h(i)：表袞在芻前擴(kuò)展結(jié)點(diǎn)處刈t］的第i個可選值；迭找回濛:采用樹的非遞歸深度憂先遍歷算法，可將回溯法表看為一個非遞歸迭代過程:[cpp]B③02.03.64.05.06.&7.施.02.03.64.05.06.&7.施.09.10.intt=l;while(t>0)-[if(f(nJt)<=g(nJt))for(inti=f(n±t};i<=gtn±t};i++}■[x[t]=h(i);if(constraint(t>fi&baund(t}}{if(solution(t>)output(x);elset++;4.15.子集松芻所給的問題是城門個元素的集合S豐找Hi?己某種性質(zhì)的子集時，相應(yīng)的解空間稱為子集如例如，那個物品的CM背包問題所相應(yīng)的解空間樹就是一顆子集樹：迄類子集問題通常有2餉個葉節(jié)點(diǎn)，其節(jié)點(diǎn)總個數(shù)為2A(n+1)-1.遍歷子集樹的任何算法均需要0(才n)的計(jì)算時間：01.02.01.02.03.@4.05.06.07.08.09.用回溯法遍歷子集樹的一般算法可描述如下:[cpp]口?voidbacktrack,(intt){if(t>n)output(x);elsefor(inti=0;i<=l;i++){if(legal(t))backtrack(t+]L);}排列孫當(dāng)所紿問題是確定n個元素滿足杲種性質(zhì)的排列時，相應(yīng)的解空間樹稱為切松排列樹適常有n!個葉子節(jié)點(diǎn).因此遍歷排列樹需要0(n!)的計(jì)算時間.01.01.02.03.04.05.06.07.08.09.何用回溯法遍歷排列樹的一般算法可描述如下:[cpp]口③voidbacktrack(intt){if(t>n)output(x);elsefor(inti=t;i<=n;i++){swap(x[t]±x[i]);if(legal(t))backtra匚k(1:+]L);swap(x[t]±x[i]);迭代回溯算法設(shè)計(jì):用回溯法解裝載問題時，用子集樹表示其解空間顯然是最合適的。用可科VWiXi<Cl行性約束函數(shù)可剪去不滿足約束條件二 的子樹。在子集樹的第j+1乞yvxi層的結(jié)點(diǎn)z處，用CW記當(dāng)前的裝載重量，即cw==，則當(dāng)cw>c1時，以結(jié)點(diǎn)z為根的子樹中所有結(jié)點(diǎn)都不滿足約束條件，因而該子樹中的解均為不可行解，故可將該子樹剪去。(該約束函數(shù)去除不可行解，得到所有可行)?？梢砸胍粋€上界函數(shù)，用于剪去不含最優(yōu)解的子樹從而改進(jìn)算法在平均情況下的運(yùn)行效率。設(shè)z是解空間樹第i層上的當(dāng)前擴(kuò)展結(jié)點(diǎn)。cw是當(dāng)前載重量；bestw是當(dāng)前最優(yōu)載重量；r是剩余集裝箱的重量，即r=「」 。定義上界函數(shù)為cw+r。在以z為根的子樹中任一葉結(jié)點(diǎn)所相應(yīng)的載重量均不超過cw+r。因此，當(dāng)cw+r<=bestw時，可將z的右子樹剪去。#include"stdafx.h"#includeviostream>usingnamespacestd;templatevclassType〉TypeMaxLoading(Typew[],Typec,intn,intbestx[]);intmain(){intn=3,m;intc=50,c2=50;intw[4]={0,10,40,40};intbestx[4];m=MaxLoading(w,c,n,bestx);coutvv"輪船的載重量分別為："vvendl;coutvv"c(l)="vvcvv",c(2)="vvc2vvendl;coutvv"待裝集裝箱重量分別為："vvendl;coutvv"w(i)=";for(inti=1;iv=n;i++){coutvvw[i]vv"";}coutvvendl;coutvv"回溯選擇結(jié)果