西電軟件學(xué)院算法實驗報告模板2份

1、精選優(yōu)質(zhì)文檔-傾情為你奉上第二次試驗一、問題：Matrix-chain product分析：本題是矩陣鏈乘問題，需要求出最優(yōu)括號化方案。即在矩陣的乘法鏈上添加括號來改變運算順序以使矩陣鏈乘法的代價降低?？梢苑治鲈撴湷说囊粋€子段總結(jié)一些結(jié)論。假設(shè)mi,j表示Ai*Aj的鏈成需要進行的乘法次數(shù)（假設(shè)j-i足夠大），我們可以將Ai*Aj分為兩段進行計算：（Ai*Ak）*（Ak+1*Aj）可以得出mi,j的遞推公式可以得出，當(dāng)i=j的時候，mi,j=0。當(dāng)i<j的時候。k的取值范圍是i到j(luò)-1，對于k的每一個取值都可以得到一個mi,j的值，取出最小值即時mi,j的最優(yōu)化方案。遞推公式如下：可以根

2、據(jù)上式得到一個遞歸算法。本題即是求m1,n的值。用二維數(shù)組m存儲mi,j的值，用二維數(shù)組s來儲存應(yīng)當(dāng)分割的位置。以本題中第一個矩陣a)<3, 5, 2, 1,10>為例，可以得出如下矩陣：通過m數(shù)組可以得出最少的乘法次數(shù)，通過s數(shù)組可以輸出最優(yōu)方案。遇到的問題：在輸出s數(shù)組的結(jié)果的時候仍然需要遞歸調(diào)用，需要合適的控制遞歸的條件。總結(jié)：在矩陣鏈乘問題中可以看出，動態(tài)規(guī)劃結(jié)合遞歸的思想可以快捷的解決很多問題。本題中，重點是歸納出mi,j的遞推公式。二、問題：Longest Common Subsequence分析：本題即是最長公共子序列問題。假設(shè)有序列Am和序列Bn，顯然，對于每一個i

3、,j，都對應(yīng)著一個公共子序列的長度。假設(shè)長度為c，就可以得到一個二維數(shù)組cm,n。對于ci,j，當(dāng)Ai=Bj的時候，問題就轉(zhuǎn)變?yōu)榍驛1.i-1和B1.j-1的公共子序列長度的問題，所以ci，j的長度就是ci-1，j-1 + 1;同理，當(dāng)Ai != Bj的時候，ci,j應(yīng)該在ci-1,j與ci,j-1中取最大值。另外，當(dāng)i或者j等于0的時候，顯然c的值為0。由上面所述，可以得到遞推公式如下：為了解決這個問題，還如要定義另一個數(shù)組用于存放c數(shù)組中每一個元素的來源。這個來源其實就反映了公共子串?？梢酝ㄟ^箭頭表示來源，相連的箭頭序列中指向左上方的箭頭最多的一串對應(yīng)的就是最長公共子序列。比如對于題目中給

4、出的第一個例子X: xzyzzyx Y: zxyyzxz可以用一個矩陣表示計算的過程：遇到的問題：在算法中，=是屬于<還是>會給結(jié)果帶來不同。在輸出子序列的時候，最長公共子序列可能不止一個，但是最終未能解決還是只能輸出一個?？偨Y(jié)：最長公共子序列問題可以利用動態(tài)規(guī)劃很好的解決。動態(tài)規(guī)劃的思想就是根據(jù)規(guī)律獲得推導(dǎo)公式，然后解決問題。三、問題：Longest Common Substring分析：最長公共子序列問題就是和最長公共子串問題差不多，就是當(dāng)當(dāng)Ai != Bj的時候，對應(yīng)的ci，j置為0。推導(dǎo)公式如下：最終c數(shù)組的最大值max對應(yīng)的就是最長公共子串，只需要將從本位置向前述max-

5、1個的子串即是所求子串。總結(jié)：本題就是第二題的一種特殊的情況，即c數(shù)組中的值不能從左和上兩個方向獲取，其他基本相同。在代碼上，只需要修改小部分代碼就可以實現(xiàn)該問題。四、問題：Max Sum分析：求和最大的子串。這個問題和第三題很像，不過這次不用二維數(shù)組而是使用兩個標(biāo)記來標(biāo)志所求子串的起始位置（maxb）結(jié)束位置（maxe）。思路是，對于第i個元素，如果當(dāng)前元素與目前選中的序列的sum小于0，那么這么序列不會被選擇，更新sumb與sume的值；如果sum仍然大于0，則sum可以選中。比較sum與max的值，如果sum>max，則更新maxb與maxe的值。遞推公式如下：遇到的問題：在全是負(fù)

6、數(shù)時出現(xiàn)問題，后來講max的初始值設(shè)置為第一個元素的值后就能正常了?？偨Y(jié)：動態(tài)規(guī)劃能解決很多問題，找到遞推公式非常重要。五、問題：Shortest path in multistage graphs. Find the shortest path from 0 to 15 for the following graph.分析：觀察本題圖的特點，發(fā)現(xiàn)可以將圖分解為7個部分，以此可以計算到每一個節(jié)點的最短的路徑。即可求出最終的最短路徑。 總結(jié)：結(jié)合本題中的特殊情況，可以采用適當(dāng)?shù)姆椒▉硖幚怼５谌螌嶒炓?、問題：Knapsack Problem. There are 5 items that hav

7、e a value and weight list below, the knapsack can contain at most 100 Lbs. Solve the problem both as fractional knapsack and 0/1 knapsack.分析：本題是背包問題的兩個解法。對于部分背包來說比較簡單，就是將單位價值大的物品優(yōu)先放置到背包中，這樣就能在背包中獲取最大的價值。但是對于0/1背包問題來說，就相對復(fù)雜了?？梢酝ㄟ^貪心算法解決。經(jīng)過分析，我們轉(zhuǎn)化這個問題為將n件物品放置到容量為w的容器中。這里，每件物品只可能有一個狀態(tài)：放入/不放入，我們用0/1來對應(yīng)。用

8、vi,w來表示前i件物品選出重量不超過w的物品，并且構(gòu)成的最大的價值。那么，可以分析得出vi,w的遞推式。如果i=0或者w=0，顯然vI,w = 0;如果第i件物品的重量wi>w則i不可能放入容器中；如果i能夠放入容器（即wi<w）則在vi+vi-1,w-wi > vi-1,w時才可能會放入。關(guān)系式如下這樣，我們可以認(rèn)為，每一次都恰到好處的選擇了放或者不放一個物品。直到最后一個物品，我們得到的一定就是最好的結(jié)果總結(jié)：背包問題是一個典型的貪心算法的例子。在解決問題的時候可以將當(dāng)前步驟做到最好，然后通過推導(dǎo)，有可能得到一個關(guān)系式，這樣就能使問題得到解決。在本題中，我們可以通過第i

9、件物品是否應(yīng)該放在容量的w的背包中進行分析，最終得到了一個遞推式。二、問題：A simple scheduling problem. We are given jobs j1, j2 jn, all with known running times t1, t2 tn, respectively. We have a single processor. What is the best way to schedule these jobs in order to minimize the average completion time. Assume that it is a nonpreem

10、ptive scheduling: once a job is started, it must run to completion. The following is an instance。分析：這是一個線程調(diào)度問題，通過操作系統(tǒng)課程的學(xué)習(xí)，我們了解到應(yīng)當(dāng)采用短作業(yè)優(yōu)先的調(diào)度方式?？梢圆捎每焖倥判?qū)M程順序進行排序即可得到調(diào)度時間?？偨Y(jié)：在進程調(diào)度問題中，如果想獲取最短的平均周轉(zhuǎn)時間（單線程）應(yīng)當(dāng)使用短作業(yè)優(yōu)先的算法。三、問題：單源點最短路徑分析：本題中，因為路徑中存在負(fù)邊，所以應(yīng)當(dāng)使用bellman-ford算法。為了方便的使用該算法，需要首先創(chuàng)建合適的邊的數(shù)據(jù)結(jié)構(gòu)。這樣，在遍歷邊的時候

11、比較快捷。首先需要初始化每一個節(jié)點的d值，源點的d值為0，其他點的d值的初始值為max（一個足夠大的數(shù)）。表示在初始時，源點到各點都不可達(dá)。然后，對每條邊進行松弛操作，進行|V|-1次松弛之后，可以得到結(jié)果。隨后，檢測結(jié)果，如果依然存在可松弛的節(jié)點的話，說明存在權(quán)重為負(fù)的環(huán)路。表明結(jié)果不存在?？偨Y(jié)：該算法并沒有在一開始就計算是否存在權(quán)值為負(fù)的環(huán)路。而是通過結(jié)果來分析，如果沒有負(fù)環(huán)路，一定能在松弛循環(huán)結(jié)束后便不能繼續(xù)被松弛。由此，可以判斷是否存在最短路徑。所以，該算法不僅可以判斷一個圖是否存在最短路徑，還能得到最短路徑。四、問題：All-pairs shortest paths分析：所有節(jié)點對的

12、最短路徑問題，應(yīng)當(dāng)使用Johnson算法。Johnson算法需要用dijkstra和bellman-ford算法作為子程序。如果圖G=（V,E）中所有的邊權(quán)重都為非負(fù)值，可以通過在每一個節(jié)點使用dijkstra算法求出所有節(jié)點虹之間的最短路徑；如果該圖包含權(quán)值為負(fù)的邊，但是沒有權(quán)重為負(fù)的環(huán)路，那么只要計算一組新的非負(fù)權(quán)重值，然后使用同樣的方法即可。總結(jié)：Johnson算法相當(dāng)于是對dijkstra算法和bellman-ford算法的應(yīng)用，結(jié)合這兩個算法，通過使用重新賦值權(quán)重來生成非負(fù)權(quán)重，最終得到所有節(jié)點對之間的最短路徑。第四次實驗一、題目：0/1 Knapsack Problem. Ther

13、e are 5 items that have a value and weight list below, the knapsack can contain at most 100 Lbs. Solve the problem using back-tracking algorithm and try to draw the tree generated.分析：使用回溯法解決0/1背包問題?？梢杂靡粋€數(shù)組來記錄“選中”物品的情況。首先，選擇第一件物品，如果超重的話不選擇該物品；如果沒有超重，繼續(xù)添加下一個物品，這樣選擇下去，最終一定可以選擇完全部的物品。計算目前選擇物品的totalValue

14、值。繼續(xù)回溯，如果的到新的totalValue值，如果大于前一個值，那么更新該值，并且更新保存選擇的數(shù)組中?？偨Y(jié)：從8皇后問題可以發(fā)現(xiàn)回溯法的一般方法。經(jīng)過代入到這個問題中，發(fā)現(xiàn)確實可行?；厮莘ㄐ枰粋€合理的遞歸函數(shù)，這個函數(shù)的終止條件也需要認(rèn)真的分析。比如這一題和8皇后問題都可以使用元素的個數(shù)作為一個結(jié)束條件，另外還需要注意導(dǎo)致“回溯”的位置。二、題目：Solve the 8-Queen problem using back-tracking algorithm.分析：8皇后問題是回溯法的一個典型的例題。假設(shè)目前已經(jīng)在奇葩的前i（i<8）行放置了i和皇后并且位置合法。然后我們放置第j（

15、j=i+1）個皇后，先將j放置在第一列，如果合法就放置第j+1個皇后；如果放置在當(dāng)前列不合法，就將j皇后放置在第二列以此類推，如果全部不行，將會返回調(diào)用該函數(shù)的上一層函數(shù)。如果i的值等于8，說明已經(jīng)完全擺放成功，就可以輸出結(jié)果，輸出后返回上一層調(diào)用，繼續(xù)查找其他的符合題意的皇后擺放?？偨Y(jié)：使用回溯法，能后很好的解決8皇后問題。在使用回溯法是，應(yīng)當(dāng)注意如何使用遞歸調(diào)用，尤其是遞歸調(diào)用的結(jié)束條件。第2份 算法導(dǎo)論上機實驗報告冊 班級： 學(xué)號： 姓名： 周家煒 教師： 張立勇 實驗一 排序算法題目一： 1、題目描述：描述一個運行時間為(nlgn)的算法，給定n個整數(shù)的集合S和另一個整數(shù)x，該算法能確

16、定S中是否存在兩個其和剛好為x的元素。 2、所用算法：1、運用歸并排序算法 2、在已經(jīng)排好序的基礎(chǔ)上，對其運用二分查找。 3、算法分析：（1）歸并排序運用的是分治思想，時間復(fù)雜度為 (nlgn)，能夠滿足題目要求的運行時間。歸并排序的分解部分是每次將數(shù)組劃分兩個部分，時間復(fù)雜度為（1）；再對已經(jīng)分解的兩個部分再進行分解直到將數(shù)組分解成單個元素為止；解決部分是遞歸求解排序子序列；合并部分是將已經(jīng)排序的子序列進行合并得到所要的答案，時間復(fù)雜度為(lgn)。（2）二分查找算法的時間復(fù)雜度為(lgn)在題目要求的范圍內(nèi)，二分查找的條件為待查的數(shù)組為有序序列。算法的主要思想為設(shè)定兩個數(shù)，low指向最低元

17、素，high指向最高元素，然后比較數(shù)組中間的元素與待查元素進行比較。如果待查元素小于中間元素，那么表明查找元素在數(shù)組的前半段；反之，如果待查元素大于中間元素，那么表明查找元素在數(shù)組的后半段。 4、結(jié)果截圖： 5、總結(jié)：（1）在主函數(shù)中調(diào)用二分查找的時候，參數(shù)應(yīng)該為BinSearch(a,j+1,n,x-aj），從j+1開始遍歷而不是都是從第一個開始。（2）遇到的困難為：由于程序語言規(guī)定數(shù)組的下標(biāo)從0開始，而算法偽代碼要求從1開始，因此在定義數(shù)組大小的時候?qū)?shù)字加1，但是在編譯運行的時候會得不到想要的結(jié)果，出現(xiàn)數(shù)組下標(biāo)訪問錯誤。 采取的解決方案為：在開始定義數(shù)組的時候，將數(shù)組的大小定義為一個較大

18、的數(shù)字，如1000。避免在運行時出現(xiàn)錯誤，但是造成了空間的浪費。較好的方案為使用動態(tài)數(shù)組，如malloc函數(shù)。題目二： 1、題目描述：實現(xiàn)優(yōu)先級隊列，即需要支持以下操作：INSERT(S,x):把元素x插入到集合S中；MAXMUM(S):返回S中具有最大key的元素；EXTRACT-MAX(S):去掉并返回S中的具有最大key的元素；INCREASE-KEY(S,x,k)：將元素x的關(guān)鍵字值增到k。 2、所用算法：堆排序，運用堆來實現(xiàn)優(yōu)先隊列。 3、算法分析： （1）堆排序算法是引用堆這個數(shù)據(jù)結(jié)構(gòu)進行信息管理。堆排序的時間復(fù)雜度是(nlgn),但是與歸并排序不同的是堆排序具有空間的原址性，任何

19、時候都只需要常數(shù)個額外的元素空間存儲臨時數(shù)據(jù)。堆排序算法分為3個過程，MAX-HEAPIEY:調(diào)整堆以滿足小頂堆性質(zhì)，其時間復(fù)雜度為(lgn)；BUILD-MAXHEAP:從無序的輸入數(shù)據(jù)數(shù)組中構(gòu)造小頂堆，其時間復(fù)雜度為線性時間;HEAP-SORT:對數(shù)組進行原址排序，其時間復(fù)雜度為(nlgn)。 （2）在堆的基礎(chǔ)上實現(xiàn)優(yōu)先隊列INSERT、MAXMUM、EXTRACT-MAX、INCREASE-KEY，時間復(fù)雜度為(lgn)。 4、結(jié)果截圖： 5、總結(jié)： 遇到的困難：沒有理解將一個序列轉(zhuǎn)換成小頂堆的過程，因此剛開始很難將偽代碼用c語言進行實現(xiàn)。從結(jié)果可以看出，在編寫MAX-EXSTRACT函

20、數(shù)的時候，當(dāng)去掉第一個元素后，程序沒有調(diào)用MAX-HEAP進行調(diào)整堆，因此最后序列是無序狀態(tài)。題目三： 1、題目描述：實現(xiàn)quick_sort算法，并且回答以下兩個問題：（1）待排數(shù)組中的元素值都相同的情況下，運用quick_sort需要進行多少次比較？（2）對于n個元素的數(shù)組，運用quick_sort舉出需要進行比較次數(shù)的上限和下限是多少？ 2、所用算法：快速排序算法 3、算法分析：快速排序采用分治策略，時間復(fù)雜度為(nlgn),但是最壞情況下為(n2),并且快速排序算法屬于原地排序，并不需要開辟空間?？焖倥判驈?fù)雜的步驟為其分解的步驟，分解的過程：數(shù)組Ap.r被劃分為兩個子數(shù)組Ap.q-1和

21、Aq+1.r,使得Ap.q-1中的每個元素都小于Aq,而Aq也小于等于Aq+1.r中的每個元素。而在實現(xiàn)的過程總是選擇將Ar作為基準(zhǔn)點進行劃分Ap.r數(shù)組。 4、結(jié)果截圖： 5、總結(jié)： 問題答案：（1）當(dāng)選取第一個或者最后一個為基準(zhǔn)點時，當(dāng)n個元素相同的時候為最壞情況，比較次數(shù)為n*(n-1)/2;(2)快速排序比較次數(shù)最少為(nlgn),最大的比較次數(shù)為(n2)。題目四： 1、題目描述：運用分治的策略將兩個已經(jīng)排好序的序列中，找出第k大的元素，且要求時間復(fù)雜度為(lgm+lgn),其中m和n分別為兩個序列的長度。 2、所用策略：分治策略 3、算法分析： （1）分解：因為已經(jīng)是兩個獨立的的序列

22、，所以不用進行分解。 （2）解決：因為兩個序列為已經(jīng)排好的序列，因此不用分開進行排序。 （3）利用歸并排序中的merge函數(shù)，將這兩個序列分別看成是L和R兩個數(shù)組，通過開辟一個新的數(shù)組，將兩個數(shù)組合并成一個新的排好序的序列，在根據(jù)要求的k值，對新的數(shù)組進行取值。4、 結(jié)果截圖：5、 總結(jié)： （1）理解分治策略的三個步驟：分解、解決和合并對于具體問題的具體表現(xiàn)，要善于根據(jù)時間復(fù)雜度與所學(xué)的算法進行結(jié)合，找出可以利用的地方。 實驗二 動態(tài)規(guī)劃題目一： 1、題目描述：用動態(tài)規(guī)劃實現(xiàn)矩陣鏈乘，保證相乘的次數(shù)最少。 2、所用策略：動態(tài)規(guī)劃 3、算法分析： （1）最優(yōu)子結(jié)構(gòu)為：如果最優(yōu)的加括號的方式將其分

23、解為Ai.k與Ak+1.j的乘積，則分別對Ai.k與Ak+1.j加括號的方式也一定是最優(yōu)的。 （2）定義mi,j為計算矩陣Ai.j所需標(biāo)量乘法次數(shù)的最小值，對于i=j時,矩陣鏈乘只包含唯一的矩陣Ai,因此不需要做任何標(biāo)量乘法運算，所以mi,i=0;當(dāng)i<j時利用最優(yōu)子結(jié)構(gòu)來計算mi,j。 （3）矩陣鏈乘的遞歸式： （4）在算法設(shè)計的時候，需要m數(shù)組記錄Ai.j最小相乘次數(shù)，s數(shù)組記錄構(gòu)造最優(yōu)解所需要的信息，其記錄的k值指出了AiAi+1Aj的最優(yōu)括號化方案的分割點應(yīng)在AkAk+1之間。 （5）矩陣鏈乘的時間復(fù)雜度為(n3) 4、結(jié)果截圖： 5、總結(jié)： 遇到的問題：在構(gòu)建m數(shù)組和s數(shù)組的時

24、候需要構(gòu)建二維數(shù)組，而c語言中函數(shù)的參數(shù)列表中二維數(shù)組要指明數(shù)組大小，但是還沒有輸入信息的時候并沒有方法確定數(shù)組大小。 采取的方案：由于此次的例子只有兩種情況，因此對于 MATRIX_CHAIN_ORDER函數(shù)和PRINT_OPTIMAL_PARENS函數(shù)寫兩遍，大體的實現(xiàn)過程相同，只是數(shù)組的大小有所改變。并沒有解決這個情況，造成代碼的冗余。題目二： 1、題目描述：用動態(tài)規(guī)劃求下列字符串的最長公共子序列（LCS） 2、所用策略：動態(tài)規(guī)劃 3、算法分析：（1） 最優(yōu)子結(jié)構(gòu)：令X=<x1,x2,.xm>和Y=<y1,y2,.,yn>為兩個序列，Z=<z1,z2,.,z

25、k>為X和Y的任意LCS。1、如果xm=yn,則zk=xm=yn且Zk-1是Xm-1和Yn-1的一個LCS.2、如果xmyn,則zkxm意味著Z是Xm-1和Y的一個LCS；3、如果xmyn,則zkyn意味著Z是X和Yn-1的一個LCS。（2） 定義一個bi,j指向表項對應(yīng)計算ci,j時所選擇的子問題最優(yōu)解，過程返回表b和表c，cm,n保持X和Y的LCS長度。（3） LCS的遞歸式為： （4） LCS的時間復(fù)雜度為(m+n),b表的空間復(fù)雜度為(mn)。 4、結(jié)果截圖： 5、總結(jié)： 用動態(tài)規(guī)劃求取最長公共子序列的時候，要理解b數(shù)組的用途和使用。 遇到的困難：編寫的代碼無法針對字符串大小未定

26、情況下，進行求解LCS這導(dǎo)致了代碼的冗余。題目三： 1、題目描述：用動態(tài)規(guī)劃求取以下字符串的最長公共子串。 2、所用策略：動態(tài)規(guī)劃 3、算法分析： （1）最優(yōu)子結(jié)構(gòu)：令X=<x1,x2,.xm>和Y=<y1,y2,.,yn>為兩個序列，Z=<z1,z2,.,zk>為X和Y的任意最長公共子串。1、如果xm=yn,則zk=xm=yn且Zk-1是Xm-1和Yn-1的一個最長公共子串.2、如果xmyn,則zkxm意味著Z是Xm-1和Y的一個最長公共子串；3、如果xmyn,則zkyn意味著Z是X和Yn-1的一個最長公共子串。 （2）定義Li,j為以xi和yj為結(jié)尾的相

27、同子串的最大長度。記錄著X和Y的最長公共子串的最大長度。 （3）最長公共子串的遞歸式： （4）最長公共子串的時間復(fù)雜度為(mn)，空間復(fù)雜度為(mn)。 4、結(jié)果截圖： 5、總結(jié)： 要同上述的最長公共子序列進行對比，區(qū)分他們的不同之處。也要理解用動態(tài)規(guī)劃求解時的相同之處和不同之處。題目四： 1、題目描述：給定n個整數(shù)（可能為負(fù)數(shù)）組成的序列，a1,a2.an,求該序列ai+ai+1.aj的子段和的最大值。 2、所用策略：動態(tài)規(guī)劃 3、算法分析: (1)最優(yōu)子結(jié)構(gòu)：定義當(dāng)所給整數(shù)全為負(fù)數(shù)的時候，最大子段和為0,則最大子段和為max0,ai+ai+1.+aj,1ijn (2)引入一個輔助數(shù)組b,動

28、態(tài)規(guī)劃的分解分為兩步：(1)計算輔助數(shù)組的值；(2)計算輔助數(shù)組的最大值。輔助數(shù)組bj用來記錄以j為尾的子段以及集合中的最大子段和。 (3)最大子段和的遞歸式： (4)最大子段和使用動態(tài)規(guī)劃進行計算的時間復(fù)雜度為(n)。 4、結(jié)果截圖： 5、總結(jié)： 在求解集合的最大子段和的時候，要對比不同解決方法的不同之處，感受用動態(tài)規(guī)劃解決的便捷。題目五： 1、題目描述：利用動態(tài)規(guī)劃求出多段圖中的最短路徑 2、所用策略：動態(tài)規(guī)劃 3、算法分析： （1）可以由圖可知，圖中的頂點講圖劃分7個階段，分別了解每個階段可以有幾種可供選擇的店，引入fk表示狀態(tài)k到終點狀態(tài)的最短距離。最優(yōu)子結(jié)構(gòu)為：當(dāng)前狀態(tài)的fk由上個狀

29、態(tài)的fk-1和狀態(tài)k-1到狀態(tài)k的距離決定決策：當(dāng)前狀態(tài)應(yīng)在前一個狀態(tài)的基礎(chǔ)上獲得。決策需要滿足規(guī)劃方程,規(guī)劃方程：f(k)表示狀態(tài)k到終點狀態(tài)的最短距離。 （2）多段圖最短路徑的遞歸式： 4、結(jié)果截圖： 無。 5、總結(jié)： （1）遇到的問題：無法將多段圖的每個階段點的狀態(tài)表示并記錄下來。并不了解如何將動態(tài)規(guī)劃與貪心算法的如迪杰斯特拉算法進行對比，真正從最優(yōu)子結(jié)構(gòu)將最短路徑表示出來。實驗三 貪心算法題目一： 1、題目描述：背包問題，即分別計算出在0-1背包和分?jǐn)?shù)背包情況下的計算結(jié)果。 2、所用策略：動態(tài)規(guī)劃和貪心策略 3、算法分析： （1）0-1背包問題：所選擇的的貪心策略為按照選擇單位重量價值

30、最大的物品順序進行挑選。算法的步驟：設(shè)背包容量為C，共有n個物品，物品重量存放在數(shù)組Wn中，價值存放在數(shù)組Vn中，問題的解存放在數(shù)組Xn中。第一步：改變數(shù)組W和V的排列順序，使其按單位重量價值Vi/Wi降序排列，并將數(shù)組Xn初始化為0；第二步初始化i=0，設(shè)計一個循環(huán)，循環(huán)終止條件為（Wi>C），循環(huán)體為將第i個物品放入背包：Xi=1;C=C-Wi;i+；最后一步：將結(jié)果存入到X數(shù)組中。 （2）分?jǐn)?shù)背包問題：所選擇的的貪心策略為按照選擇單位重量價值最大的物品順序進行挑選。算法的步驟：設(shè)背包容量為C，共有n個物品，物品重量存放在數(shù)組Wn中，價值存放在數(shù)組Vn中，問題的解存放在數(shù)組Xn中。第

31、一步：改變數(shù)組W和V的排列順序，使其按單位重量價值Vi/Wi降序排列，并將數(shù)組Xn初始化為0；第二步初始化i=0，設(shè)計一個循環(huán)，循環(huán)終止條件為（Wi>C），循環(huán)體為將第i個物品放入背包：Xi=1;C=C-Wi;i+；最后一步：將結(jié)果存入到X數(shù)組中Xi=C/Wi。 （3）分?jǐn)?shù)背包問題所采用的貪心策略之不能得到最優(yōu)解，是由于物品不允許分割，因此，無法保證最終能將背包裝滿，部分閑置的背包容量使背包的單位重量價值降低了。 （4）分?jǐn)?shù)背包問題采用選擇單位重量價值最大的物品順序進行挑選，其算法的時間復(fù)雜度為(nlgn)。 4、結(jié)果截圖： 5、總結(jié)： 使用貪心策略解決0-1背包問題得出的結(jié)果并不是最優(yōu)

32、解，這是由于所用的選擇策略不同。題目二： 1、題目描述：一個簡單的調(diào)度問題，給予工作編號為J1，J2.Jn，已知所以工作的運行時間分別為T1，T2.TN。有一個單獨的處理器，為了安排這些工作以到達(dá)減少平均完成時間的最好方法是什么。假定它是一個非搶占式調(diào)度：一旦工作開始，它必須運行完成。 2、所用策略：貪心策略 3、算法分析： （1）由于是非搶占式調(diào)度，所以應(yīng)該盡量讓時間短的工作先做，然后再讓時間長的工作做。這里我們使用堆進行排序，建立一個小頂堆，然后每次拿出小頂堆上的最小元素，并使用sum中的公式就可以算出平均完成時間。堆排序的時間復(fù)雜度是O(nlgn)，其中BuildMinHeap的時間復(fù)雜

33、度是O(n)，而BuildMinHeap()的時間復(fù)雜度是O(lgn)。其中HeapExtractMin(N)的時間復(fù)雜度是O(lgn)。 4、結(jié)果截圖： 5、總結(jié)： 由于前面對于堆排序和優(yōu)先隊列的MIN-EXTRACT函數(shù)的錯誤沒有解決，導(dǎo)致在調(diào)度中，需要每次去運行時間最短的工作時發(fā)生了錯誤。題目三： 1、題目描述:以A為源點，求出下圖的單源點最短路徑。 2、所用算法：由于圖中存在負(fù)權(quán)值，所以Dijkstra算法無法使用，因此采用Bellman-Ford算法求取圖的單源點最短路徑。 3、算法分析： （1）Bellman-Ford算法通過對邊進行松弛操作來漸近地降低從源點A到每個結(jié)點的最短路徑

34、的估計值，直到該估計值與實際的最短路徑權(quán)重(A,v)相同為止。該算法返回TRUE值當(dāng)且僅當(dāng)輸入圖中不包含可以從源結(jié)點到達(dá)的權(quán)重為負(fù)值的環(huán)路。 （2）Bellman-Ford算法的執(zhí)行步驟：1、初始化：將除源點外的所有頂點的最短距離估計值dv+, ds0；2、迭代求解：反復(fù)對邊集E中的每條邊進行松弛操作，使得頂點集V中的每個頂點v的最短距離估計值逐步逼近其最短距離；（運行|v|-1次）3、檢驗負(fù)權(quán)回路：判斷邊集E中的每一條邊的兩個端點是否收斂。如果存在未收斂的頂點，則算法返回false表明問題無解；否則算法返回true，并且從源點可達(dá)的頂點v的最短距離保存在dv中。 （3）算法適用范圍和條件： 1.單源最短路徑(從源點A到其它所有頂點v)； 2.有向圖&無向圖(無向圖可以看作(u,v),(v,u)同屬于邊