算法設計與分析期末試題考試版

算法設計與分析期末試題考試版1、用計算機求解問題的步驟：1、問題分析2、數(shù)學模型建立3、算法設計與選擇4、算法指標5、算法分析6、算法實現(xiàn)7、程序調試8、結果整理文檔編制2、算法定義：算法是指在解決問題時，按照某種機械步驟一定可以得到問題結果的處理過程3、算法的三要素1、操作2、控制結構3、數(shù)據(jù)結構算法具有以下5個屬性：有窮性：確定性：可行性：輸入：輸出：算法設計的質量指標：正確性：算法應滿足具體問題的需求；可讀性：算法應該好讀，以有利于讀者對程序的理解；健壯性：算法應具有容錯處理，當輸入為非法數(shù)據(jù)時，算法應對其作出反應，而不是產(chǎn)生莫名其妙的輸出結果。效率與存儲量需求：效率指的是算法執(zhí)行的時間；存儲量需求指算法執(zhí)行過程中所需要的最大存儲空間。一般這兩者與問題的規(guī)模有關。1/26算法設計與分析期末試題考試版復雜性的漸近性態(tài)設T(N是算法A的復雜性函數(shù)，使得當NRs時有:(T(N)-丁(N)/T(N-0那么，我們就說丁(N)是T(N)當NRs時的漸近性態(tài)，或叫T(N)為算法A當NRs的漸近復雜性而與T(N)相區(qū)別。4=碼心JTEL5殲3J白近似算法的基本思想是用近似最優(yōu)解代替最優(yōu)解，以換取算法設計上的簡化和時間且雜性的降低」近似算法是這樣一個過程：雖然它可能找不到一個最優(yōu)解，但它總會為行求解的問題提供個解。為了具有實用性，近似算法必須能夠給出算法所產(chǎn)生的解可最優(yōu)解之間的差別或者比例的一個界限?它保證任意一個實例的近似最優(yōu)解與最優(yōu)解之間相差的程度口顯然，這個差別越小，近似算法越具有實用性.P=NP經(jīng)常采用的算法主要有迭代法、分而治之法、貪婪法、動態(tài)規(guī)劃法、回溯法、分支限界法分而治之法1、基本思想將一個難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個擊破，分而治之。分治法所能解決的問題一般具有以下幾個特征：2/26算法設計與分析期末試題考試版(1)該問題的規(guī)?？s小到一定的程度就可以容易地解決；(2)該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結構性質；(3)利用該問題分解出的子問題的解可以合并為該問題的解;(4)該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子子問題。3、分治法的基本步驟(1)分解：將原問題分解為若干個規(guī)模較小，相互獨立，與原問題形式相同的子問題；(2)解決：若子問題規(guī)模較小而容易被解決則直接解，否則遞歸地解各個子問題；(3)合并：將各個子問題的解合并為原問題的解。遞歸：直接或間接的調用自身的算法、叫做遞歸算法。1■期盤覆蓋用分治策略，可以設計解棋盤問題的一個簡捷的算法。當k>0時，將2"*2Ak棋盤分割為4個2A(k-1)*2A(k-1) 子棋盤特殊方格必位于4個較小子棋盤之一中，其余3個子棋盤中無特殊方格。為了將這3個無特殊方格的子棋盤轉化為特殊棋盤，我們可以用一個L型骨牌覆蓋這3個較小的棋盤的匯合處，如下圖所示，這3個子棋盤上被L型骨牌覆蓋的方格就成為該棋盤上的特殊方格，從而將原問題化為4個較小規(guī)模的棋盤覆蓋問題。遞歸的使用這種分割，直至棋盤簡化為1x1棋盤。2?合并排序合并排序，顧名思義，就是通過將兩個有序的序列合并為一個大的有序的序列的方式來實現(xiàn)排序。合并排序是一種典型的分治算法：首先將序列分為兩部分，然后對每一部分進行循環(huán)遞歸的排序，然后3/26算法設計與分析期末試題考試版逐個將結果進行合并。合并排序最大的優(yōu)點是它的時間復雜度為 O(nlgn),這個是我們之前的選擇排序和插入排序所達不到的。他還是一種穩(wěn)定性排序，也就是相等的元素在序列中的相對位置在排序前后不會發(fā)生變化。他的唯一缺點是，需要利用額外的N的空間來進行排序。合并排序依賴于合并操作，即將兩個已經(jīng)排序的序列合并成一個序列，具體的過程如下：申請空間，使其大小為兩個已經(jīng)排序序列之和，然后將待排序數(shù)組復制到該數(shù)組中。設定兩個指針，最初位置分別為兩個已經(jīng)排序序列的起始位置比較復制數(shù)組中兩個指針所指向的元素，選擇相對小的元素放入到原始待排序數(shù)組中，并移動指針到下一位置重復步驟3直到某一指針達到序列尾將另一序列剩下的所有元素直接復制到原始數(shù)組末尾3?快速排序(1)在數(shù)據(jù)集之中，選擇一個元素作為“基準"(pivot)。(2)所有小于“基準”的元素，都移到“基準"的左邊；所有大于"基準"的元素，都移到"基準"的右邊。(3)對"基準"左邊和右邊的兩個子集，不斷重復第一步和第二步，直到所有子集只剩下一個元素為止。(1)快速排序問題設a[0:n-1]是一個未排序的數(shù)組，如｛0,12,45,3,6,29,4,16,77｝。實現(xiàn)快速排序算法對該數(shù)組進行排序。(2)步驟對于輸入的子序列L[p..r]分三步處理：第一步：分解(Divide)先從數(shù)據(jù)序列中選一個元素，稱為基準元素。將序列中所有比基準元素小的元素都放到它的左邊，比基準元素大的元素都放到它的右邊。在序列L[p..r]中選擇基準元素L[q],經(jīng)比較和移動后，L[q]將處于L[p..r]中間的適當位置，使得基準元素L[q]的值大于L[p..q-1]中任一元素的值，基準元素L[q]的值小于L[q+1..r]中任一元素的值。第二步：遞歸求解(Conquer)4/26算法設計與分析期末試題考試版再對左右兩邊分別用同樣的方法處理，直到每一個待處理的序列的長度為 1。通過遞歸調用快速排序算法，分別對 L[p..q-1]和L[q+1..r]進行排序。第三步：合并(Merge)由于對分解出的兩個子序列的排序是就地進行的，所以在 L[p..q-1]和L[q+1..r]都排好序后不需要執(zhí)行任何計算L[p..r]就已排好序，即自然合并。這個解決流程是符合分治法的基本步驟的。貪心算法貪心算法(又稱貪婪算法)是指，在對問題求解時,總是做出在當前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的是在某種意義上的局部 最優(yōu)解。(2)特性：貪心算法采用自頂向下，以迭代的方法做出相繼的貪心選擇，每做一次貪心選擇就將所求問題簡化為一個規(guī)模更小的子問題，通過每一步貪心選擇，可得到問題的一個最優(yōu)解， 雖然每一步上都要保證能獲得局部最優(yōu)解，但由此產(chǎn)生的全局解有時不一定是最優(yōu)的，所以貪婪法不要回溯。能夠用貪心算法求解的問題一般具有兩個重要特性： 貪心選擇性質和最優(yōu)子結構性質(3)貪心算法與動態(tài)規(guī)劃算法的差異：動態(tài)規(guī)劃和貪心算法都是一種遞推算法，均有最優(yōu)子結構性質，通過局部最優(yōu)解來推導全局最優(yōu)解。兩者之間的區(qū)別在于： 貪心算法中作出的每步貪心決策都無法改變，因為貪心策略是由上一步的最優(yōu)解推導下一步的最優(yōu)解， 而上一部之前的最優(yōu)解則不作保留，貪心算法每一步的最優(yōu)解一定包含上一步的最優(yōu)解。 動態(tài)規(guī)劃算法中全局最優(yōu)解中一定包含某個局部最優(yōu)解，但不一定包含前一個局部最優(yōu)解，因此需要記錄之前的所有最優(yōu)解?；顒影才艈栴}由于輸入的活動以其完成時間的非減序排列， 所以算法greedySelector每次總是選擇具有最早完成時間的相容活動加入集合A中。直觀上，按這種方法選擇相容活動為未安排活動留下盡可能多的時間。也就是說，該算法的貪心選擇的意義是使剩余的可安排時間段極大化，以便安排盡可能多的相容活動 。最小生成樹5/26算法設計與分析期末試題考試版Prim算法設6=(V,E)是連通帶權圖，V={1,2,…,n}。構造G的最小生成樹Prim算法的基本思想是：首先置S={1},然后，只要S是V的真子集，就進行如下的貪心選擇：選取滿足條件i6S,j6VS,且c[i][j] 最小的邊，將頂點j添加到S中。這個過程一直進行到S=V時為止。在這個過程中選取到的所有邊恰好構成G的一棵最小生成樹。Kruskal算法給定無向連同帶權圖G=(V,E),V ={1,2，…,n} oKruskal算法構造G的最小生成樹的基本思想是：(1)首先將G的n個頂點看成n個孤立的連通分支。將所有的邊按權從小大排序。(2)從第一條邊開始，依邊權遞增的順序檢查每一條邊。并按照下述方法連接兩個不同的連通分支：當查看到第k條邊(v,w)時，如果端點v和w分別是當前兩個不同的連通分支T1和T2的端點是，就用邊(v,w)將T1和T2連接成一個連通分支，然后繼續(xù)查看第k+1條邊；如果端點v和w在當前的同一個連通分支中，就直接再查看k+1條邊。這個過程一個進行到只剩下一個連通分支時為止。動態(tài)規(guī)劃基本思想：基本思想動態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質的問題。在這類問題中，可能會有許多可行解。每一個解都對應于一個值，我們希望找到具有最優(yōu)值的解。動態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。與分治法不同的是，適合于用動態(tài)規(guī)劃求解的問題，經(jīng)分解得到子問題往往不是互相獨立的。若用分治法來解這類問題，則分解得到的子問題數(shù)目太多，有些子問題被重復計算了很多次。如果我們能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，這樣就可以避免大量的重復計算，節(jié)省時間。我們可以用一個表來記錄所有已解的子問題的答案。不管該子問題以后是否被用到，只要它被計算過，就將其結果填入表中。這就是動態(tài)規(guī)劃法的基本思路。具體的動態(tài)規(guī)劃算法多種多樣，但它們具有相同的填表格式?；静襟E(1)劃分階段：按照問題的時間或空間特征，把問題分為若干個階6/26算法設計與分析期末試題考試版段。注意這若干個階段一定要是有序的或者是可排序的(即無后向性)，否則問題就無法用動態(tài)規(guī)劃求解。(2)選擇狀態(tài)：將問題發(fā)展到各個階段時所處于的各種客觀情況用不同的狀態(tài)表示出來。當然，狀態(tài)的選擇要滿足無后效性。(3)確定決策并寫出狀態(tài)轉移方程：之所以把這兩步放在一起，是因為決策和狀態(tài)轉移有著天然的聯(lián)系，狀態(tài)轉移就是根據(jù)上一階段的狀態(tài)和決策來導出本階段的狀態(tài)。所以，如果我們確定了決策，狀態(tài)轉移方程也就寫出來了。但事實上，我們常常是反過來做，根據(jù)相鄰兩段的各狀態(tài)之間的關系來確定決策。動態(tài)規(guī)劃算法分以下4個步驟：.描述最優(yōu)解的結構.遞歸定義最優(yōu)解的值.按自底向上的方式計算最優(yōu)解的值〃此3步構成動態(tài)規(guī)劃解的基礎。.由計算出的結果構造一個最優(yōu)解?！ù瞬饺绻灰笥嬎阕顑?yōu)解的值時，可省略。好，接下來，咱們討論適合采用動態(tài)規(guī)劃方法的最優(yōu)化問題的倆個要素：最優(yōu)子結構性質，和子問題重疊性質。1?最優(yōu)子結構性簡而言之，一個最優(yōu)化策略的子策略總是最優(yōu)的。一個問題滿足最優(yōu)化原理又稱其具有最優(yōu)子結構性質。2?重疊子問題在遞歸算法自頂向下解決問題時，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復計算了多次。動態(tài)規(guī)劃正是利用這種重疊子問題性質，對每一子問題直解一次，而后將其解保存在一個表格中，當7/26算法設計與分析期末試題考試版每次需要時，只簡單用常數(shù)時間查看一下結果。3?備忘錄方法備忘錄方法是動態(tài)規(guī)劃算法的變形。與動態(tài)規(guī)劃算法一樣，備忘錄方法用表格保存已解決的子問題的答案，在下次需要解此子問題時，只要簡單查看該問題的解答，而不必重新計算。與動態(tài)規(guī)劃算法不同的是，備忘錄方法的遞歸方式是自頂向下，而動態(tài)規(guī)劃算法是自底向上遞歸。矩陣連乘.._I 0 i=j"*5一[:駛｛〃匯用+ +1j]+p.任用｝r<j一J8/26

算法設計與分析期末試題考試版M6握x第57rjj-5"W4?rE?帚孑歡k。君2國zr-3第1次尸1*I十^程力*rx%%2^415-6-b30*35*15=(At)AiAHA2A3){A1AJA3-d(A2A3A4](AlA)tAjA4)，(A1A^^}A4.■[AM3A1AH{A1A2KAJA4A5).{AlA\J}{A^A?)(《：mi4}aiAi{A2^3A4A$A6]t'PUA2HAWA5A6)(Al '){AJA'A6)(4]4?A*AJ)iA;A6){A1A_43A-AJA61充THA二{a*A1}A44A2{AJA4A5]'3A3*A4A5MWA3A41QAEA3A4A?A6^(a2AJHA4A5A6}h《為",1為二}{R、A6},gYW)ASJr?3卜30二(A_Z；AdrAj{A4Ai).-|A.Al}A?Aj{A4A2iA6}，-{A/A；A>A6}(AjA-aJA6^船.atA』)“15^*10=.(AJ]A5-A』(A>AJ{%-%)A6*0fA5)*11)*20*25=(A51A6禮.**,(k26人最長公共子序列最長公共子序列的結構最長公共子序列的結構有如下表示：設序列X=<x,x 2,…，x m>和Y=<yi,y 2,…，y n>的一個最長公共子序列 Z=<zi, z2,…，z k>,則:.若xm=yn,則zk=xm=yn且Zk-i是Xm-i和Yn-i的最長公共子序列；.若Xm^yn且zkwXm，則Z是Xm-i和Y的最長公共子序列；.若Xm^yn且zkWyn，則Z是X和Y>-i的最長公共子序列。其中Xm-i=<xi,x2,…，xm-i>,Y)-i=<yi,y2,…，yn-i>,Zk-i=<zi,z2,…，zk-i>。子問題的遞歸結構由最長公共子序列問題的最優(yōu)子結構性質可知，要找出 X=<xi,x2,…，xm>和丫=<y,y2,…，yn>的最長公共子序列，可按以下方式遞歸地進行：當 xm=yn時，找出Xm-i禾口Y-i的最長公共子序列，然后在其尾部加上xm(=yn)即可得X和丫的一個最長公共子序列。當 xmWyn時，必須解兩個子問題，即找出 Xm-i9/26算法設計與分析期末試題考試版和Y的一個最長公共子序列及X和Yn-1的一個最長公共子序列。這兩個公共子序列中較長者即為 X和丫的一個最長公共子序列。由此遞歸結構容易看到最長公共子序列問題具有子問題重疊性質。 例如，在計算X和丫的最長公共子序列時，可能要計算出X和Yn-1及Xm-1和Y的最長公共子序列。而這兩個子問題都包含一個公共子問題，即計算Xm-1和Y-1的最長公共子序列。與矩陣連乘積最優(yōu)計算次序問題類似，我們來建立子問題的最優(yōu)值的遞歸關系。用c[i,j]記錄序列X和丫的最長公共子序列的長度。其中X=<x1,x2,???,xi>,Y=<y1,y2,???,yj>。當i=0或j=0時，空序列是X和丫的最長公共子序列，故c[i,j]=0o其他情況下，由定理可建立遞歸關系如下：(} if/=Ocrj=1((/-L/—I]+I ifJ>(>undxt=>,j—l]t-I,j])ifLJ>(IandXf#皆.計算最優(yōu)值直接利用上節(jié)節(jié)末的遞歸式，我們將很容易就能寫出一個計算 c[i,j]的遞歸算法，但其計算時間是隨輸入長度指數(shù)增長的。由于在所考慮的子問題空間中，總共只有 0(m*n)個不同的子問題，因此，用動態(tài)規(guī)劃算法自底向上地計算最優(yōu)值能提高算法的效率。計算最長公共子序列長度的動態(tài)規(guī)劃算法 LCS_LENGTH(X,Y)X序歹UX=<X1,X2,…，xm^DY=<y1,y2,…，yn>作為輸入。輸出兩個數(shù)組c[0..m,0..n]和b[1..m,1..n]。其中c[i,j]存儲X與丫的最長公共子序列的長度，b[i,j]記錄指示c[i,j]的值是由哪一個子問題的解達到的，這在構造最長公共子序列時要用到。最后，X和丫的最長公共子序列的長度記錄于 c[m,n]中。由算法LCS_LENGT計算得到的數(shù)組b可用于快速構造序列X=<x,x2,…，x?>和Y=<y,y2,…，yn>的最長公共子序列。首先從b[m,n]開始，沿著其中的箭頭所指的方向在數(shù)組 b中搜索。當b[i,j]中遇到"\"時(意味著xi=yi是LCS的一個元素)，表示X與丫的最長公共子序列是由X-1與Y-1的最長公共子序列在尾部加上 xi得到的子序列；當b[i,j]中遇到"T"時，表示X與Y的最長公共子序列和X-1與Y的最長公共子序列相同;當b[i,j]中遇到"一"時，表示X與丫的最長公共子序列和Xi與Y-1的最長公共子序列相同。這種方法是按照反序來找LCS的每一個元素的。由于每個數(shù)組單元的計算耗費 0(1)時間，算法LCS_LENGTH時O(mn。10/26算法設計與分析期末試題考試版,012 3 4 5 6流水線調度在M1上加工時間短的任務優(yōu)先，而在M2上加工時間短的任務排在最后如果最小的時間是Tk1則將任務k排在第一位，如果最小的任務Tk2則排在最后一個。最優(yōu)二叉搜索樹對于有n個關鍵碼的集合，其關鍵碼有 n!種不同的排列，可構成的不同二叉搜索樹有1棵。（n個結點的不同二叉樹，卡塔蘭數(shù)）。如何評價這些二叉搜索樹，可以用樹的搜索效率來衡量。例如：標識符集 {1,2,3}={do,if,stop} 可能的二分檢索樹為：11/26算法設計與分析期末試題考試版TOC\o"1-5"\h\z(a) (b)若P1=0.5,P2=0.1,P3=0.05,q0=0.15, q1=0.1,q2=0.05,q3=0.05,求每棵樹的平均比較次數(shù)(成本)。Pa(n)=1 Xp1+2X p2+3Xp3+1Xq0+2Xq1+3X(q2+q3) =1義 0.5+2義 0.1+3X0.05 +1X0.05+2X0.1+3X(0.05+0.05) =1.5Pb(n)=1Xp1+2X p3+3Xp2+1Xq0+2Xq3+3X(q1+q2 ) =1義 0.5+2義 0.05+3X0.1+1X0.15+2X0.05+3X(0.1+0.05) =1.6Pc(n)=1Xp2+2X(p1+ p3)+2X(q0+q1+q2+q3) =1乂0.1+2義(0.5+0.05)+2X(0.15+0.1+0.05+0.05) =1.9Pd(n)=1Xp3+2Xp1+3Xp2+1Xq3+2乂q0+3乂(q1+q2)=1X0.05+2X0.5+3X0.1+1X0.05+ 2X0.15+3X(0.1+0.05) =2.1512/26算法設計與分析期末試題考試版Pe(n)=1Xp3+2Xp2+3Xpl+1Xq3+2乂q2+3乂(q0+q1) =1X0.05+2X0.1+3X0.5+1X0.05+2X0.15+3X(0.15TOC\o"1-5"\h\z+0.1) =2.85因此，上例中的最小平均路長為 Pa(n)=1.5?？梢缘贸鼋Y論：結點在二叉搜索樹中的層次越深，需要比較的次數(shù)就越多，因此要構造一棵最小二叉樹，一般盡量把搜索概率較高的結點放在較高的層次 。p=y深度+ *路徑長。最優(yōu)二叉搜索樹：在一個表示S的二叉樹T中，設存儲元素Xi的結點深度為Ci；葉結點(xj,xj+1)的結點深度為dj。\o"CurrentDocument"n nP二，二1 六0注：在檢索過程中，每進行一次比較，就進入下面一層，對于成功的檢索，比較的次數(shù)就是所在的層數(shù)加1。對于不成功的檢索，被檢索的關鍵碼屬于那個外部結點代表的可能關鍵碼集合，比較次數(shù)就等于此外部結點的層數(shù)。又t于圖的內結點而言，第 0層需要比較操作次數(shù)為1,第1層需要比較2次，第2層需要3次。13/26

算法設計與分析期末試題考試版根層士M=1鍵值：自頂向下分析A—1概率：pi,…,pk_i,Pg?pfc+根層士M=1鍵值：自頂向下分析A—1lr-1?？趉^^k+J，■一，口左子樹一』報' , 左子樹右手軻k-i=i：左子隅縮為單節(jié)點.k+1=j：右子樹縮為單節(jié)點.k<h左子樹為空朝.k>h右子樹為空糊.■力=嗎粳血xi+Zm（〃即）+D+Ep。（嗎+i）｝左子樹（成功查找） 石子朝（硼查找）TOC\o"1-5"\h\zI7 A-l J=恩思（4+2>『+Za+2>內。]）十匯凡上（初｝- l-i 修+1 l-i 13-1,…一人"全^節(jié)^R率和 平趾上昌￡子砌嘀QhL；]遞推卜I算式 jq。力冒■｛qj,大一1]+q左+1,力｝+2區(qū)1wiqwnT 5=rOpfintalBST(A[L?/t]?P[l?ji]?C[L,./!+。0-磯￡[1../+1,?！╙)00.104id1；00.20.814D0.41.000.30j=0 12 3 4C[/,/-i]<-0;Cj=0 12 3 4C[iJ]^P[i];C次對角元；/R次對角元C仍+1t川<-0;”c對角元最后一個元素for(d 而for(i<-\ton-rf)do*匚1 1jyf+d;”范圍;2~nminval-8；for（k<^itojydo戈最優(yōu)根 if（C[f;fr-ll+C[fr+lJ1<mimal）/基本操作 立方型效率加m亦。八曰1+CW+1,力；卜〃.一紀口間可以限短長d/I一后收加；”記錄最優(yōu)根，此句教材上錯為IRpj-1]^R[i+1j]sum<-P[i]; 之間，效率降至for（si+1toj）dosumsain+P[s]; 平方型.C[i,7]=niimat+5?w/;14/26算法設計與分析期末試題考試版0.(15仆$。0.(15仆$?；厮莘?.簡單概述回溯法思路的簡單描述是：把問題的解空間轉化成了圖或者樹的結構表示，然后使用深度優(yōu)先搜索策略進行遍歷，遍歷的過程中記錄和尋找所有可行解或者最優(yōu)解?；舅枷腩愅冢?圖的深度優(yōu)先搜索?二叉樹的后序遍歷【分支限界法：廣度優(yōu)先搜索思想類同于：圖的廣度優(yōu)先遍歷15/26算法設計與分析期末試題考試版二叉樹的層序遍歷】一些概念(1)問題的解向量：回溯法希望一個問題的解能夠表示成一個 n元式(x1,x2,…,xn)的形式。(2)顯約束：對分量xi的取值限定。(3)隱約束：為滿足問題的解而對不同分量之間施加的約束。(4)解空間：對于問題的一個實例，解向量滿足顯式約束條件的所有多元組，構成了該實例的一個解空間。(5)擴展結點：一個正在產(chǎn)生兒子的結點稱為擴展結點(6)活結點：一個自身已生成但其兒子還沒有全部生成的節(jié)點稱做活結點(7)死結點：一個所有兒子已經(jīng)產(chǎn)生的結點稱做死結點(8)深度優(yōu)先的問題狀態(tài)生成法：如果對一個擴展結點R一旦產(chǎn)生了它的一個兒子C,就把C當做新的擴展結點。在完成對子樹C(以C為根的子樹)的窮盡搜索之后，將R重新變成擴展結點，繼續(xù)生成R的下一個兒子(如果存在)(9)寬度優(yōu)先的問題狀態(tài)生成法 ：在一個擴展結點變成死結點之前，它一直是擴展結點(10)回溯法：為了避免生成那些不可能產(chǎn)生最佳解的問題狀態(tài)，要不斷地利用限界函數(shù)(boundingfunction)來處死那些實際上不可能產(chǎn)生所需解的活結點， 以減少問題的計算量。具有限界函數(shù)的深度優(yōu)先生成法稱為回溯法基本思想：按照深度優(yōu)先策略，從根結點出發(fā)搜索解空間。算法搜索至解空間的任一結點時總是先判斷該結點是否問題的約束條件。 如果滿足進入該子樹，繼續(xù)按深度優(yōu)先的策略搜索。否則，不去搜索以該結點為根的子樹，而是逐層向其祖先結點回溯。其實回溯法就是對隱式圖的深度優(yōu)先搜索算法回溯法的基本行為是搜索，搜索過程使用剪枝函數(shù)來為了避免無效的搜索。剪枝函數(shù)包括兩類：.使用約束函數(shù)，剪去不滿足約束條件的路徑；.使用限界函數(shù)，剪去不能得到最優(yōu)解的路徑。16/26

算法設計與分析期末試題考試版問題的關鍵在于如何定義問題的解空間，轉化成樹（即解空間樹）。解空間樹分為兩種：子集樹和排列樹。兩種在算法結構和思路上大體相同。.子集樹所給的問題是從n個元素的集合S中找出滿足某種性質的子集時，相應的解空間成為子集樹。如0-1背包問題，從所給重量、價值不同的物品中挑選幾個物品放入背包，使得在滿足背包不超重的情況下，背包內物品價值最大。它的解空間就是一個典型的子集樹?；厮莘ㄋ阉髯蛹瘶涞乃惴ǚ妒饺缦拢篬cpp]viewplaincopyvoidbacktrack(intt)TOC\o"1-5"\h\z{if(t>n)output(x);elsefor (inti=0;i<=1;i++) {backtrack(t+1);x[t]=i;backtrack(t+1);if(constraint(t)&&bound(t))}.排列樹所給的問題是確定n個元素滿足某種性質的排列時，相應的解空間就是排列樹。17/26

算法設計與分析期末試題考試版如旅行售貨員問題，一個售貨員把幾個城市旅行一遍，要求走的路程最小它的解就是幾個城市的排列，解空間就是排列樹?；厮莘ㄋ阉髋帕袠涞乃惴ǚ妒饺缦拢篬cpp]viewplaincopy<spanstyle="font-size:18px;">voidbacktrack(intt){if(t>n)output(x);elsefor(inti=t;i<=n;i++) {swap(x[t],x[i]);if(constraint(t)&&bound(t)) backtrack(t+1);swap(x[t],x[i]);}基本步驟：確定問題的解空間：應用回溯法時，首先應明確定義問題的解的空間。問題的解空間應至少包含問題的一個解。確定結點的擴展規(guī)則搜索解空間：從開始結點出發(fā)，以深度優(yōu)先的方式搜索整個解空間。分支限界法一、分支限界法與回溯法的區(qū)別與聯(lián)系(1)求解目標：回溯法的求解目標是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標則是找出滿足約束條件的一個解， 或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解。(2)搜索方式的不同：回溯法以深度優(yōu)先的方式搜索解空間樹，而分支限界法則以廣度優(yōu)先或以最小耗費優(yōu)先的方式搜索解空間樹。18/26算法設計與分析期末試題考試版二、分支限界法的基本思想分支限界法常以廣度優(yōu)先或以最小耗費（最大效益）優(yōu)先的方式搜索問題的解空間樹。在分支限界法中，每一個活結點只有一次機會成為擴展結點。 活結點一旦成為擴展結點，就一次性產(chǎn)生其所有兒子結點。在這些兒子結點中，導致不可行解或導致非最優(yōu)解的兒子結點被舍棄，其余兒子結點被加入活結點表中。此后，從活結點表中取下一結點成為當前擴展結點， 并重復上述結點擴展過程。這個過程一直持續(xù)到找到所需的解或活結點表為空時為止⑴描述：采用廣度優(yōu)先產(chǎn)生狀態(tài)空間樹的結點，并使用剪枝函數(shù)的方法稱為分枝限界法。所謂“分支”是采用廣度優(yōu)先的策略，依次生成擴展結點的所有分支（即：兒子結點）。所謂“限界”是在結點擴展過程中，計算結點的上界（或下界），邊搜索邊減掉搜索樹的某些分支，從而提高搜索效率。⑵原理：按照廣度優(yōu)先的原則，一個活結點一旦成為擴展結點（ E-結點）R后，算法將依次生成它的全部孩子結點，將那些導致不可行解或導致非最優(yōu)解的兒子舍棄，其余兒子加入活結點表中。然后，從活結點表中取出一個結點作為當前擴展結點。重復上述結點擴展過程，直至找到問題的解或判定無解為止。（3）分支限界法與回溯法1）求解目標：回溯法的求解目標是找出解空間樹中滿足約束條件的 所有解，而分支限界法的求解目標則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解。19/26算法設計與分析期末試題考試版2）搜索方式的不同：回溯法以深度優(yōu)先的方式搜索解空間樹，而分支限界法則以廣度優(yōu)先或以最小耗費優(yōu)先的方式搜索解空間樹。（4）常見的分支限界法1）FIFO分支限界法（隊列式分支限界法）基本思想：按照隊列先進先出（FIFO）原則選取下一個活結點為擴展結點0搜索策略：一開始，根結點是唯一的活結點，根結點入隊。從活結點隊中取出根結點后，作為當前擴展結點。對當前擴展結點，先從左到右地產(chǎn)生它的所有兒子，用約束條件檢查，把所有滿足約束函數(shù)的兒子加入活結點隊列中。再從活結點表中取出隊首結點（隊中最先進來的結點）為當前擴展結點，……，直到找到一個解或活結點隊列為空為止。2）LC（leastcost） 分支限界法（優(yōu)先隊列式分支限界法）基本思想：為了加速搜索的進程，應采用有效地方式選擇活結點進行擴展。按照優(yōu)先隊列中規(guī)定的優(yōu)先級選取優(yōu)先級最高的結點成為當前擴展結點。搜索策略：對每一活結點計算一個優(yōu)先級（某些信息的函數(shù)值），并根據(jù)這些優(yōu)先級；從當前活結點表中優(yōu)先選擇一個優(yōu)先級最高（最有利）的結點作為擴展結點，使搜索朝著解空間樹上有最優(yōu)解的分支推進，以便盡快20/26算法設計與分析期末試題考試版地找出一個最優(yōu)解。再從活結點表中下一個優(yōu)先級別最高的結點為當前擴展結點，……，直到找到一個解或活結點隊列為空為止。2、單源最短路徑問題問題描述在下圖所給的有向圖G中，每一邊都有一個非負邊權。要求圖 G的從源頂點s到目標頂點t之間的最短路徑。(2)解空間數(shù)一一排列樹下圖是用優(yōu)先隊列式分支限界法解有向圖 G的單源最短路徑問題產(chǎn)生的解空間樹。從根節(jié)點s到一個葉子的一條路徑表示從結點 s到結點t的一條路徑，路徑上邊的權的和為路徑長度。其中，每一個結點旁邊的數(shù)字表示該結點所對應的當前路長。21/26算法設計與分析期末試題考試版(3)算法思想采用優(yōu)先隊列式分支限界法來解本問題:(3)算法思想采用優(yōu)先隊列式分支限界法來解本問題:用一極小堆來存儲活結點表，其優(yōu)先級是結點所對應的當前路長。算法從圖G的源頂點s和空優(yōu)先隊列開始。結點s被擴展后，它的兒子結點被依次插入堆中。此后，算法從堆中取出具有最小當前路長的結點作為當前擴展結點，并依次檢查與當前擴展結點相鄰的所有頂點。如果從當前擴展結點i到頂點j有邊可達，且從源出發(fā)，途經(jīng)頂點 i再到頂點j的所相應的路徑的長度小于當前最優(yōu)路徑長度，則將該頂點作為活結點插入到活結點優(yōu)先隊列中。這個結點的擴展過程一直繼續(xù)到活結點優(yōu)先隊列為空時為止。在算法擴展結點的過程中，一旦發(fā)現(xiàn)一個結點的下界不小于當前找到的最短路長，則算法剪去以該結點為根的子樹。在算法中，利用結點間的控制關系進行剪枝。從源頂點 s出發(fā)，2條不同路徑到達圖G的同一頂點。由于兩條路徑的路長不同，因此可以將路長長的路徑所對應的樹中的結點為根的子樹剪去。22/26

算法設計與分析期末試題考試版動態(tài)規(guī)劃思想：石子合并問題描述：在一個圓形操場的四周擺放著n堆石子?，F(xiàn)要將石子有次序地合并成一堆。規(guī)定每次只能選相鄰的2堆石子合并成新的一堆，并將新的一堆石子數(shù)記為該次合并的得分試設計一個算法，計算出將n堆石子合并成一堆的最小得分和最大得分。圖1精圖2總行號="一】圻￡="圖加開始以為通過貪心算法可能很快解決問題，可是是行不通的。首先我們可以把這么堆石子看成一列我們假如5堆的石子，其中石子數(shù)分別為7,6,5,7,100?按照貪心法，合并的過程如下：每次合并得分第一次合并 76 5 7 100 =1123/26算法設計與分析期末試題考試版第二次合并 7 117 100=18第三次合并 18 7 100=25第四次合并25 100