第3章 動態(tài)規(guī)劃算法實(shí)驗(yàn)指導(dǎo)

第3章動態(tài)規(guī)劃算法實(shí)驗(yàn)3.1動態(tài)規(guī)劃算法的實(shí)現(xiàn)與時(shí)間復(fù)雜度測試實(shí)驗(yàn)?zāi)康木幊虒?shí)現(xiàn)經(jīng)典的動態(tài)規(guī)劃算法，理解動態(tài)規(guī)劃算法設(shè)計(jì)的基本思想、程序?qū)崿F(xiàn)的相關(guān)技巧，加深對動態(tài)規(guī)劃算法設(shè)計(jì)與分析思想的理解。通過程序的執(zhí)行時(shí)間測試結(jié)果，與理論上的時(shí)間復(fù)雜度結(jié)論進(jìn)行對比、分析和驗(yàn)證。原理解析■動態(tài)規(guī)劃算法的基本思想動態(tài)規(guī)劃是一種在數(shù)學(xué)和計(jì)算機(jī)科學(xué)中使用的、用于求解包含重疊子問題的最優(yōu)化問題的有效方法。其基本思想是：將原問題分解為相似的子問題，在求解的過程中通過子問題的解描述并求出原問題的解。動態(tài)規(guī)劃的思想是多種算法的基礎(chǔ)，被廣泛應(yīng)用于計(jì)算機(jī)科學(xué)和工程領(lǐng)域，在查找有很多重疊子問題的情況的最優(yōu)解時(shí)有效。它將問題重新組合成子問題，為了避免多次解決這些子問題，它們的結(jié)果都逐漸被計(jì)算并保存，從小規(guī)模的子問題直到整個(gè)問題都被解決。因此，動態(tài)規(guī)劃對每一子問題只做一次計(jì)算，具有較高的效率。■測試算法0-1背包問題是使用動態(tài)規(guī)劃算法求解的代表問題，算法如下：KnapsackDP({w1,w2,…，wn),(v1,v2,…，vn}, C)fori=0tondom[i,0]=0endforforj=0toCdom[0,j]=0endforfori=1tondoforj=1toCdom[i,j]=m[i-1,j]ifwijthenm[i,j]=max{m[i,j],m[i-1,j-wi]+vi}endifendforendforreturnm[n,C]算法的時(shí)間復(fù)雜度為0(^Qo實(shí)驗(yàn)內(nèi)容編程實(shí)現(xiàn)以上求解0-1背包問題的動態(tài)規(guī)劃算法，并通過手動設(shè)置、生成隨機(jī)數(shù)獲得實(shí)驗(yàn)數(shù)據(jù)。記錄隨著輸入規(guī)模增加算法的執(zhí)行時(shí)間，分析并以圖形方式展現(xiàn)增長率；測試、驗(yàn)證、對比算法的時(shí)間復(fù)雜度。實(shí)驗(yàn)步驟和要求編程實(shí)現(xiàn)以上算法，并進(jìn)行測試，保證程序正確無誤。其中，分別在程序開始和結(jié)束處設(shè)置記錄系統(tǒng)當(dāng)前時(shí)間的變量、用于計(jì)算程序執(zhí)行的時(shí)間(以毫秒(ms)作為程序執(zhí)行時(shí)間的計(jì)數(shù)單位)。測試C值不變的情形下隨著n增加、程序執(zhí)行時(shí)間增加的趨勢。對于C=200、400、800、2000這四種情形，分別使用實(shí)驗(yàn)1中的隨機(jī)數(shù)生成算法生成n個(gè)隨機(jī)整數(shù)作為n個(gè)物品的重量，再生成n個(gè)隨機(jī)整數(shù)作為n個(gè)物品的價(jià)值(n=10,20,40,100,200,400,800,2000)。對于每個(gè)C值，記錄隨著n增加程序的執(zhí)行時(shí)間，并使用MSExcel圖表繪制工具生成各不同C值情形下程序執(zhí)行時(shí)間的對比曲線圖(4條折線)。與理論上的時(shí)間復(fù)雜度結(jié)論進(jìn)行對比分析，完成實(shí)驗(yàn)報(bào)告。

實(shí)驗(yàn)3.2動態(tài)規(guī)劃算法的適應(yīng)性測試1.實(shí)驗(yàn)?zāi)康膶τ谕粏栴}，編程實(shí)現(xiàn)其分治算法和動態(tài)規(guī)劃算法，通過對比分析，理解動態(tài)規(guī)劃算法的適用情形。通過程序的執(zhí)行時(shí)間測試結(jié)果，與理論結(jié)論進(jìn)行對比、分析和驗(yàn)證。2.原理解析■分治算法與動態(tài)規(guī)劃算法的對比：針對子問題是否重疊雖然很多問題均可分解為子問題、動態(tài)規(guī)劃和分治算法都是通過子問題的解決來獲得原問題的解。然而，分治算法適用于子問題不重疊（即相互獨(dú)立）的情形，對于子問題重疊的情形分治法具有較高的時(shí)間復(fù)雜度，動態(tài)規(guī)劃是針對這類情形的有效算法。■測試算法斐波納契數(shù)列在現(xiàn)代物理、準(zhǔn)晶體結(jié)構(gòu)、化學(xué)等領(lǐng)域都有直接的應(yīng)用。斐波那契數(shù)列指的是這樣一個(gè)數(shù)列：1、1、2、3、5、8、13、21、……，這個(gè)數(shù)列從第三項(xiàng)開始，每一項(xiàng)都等于前兩項(xiàng)之和，即:'('(n)=〃(n-1)，f(n-2)n=1,2

n>3直觀地，斐波納契數(shù)列可遞歸地得到，算法如下:DAC_f(n)if(n==1)or(n==2)thenreturn1elsereturnf(n-1)+f(n-2)endif通過理論分析已經(jīng)得出結(jié)論：以上遞歸算法隨著n增大有指數(shù)計(jì)算時(shí)間。對于n的多項(xiàng)式個(gè)數(shù)的子問題，顯然指數(shù)計(jì)算時(shí)間是不現(xiàn)實(shí)的?；趧討B(tài)規(guī)劃算法可高效地求解Fibonacci數(shù)問題，算法如下:DP_f(n)Initializef[1..n]fori=1tondoif(i==1)or(i==2)thenf[i]=1elsef[i]=f[i-1]+f[i-2]endifendforreturnf[n]算法的時(shí)間復(fù)雜度為。3)。實(shí)驗(yàn)內(nèi)容編程實(shí)現(xiàn)以上求斐波納契數(shù)的分治算法和動態(tài)規(guī)劃算法。對于每個(gè)算法，記錄隨著斐波納契數(shù)數(shù)列大小增加基本操作的執(zhí)行次數(shù)，分析并以圖形方式展現(xiàn)增長率；對比這兩個(gè)算法，隨著數(shù)列大小增加算法增長率的變化趨勢；測試、驗(yàn)證、對比理論結(jié)論。實(shí)驗(yàn)步驟和要求“加法”是以上兩個(gè)斐波納契數(shù)算法的基本操作。編程實(shí)現(xiàn)以上DAC_f和DP_f算法，并進(jìn)行測試，在其中設(shè)置加法執(zhí)行次數(shù)的計(jì)數(shù)器變量。分別測試不同n值(n=5,10,15,20,25,30)情形下DAC_f和DP_f算法的加法次數(shù)，記錄加法次數(shù)，并使用MSExcel圖表繪制工具生成各不同n值情形下以上兩個(gè)算法加法次數(shù)的對比曲線圖(2條折線)。與兩個(gè)算法時(shí)間復(fù)雜度的理論結(jié)論進(jìn)行對比分析，總結(jié)分治與動態(tài)規(guī)劃算法的適用條件和特點(diǎn)，