數(shù)學(xué)院算法實(shí)驗

《算法設(shè)計與分析》實(shí)驗指導(dǎo)書課程編號：課程名稱：算法設(shè)計與分析英文名稱：AlgorithmsDesignandAnalysis適應(yīng)專業(yè)：計算機(jī)科學(xué)與技術(shù)執(zhí)筆人：劉少兵參考教材：《計算機(jī)算法基礎(chǔ)》（余祥宣）、《算法設(shè)計與分析》（王曉東）實(shí)驗一（1）分治法基本要求1）了解用分治法求解的問題：當(dāng)要求解一個輸入規(guī)模為n，且n的取值相當(dāng)大的問題時，的，如果問題可以分成k個不同子集合，得到k個不同的可獨(dú)立求解的子問題，其中1<k≤n，而且子問題與原問題性質(zhì)相同，原問題的解可由這些子問題的解合并得出。那末，對于這類問題分治法是十分有效的。2）掌握分治法的一般控制流程DanC(p,q)globaln，A[1:n];integerm,p,q;//1￡p￡q￡nifSmall(p,q)thenreturnG(p,q);elsem=Divide(p,q);//p￡m<qreturnCombine(DanC(p,m),DanC(m+1,q));endifendDanC3）實(shí)現(xiàn)典型的分治算法的編程與上機(jī)實(shí)驗，驗證算法的時間復(fù)雜性函數(shù)。實(shí)驗內(nèi)容[斜線部分可以不用實(shí)現(xiàn)]編程實(shí)現(xiàn)歸并排序算法和快速排序算法，程序中加入比較次數(shù)的計數(shù)功能，輸出排序結(jié)果和比較次數(shù)。待排序的實(shí)驗數(shù)據(jù)如下：a[]={70,66,88,70,45,90,33,66,70,22,11,90,11,90,11,90};輸入10組相同的數(shù)據(jù)，驗證排序結(jié)果和完成排序的比較次數(shù)。與復(fù)雜性函數(shù)所計算的比較次數(shù)比較。用表格列出比較結(jié)果。給出文字分析。歸并排序算法和快速排序算法歸并排序算法procedureMERGESORT(low，high)//A(low；high)是一個全程數(shù)組，它含有high-low+1≥0個待排序的元素//integerlow，high；iflow<high；thenmid←，//求這個集合的分割點(diǎn)//callMERGESORT(low，mid)//將一個子集合排序//callMERGESORT(mid+1，high)//將另一個子集合排序callMERGE(low，mid，high)//歸并兩個已排序的子集合//endifendMERGESORT歸并兩個已排序的集合procedureMERGE(low，mid，high)//A(low：high)是一個全程數(shù)組////輔助數(shù)組B(low；high)//integerh，i，j，k；h←low；i←low；j←mid+1；whileh≤midandj≤highdo//當(dāng)兩個集合都沒取盡時//ifA(h)≤A(j)thenB(i)←A(h)；h←h+1elseB(i)←A(j)；j←j+1endifi←i+1repeatifh>midthenfork←jtohighdo//處理剩余的元素//B(i)←A(k)；i←i+1repeatelsefork←htomiddoB(i)←A(k)；i←i+1repeatendif將已歸并的集合復(fù)制到AendMERGE快速排序算法QuickSort(p,q)//將數(shù)組A[1:n]中的元素A[p],A[p+1],?,A[q]按不降次序排列，并假定A[n+1]是一個確定的、且大于A[1:n]中所有的數(shù)。//intp,q;globaln,A[1:n];ifp<qthenj=Partition(p,q+1);//劃分后j成為劃分元素的位置QuickSort(p,j-1);QuickSort(j+1,q);endifendQuickSortprocedurePARTITION(m，p)//退出過程時，p帶著劃分元素所在的下標(biāo)位置。//integerm，p，i；globalA(m：p-1)v←A(m)；i←m//A(m)是劃分元素//looploopi←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實(shí)驗一（2）用分治策略求2維極大點(diǎn)問題1、基本要求在2維空間中，如果x1>x2且y1>y2，那么稱點(diǎn)(x1,y1)支配點(diǎn)(x2,y2)。如果一個點(diǎn)沒有其他點(diǎn)支配，那么稱其為極大者。已知有n個點(diǎn)的集合，求極大點(diǎn)問題是指找出在n個點(diǎn)中的所有極大點(diǎn)。使用分治策略，首先找出垂直于x軸的中位線L，它劃分整個點(diǎn)集為兩個子集，分別用SL和SR表示中線L的左邊點(diǎn)集合和右邊點(diǎn)集合。下一步，分別找出SL和SR的極大點(diǎn)。合并過程相當(dāng)簡單。由于在SR中點(diǎn)的x值總是大于SL中每個點(diǎn)的x值，所以SL中的點(diǎn)是極大點(diǎn)當(dāng)且僅當(dāng)它的y值不小于SR中極大點(diǎn)的y值。在平面中找出極大點(diǎn)的分治算法輸入：n個平面點(diǎn)的集合。輸出：S的極大點(diǎn)。步驟1.如果S只含一個點(diǎn)，那么輸出該點(diǎn)為極大點(diǎn)；否則，找一條垂直于x軸的直線L，它劃分點(diǎn)集合為兩個子集合SL和SR，每個子集含有n/2個點(diǎn)。步驟2.遞歸地找出SL和SR的極大點(diǎn)。步驟3.將SL和SR的極大點(diǎn)投影到直線L上，并根據(jù)它們的y值排序這些點(diǎn)。對投影進(jìn)行線性掃描，如果SL中的極大點(diǎn)的y值小于SR中某個極大點(diǎn)的y值，那么舍棄它。2、實(shí)驗內(nèi)容隨機(jī)輸入平面上n個點(diǎn)的集合；使用分治策略編制計算機(jī)程序求出這n個點(diǎn)的極大點(diǎn)。編程實(shí)現(xiàn)2維極大點(diǎn)問題的求解，且在程序中體現(xiàn)分治策略。程序能處理任意的n個點(diǎn)。

實(shí)驗二貪心法基本要求優(yōu)化問題有n個輸入，而它的解就由這n個輸入滿足某些事先給定的約束條件的某個子集組成，而把滿足約束條件的子集稱為該問題的可行解?？尚薪庖话銇碚f是不唯一的。那些使目標(biāo)函數(shù)取極值(極大或極小)的可行解，稱為最優(yōu)解。貪心法求優(yōu)化問題算法思想：在貪心算法中采用逐步構(gòu)造最優(yōu)解的方法。在每個階段，都作出一個看上去最優(yōu)的決策（在一定的標(biāo)準(zhǔn)下）。決策一旦作出，就不可再更改。作出貪心決策的依據(jù)稱為貪心準(zhǔn)則（greedycriterion）。2）一般方法①根據(jù)題意，選取一種量度標(biāo)準(zhǔn)。②按這種量度標(biāo)準(zhǔn)對這n個輸入排序③依次選擇輸入量加入部分解中。如果當(dāng)前這個輸入量的加入，不滿足約束條件，則不把此輸入加到這部分解中。procedureGREEDY(A，n)/*貪心法一般控制流程*///A(1：n)包含n個輸入//solutions←φ//將解向量solution初始化為空／fori←1tondox←SELECT(A)ifFEASIBLE(solution，x)thensolutions←UNION(solution，x)endifrepeatreturn(solution)endGREEDY實(shí)現(xiàn)典型的貪心算法的編程與上機(jī)實(shí)驗，驗證算法的時間復(fù)雜性函數(shù)。實(shí)驗內(nèi)容[斜線部分可以不用實(shí)現(xiàn)]編程實(shí)現(xiàn)背包問題貪心算法和最小生成樹prim算法。通過具體算法理解如何通過局部最優(yōu)實(shí)現(xiàn)全局最優(yōu)，并驗證算法的時間復(fù)雜性。輸入5個的圖的鄰接矩陣，程序加入統(tǒng)計prim算法訪問圖的節(jié)點(diǎn)數(shù)和邊數(shù)的語句。將統(tǒng)計數(shù)與復(fù)雜性函數(shù)所計算的比較次數(shù)比較，用表格列出比較結(jié)果，給出文字分析。背包問題的實(shí)驗數(shù)據(jù)如下表：n=8,m=110,12345678Profit[i]1121313343535565Weight[i]111212333434555X[i]背包問題貪心算法和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；X←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的鄰接點(diǎn)dad[w]←1;//w通過1與T建立聯(lián)系dist[w]←weight(1,w)//w到T的距離repeatwhilestatus[t]≠“treenode”dopickafringeuwithmindist[w]//選取到T最近的節(jié)點(diǎn)status[u]←“treenode”foreachedge(u,w)do修改w和T的關(guān)系repeatrepeat實(shí)驗三動態(tài)規(guī)劃基本要求理解最優(yōu)子結(jié)構(gòu)的問題。有一類問題的活動過程可以分成若干個階段，而且在任一階段后的行為依賴于該階段的狀態(tài)，與該階段之前的過程如何達(dá)到這種狀態(tài)的方式無關(guān)。這類問題的解決是多階段的決策過程。在50年代，貝爾曼（RichardBellman）等人提出了解決這類問題的“最優(yōu)化原理”，從而創(chuàng)建了最優(yōu)化問題的一種新的算法設(shè)計方法－動態(tài)規(guī)劃。對于一個多階段過程問題，是否可以分段實(shí)現(xiàn)最優(yōu)決策，依賴于該問題是否有最優(yōu)子結(jié)構(gòu)性質(zhì)，能否采用動態(tài)規(guī)劃的方法，還要看該問題的子問題是否具有重疊性質(zhì)。最優(yōu)子結(jié)構(gòu)性質(zhì)：原問題的最優(yōu)解包含了其子問題的最優(yōu)解。子問題重疊性質(zhì)：每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計算多次。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題重疊性質(zhì)是采用動態(tài)規(guī)劃算法的兩個基本要素。理解分段決策Bellman方程。每一點(diǎn)最優(yōu)都是上一點(diǎn)最優(yōu)加上這段長度。即當(dāng)前最優(yōu)只與上一步有關(guān)。us初始值，uj第j段的最優(yōu)值。一般方法找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征；遞歸地定義最優(yōu)值（寫出動態(tài)規(guī)劃方程）；以自底向上的方式計算出最優(yōu)值；根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造一個最優(yōu)解。步驟1-3是動態(tài)規(guī)劃算法的基本步驟。在只需要求出最優(yōu)值的情形，步驟4可以省略，步驟3中記錄的信息也較少；若需要求出問題的一個最優(yōu)解，則必須執(zhí)行步驟4，步驟3中記錄的信息必須足夠多以便構(gòu)造最優(yōu)解。實(shí)驗內(nèi)容[斜線部分可以不實(shí)現(xiàn)]編程遞歸實(shí)現(xiàn)0-1背包問題并回溯求出問題的解向量（即X[N]的值）和多段圖的最短路經(jīng)問題的動態(tài)規(guī)劃算法。圖的數(shù)據(jù)結(jié)構(gòu)采用鄰接表。要求用文件裝入5個多段圖數(shù)據(jù)，編寫從文件到鄰接表的函數(shù)。驗證算法的時間復(fù)雜性。0-1背包問題的實(shí)驗數(shù)據(jù)見實(shí)驗二的背包問題數(shù)據(jù)。多段圖算法procedureFGRAPH(E，k，n，P)//輸入是按段的順序給結(jié)點(diǎn)編號的，有n個結(jié)點(diǎn)的k段圖。E是邊集，c(i，j)是邊<i,j>的成本。P(1：k)是最小成本路徑。//realCOST(n)，integerD(n一1)，P(k)，r，j，k，nCOST(n)←0forj←n-1to1by－1do//計算COST(j)//設(shè)r是一個這樣的結(jié)點(diǎn)，(j，r)?E且使c(j，r)+COST(r)取最小值COST(j)←c(j，r)+COST(r)D(j)←rrepeat//向前對j-1進(jìn)行決策//P(1)←1；P(k)←n；forj←2tok-1do//找路徑上的第j個節(jié)點(diǎn)//P(j)←D(P(j-1))repeatendFGRAPH

實(shí)驗四回溯法基本要求理解可用回溯法求解的問題問題P通常要能表達(dá)為對已知的、由n元組(x1，…，xn)組成的狀態(tài)空間E={(x1，…，xn)|xi?Si,i=1,2,…n}，給定關(guān)于n元組中的分量的一個約束集D，求滿足D的全部約束條件的所有n元組。Si是xi的定義域且Si是有窮集，稱E中滿足D的全部約束條件的所有n元組為問題P的一個解。理解回溯法的基本思想回溯法是一個既帶有系統(tǒng)性又帶有跳躍性的搜索算法。它在包含問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空間樹的任一結(jié)點(diǎn)時，總是先判斷該結(jié)點(diǎn)是否肯定不包含問題的解。如果肯定不包含，則跳過對以該結(jié)點(diǎn)為根的子樹的系統(tǒng)搜索，逐層向其祖先結(jié)點(diǎn)回溯。否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先的策略進(jìn)行搜索?；厮莘ǖ男问矫枋觯簆rocedureBACAKTRACE(n)k=1;while(k>0)doifTk(x1，x2，…，xk-1)的值還未取遍then{xk←Tk(x1，x2，…，xk-1)中未取遍過的值；ifBk(x1，x2，…，xk)then{(x1，x2，…，xk)被激活；ifk==nthen輸出(x1，x2，…，xn)；elsek=k+1；//深度擴(kuò)展搜索}}elsek=k-1//試探完了所有的xk，回溯endBACAKTRACE實(shí)驗內(nèi)容[斜線部分可以不用實(shí)現(xiàn)]編程實(shí)現(xiàn)n皇后算法，要求求出8皇后問題的所有解。編程實(shí)現(xiàn)0-1背包問題的最優(yōu)解。測試數(shù)據(jù)采用貪心算法一章的實(shí)驗數(shù)據(jù)。用圖形輸出中間過程。在程序中添加統(tǒng)計擴(kuò)展節(jié)點(diǎn)數(shù)，估計算法的復(fù)雜性。n皇后算法procedureNQUEENS(n)X(1)←0；k←1//k是當(dāng)前行；X(k)是當(dāng)前列//Whilek>0do//對所有的行執(zhí)行以下語句//{X(k)←X(k)+1//移到下一列//WhileX(k)≤nandnotPLACE(k)doX(k)←X(k)十lifX(k)≤n//找到一個位置//thenifk=n//是一個完整的解嗎//thenprint(X)//是，打印這個數(shù)組//else{k←k+1；X(k)←0；}elsek←k－1//回溯//}endNQUEENS

實(shí)驗五分支限界算法一、實(shí)驗?zāi)康?、掌握樹搜索策略。2、掌握分支限界策略。3、掌握用分支限界策略求解最短路徑問題。二、實(shí)驗學(xué)時：2學(xué)時三、實(shí)驗要求1、編程實(shí)現(xiàn)分支限界策略求解最短路徑問題。2、能對任意圖，給定源點(diǎn)和終點(diǎn)，求它們的最短路徑。四、實(shí)驗原理1、分支限界策略的思想分支限界策略是解決一大類組合問題的最有效策略之一?；旧?，該策略表明問題可能有許多可行解。然而，人們通過發(fā)現(xiàn)許多可行解不能成為最優(yōu)解來修剪解空間。2、分支限界策略的兩個重要機(jī)制：一個機(jī)制是產(chǎn)生分支，另一個機(jī)制是產(chǎn)生一個界限以致于能終止許多分支。五、實(shí)驗內(nèi)容 1、圖3-1中，問題是找出從v0到v3的最短路徑。這個問題能先通過轉(zhuǎn)換成一棵樹搜索問題而有效地解決。圖3-12、圖3-2顯示了所有6個可行解。如果不使用窮舉策略，那么分支限界策略是怎么實(shí)現(xiàn)找到最短路徑的呢？圖3-23、發(fā)現(xiàn)可行解，V0->V1,1->V2,3->V3，這個可行解的代價是5。這個代價等于5的可行解可作為最優(yōu)解的上界。任何代價大于5的解都不能成為一個最優(yōu)解。因此，這個上界能終止許多不成熟的分支。4、因此，窮舉搜索整個解空間是可以避免的。六、實(shí)驗任務(wù)1、使用分支限界策略求解最短路徑問題。2、能對任意給定的一副帶權(quán)圖，給定源點(diǎn)和終點(diǎn)，求它們的最短路徑長度及經(jīng)過的最短路徑。

實(shí)驗六解決最近點(diǎn)對問題的隨機(jī)算法一、實(shí)驗?zāi)康?、掌握隨機(jī)算法的思想。2、掌握最近點(diǎn)對問題的求解方法。二、實(shí)驗學(xué)時：2學(xué)時（綜合設(shè)計性實(shí)驗）三、實(shí)驗要求1、編程實(shí)現(xiàn)最近點(diǎn)對問題的求解。2、使用隨機(jī)算法求解最近點(diǎn)對問題。四、實(shí)驗原理1、隨機(jī)算法的概念相對較新。在執(zhí)行算法的過程中，隨機(jī)算法可以做出任意的選擇，這意味著可隨機(jī)地執(zhí)行某些動作。2、由于某些動作的執(zhí)行是隨機(jī)的，隨機(jī)算法具有下面兩個屬性：(1)在最優(yōu)化問題的情況中，隨意算法給出一個最優(yōu)解。但是由于在算法中隨機(jī)地采取動作，因此隨機(jī)最優(yōu)算法的時間復(fù)雜度也是隨機(jī)的。這樣，隨機(jī)最優(yōu)算法的平均情況時間復(fù)雜度遠(yuǎn)比它的最壞情況時間復(fù)雜度重要。(2)在判定問題的情況中，隨機(jī)算法有時會出錯。然而，產(chǎn)生錯誤的概率是非常小的；另外，隨機(jī)算法并非總是有用。五、實(shí)驗內(nèi)容1、最近點(diǎn)對問題令x1,x2,…,xn為二維平面上的n個點(diǎn)。最近點(diǎn)對問題是找到最近的一對點(diǎn)xi和xj，使得xi和xj之間的距離是所有可能的點(diǎn)對距離中最小。解決該問題的直接方法是計算出所有的n(n-1)/2個點(diǎn)對之間的距離，并在這些距離中找出最小值。2、隨機(jī)算法的主要思想如果兩個點(diǎn)xj和xk彼此遠(yuǎn)離，那么它們之間的距離不可能最小，因此可以被忽略。由于這種思想，隨機(jī)算法首先將點(diǎn)分成幾