《算法設計與分析》實驗指導書課程編號：09110112課程名稱：算法設計與分析英文名稱：AlgorithmsDesignandAnalysis適應專業：計算機科學與技術執筆人：沙莎實驗指導書名稱：計算機算法基礎實驗一 分治法1、基本要求1）了解用分治法求解的問題：當要求解一個輸入規模為 n，且n的取值相當大的問題時，的，如果問題可以分成 k個不同子集合，得到 k個不同的可獨立求解的子問題， 其中1<k≤n，而且子問題與原問題性質相同， 原問題的解可由這些子問題的解合并得出。那末， 對于這類問題分治法是十分有效的。2）掌握分治法的一般控制流程DanC(p,q)global n，A[1:n]; integer m,p,q;//1 pqnif Small(p,q) thenreturnG(p,q);else m=Divide(p,q);//p m<qreturn Combine(DanC(p,m),DanC(m+1,q));endifendDanC3）實現典型的分治算法的編程與上機實驗，驗證算法的時間復雜性函數。2、實驗內容1）編程實現歸并排序算法和快速排序算法，程序中加入比較次數的計數功能，輸出排序結果和比較次數。2）輸入10組相同的數據，驗證排序結果和完成排序的比較次數。3）與復雜性函數所計算的比較次數比較。4）用表格列出比較結果。5）給出文字分析。3、歸并排序算法和快速排序算法歸并排序算法procedureMERGESORT(low，high)//A(low ；high)是一個全程數組，它含有high-low+1≥0個待排序的元素//integerlow ，high；iflow<high ；1thenmid ← ，// 求這個集合的分割點 //callMERGESORT(low ，mid)// 將一個子集合排序 //callMERGESORT(mid+1 ，high)// 將另一個子集合排序callMERGE(low ，mid，high)// 歸并兩個已排序的子集合 //endifendMERGESORT歸并兩個已排序的集合procedureMERGE(low ，mid，high)//A(low ：high)是一個全程數組 //輔助數組B(low；high)//integerh ，i，j，k；h ←low；i←low；j←mid+1；whileh ≤midand j ≤highdo// 當兩個集合都沒取盡時 //ifA(h) ≤A(j)thenB(i) ←A(h)；h←h+1elseB(i) ←A(j) ；j←j+1endif←i+1repeatifh>midthenfork ←jtohigh do// 處理剩余的元素 //B(i) ←A(k)；i←i+1repeatelsefork ←htomid doB(i) ←A(k)；i←i+1repeatendif將已歸并的集合復制到 AendMERGE快速排序算法QuickSort(p,q)將數組A[1:n]中的元素A[p],A[p+1], ,A[q] 按不降次序排列，并假定A[n+1]是一個確定的、且大于A[1:n] 中所有的數。//intp,q;globaln,A[1:n];ifp<qthenj=Partition(p,q+1);// 劃分后j成為劃分元素的位置QuickSort(p,j-1);2QuickSort(j+1,q);endifendQuickSortprocedurePARTITION(m，p)// 退出過程時， p帶著劃分元素所在的下標位置。 //integerm ，p，i；globalA(m ：p-1)←A(m)；i←m//A(m)是劃分元素//looploop i ←i+1untilA(i) ≥vrepeat//i 由左向右移//loopp ←p-1untilA(p) ≤vrepeat//p 由右向左移//ifi<pthencallINTERCHANGE(A(i) ，A(p))//A(i) 和A(p)換位//elseexitendifrepeatA(m) ←A(p)；A(p) ←v// 劃分元素在位置 p//EndPARTITION實驗二 貪心法1、 基本要求1）優化問題有n個輸入，而它的解就由這n個輸入滿足某些事先給定的約束條件的某個子集組成，而把滿足約束條件的子集稱為該問題的可行解。可行解一般來說是不唯一的。那些使目標函數取極值(極大或極小)的可行解，稱為最優解。2）貪心法求優化問題算法思想：在貪心算法中采用逐步構造最優解的方法。 在每個階段，都作出一個看上去最優的決策（在一定的標準下）。決策一旦作出，就不可再更改。作出貪心決策的依據稱為貪心準則 （greedycriterion ）。2）一般方法①根據題意，選取一種量度標準。②按這種量度標準對這 n個輸入排序③依次選擇輸入量加入部分解中。如果當前這個輸入量的加入，不滿足約束條件，則不把此輸入加到這部分解中。procedureGREEDY(A，n)/* 貪心法一般控制流程 *///A(1 ：n)包含n個輸入//solutions ←φ// 將解向量solution 初始化為空／fori ←1tondox ←SELECT(A)3ifFEASIBLE(solution ，x)thensolutions ←UNION(solution ，x)endifrepeatreturn(solution)endGREEDY3）實現典型的貪心算法的編程與上機實驗，驗證算法的時間復雜性函數。2、實驗內容1）編程實現背包問題貪心算法和最小生成樹prim算法。通過具體算法理解如何通過局部最優實現全局最優，并驗證算法的時間復雜性。2） 輸入5個的圖的鄰接矩陣，程序加入統計 prim算法訪問圖的節點數和邊數的語句。3） 將統計數與復雜性函數所計算的比較次數比較，用表格列出比較結果，給出文字分析。3、 背包問題貪心算法和 prim算法背包問題的貪心算法procedureKNAPSACK(P ，W，M，X，n)//P(1 ：n)和W(1；n)分別含有按P(i)/W(i) ≥P(i+1)/W(i+1) 排序的n件物品的效益值和重量。M是背包的容量大小，而 x(1：n)是解向量//realP(1 ：n)，W(1：n)，X(1：n)，M，cu；integeri ，n；←0//將解向量初始化為零//cu←M//cu是背包剩余容量//fori←1tondoifW(i)>cuthenexitendifX(i) ←1cu ←cu-W(i)repeatifi ≤nthenX(i) ←cu/W(i)endifendGREEDY-KNAPSACKprocedureprim(G,)status←“unseen” //T 為空status[1] ←“treenode ” // 將1放入Tforeachedge(1,w)dostatus[w] ←“fringe ” // 找到T的鄰接點dad[w] ←1; //w 通過1與T建立聯系4dist[w] ←weight(1,w) //w 到T的距離repeatwhilestatus[t] ≠“treenode ”dopickafringeuwithmindist[w]// 選取到T最近的節點status[u] ←“treenode ”foreachedge(u,w)do修改w和T的關系repeatrepeat實驗三 動態規劃1、 基本要求1）理解最優子結構的問題。有一類問題的活動過程可以分成若干個階段， 而且在任一階段后的行為依賴于該階段的狀態，與該階段之前的過程如何達到這種狀態的方式無關。這類問題的解決是多階段的決策過程。在 50年代，貝爾曼（ RichardBellman ）等人提出了解決這類問題的 “最優化原理”，從而創建了最優化問題的一種新的算法設計方法－動態規劃。對于一個多階段過程問題，是否可以分段實現最優決策，依賴于該問題是否有最優子結構性質，能否采用動態規劃的方法，還要看該問題的子問題是否具有重疊性質。最優子結構性質： 原問題的最優解包含了其子問題的最優解。子問題重疊性質： 每次產生的子問題并不總是新問題，有些子問題被反復計算多次。問題的最優子結構性質和子問題重疊性質是采用動態規劃算法的兩個基本要素。2）理解分段決策Bellman方程。每一點最優都是上一點最優加上這段長度。即當前最優只與上一步有關。us 0,uj min{ui wij}.i jus 初始值，uj第j段的最優值。3）一般方法① 找出最優解的性質，并刻畫其結構特征；② 遞歸地定義最優值（寫出動態規劃方程）；③ 以自底向上的方式計算出最優值；④ 根據計算最優值時得到的信息，構造一個最優解。步驟1-3是動態規劃算法的基本步驟。在只需要求出最優值的情形，步驟 4可以省略，步驟 3中記錄的信息也較少；若需要求出問題的一個最優解，則必須執行步驟 4，步驟3中記錄的信息必須足夠多以便構造最優解。2、實驗內容1） 編程實現多段圖的最短路經問題的動態規劃算法。2） 圖的數據結構采用鄰接表。53） 要求用文件裝入 5個多段圖數據，編寫從文件到鄰接表的函數。4） 驗證算法的時間復雜性。3、 多段圖算法procedure FGRAPH(E，k，n，P)// 輸入是按段的順序給結點編號的，有 n個結點的k段圖。E是邊集，c(i，j)是邊<i,j> 的成本。P(1 ：k)是最小成本路徑。 //realCOST(n)，integerD(n一1)，P(k)，r，j，k，nCOST(n)←0for j←n-1to1by－1do// 計算COST(j)//設r是一個這樣的結點， (j，r) E且使c(j，r)+COST(r)取最小值COST(j)←c(j，r)+COST(r)D(j) ←rrepeat // 向前對j-1進行決策//P(1) ←1；P(k)←n；for j←2tok-1do// 找路徑上的第j個節點//P(j) ←D(P(j-1))repeatend FGRAPH實驗四 深度優先搜索1、基本要求1） 理解深度優先搜索策略是盡可能“深”地搜索圖。在深度優先搜索中，對于最新發現的頂點 v，如果邊（v，w）是還未探測的邊，則沿（ v，w）繼續搜索下去。當所有的邊（ v，w）都己被探尋過，搜索將回溯到發現結點v的頂點。這一過程一直進行到回到源點為止。如果還存在未被發現的頂點，則選擇其中一個作為源結點并重復以上過程，整個進程反復進行直到所有結點都被發現為止。2） 理解深度優先搜索過程中頂點的三種狀態還未到達的頂點，當前路徑上經過的頂點，深度優先在搜索過程中也為結點著色以表示結點的狀態。每個頂點開始均為白色，搜索中被發現時置為灰色， 當其鄰接表被完全檢索之后又被置成黑色。2、實驗內容1） 編程實現深度優先搜索算法。2） 修改算法使之可以找出圖的所有樹。3） 修改算法使之可以判斷圖是否為一棵樹。4） 修改算法使之可以判斷圖是否存在一個環。3、深度優先算法6procedureDFS(G);for 每個頂點 u∈Gdocolor[u] ←White;repeatfor 每個頂點u∈Gdoifcolor[u]=WhitethenDFS_Visit(G,u);end;procedureDFS_Visit(u);color[u] ←Gray;for(u,w) ∈E do // 探尋邊(u,w)ifcolor[w]=WhitethenDFS_Visit(w);repeatcolor[u] ←Black; //完成后置 u為黑色end;實驗五 回溯法1、基本要求1）理解可用回溯法求解的問題問題P通常要能表達為對已知的、由n元組(x1，?，xn)組成的狀態空間E={(x1，?，xn)|xiSi,i=1,2,?n}，給定關于n元組中的分量的一個約束集D，求滿足D的全部約束條件的所有n元組。Si是xi的定義域且Si是有窮集，稱E中滿足D的全部約束條件的所有 n元組為問題P的一個解。2）理解回溯法的基本思想回溯法是一個既帶有系統性又帶有跳躍性的搜索算法。它在包含問題的所有解的解空間樹中，按照深度優先的策略，從根結點出發搜索解空間樹。算法搜索至解空間樹的任一結點時，總是先判斷該結點是否肯定不包含問題的解。如果肯定不包含，則跳過對以該結點為根的子樹的系統搜索，逐層向其祖先結點回溯。否則，進入該子樹，繼續按深度優先的策略進行搜索。回溯法的形式描述：procedureBACAKTRACE(n)k=1;while(k>0)doifTk(x1 ，x2，?，xk-1) 的值還未取遍 then{xk←Tk(x1，x2，?，xk-1) 中