第3章 動態(tài)規(guī)劃算法實驗指導

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

實驗3.2動態(tài)規(guī)劃算法的適應性測試1.實驗目的對于同一問題，編程實現(xiàn)其分治算法和動態(tài)規(guī)劃算法，通過對比分析，理解動態(tài)規(guī)劃算法的適用情形。通過程序的執(zhí)行時間測試結(jié)果，與理論結(jié)論進行對比、分析和驗證。2.原理解析■分治算法與動態(tài)規(guī)劃算法的對比：針對子問題是否重疊雖然很多問題均可分解為子問題、動態(tài)規(guī)劃和分治算法都是通過子問題的解決來獲得原問題的解。然而，分治算法適用于子問題不重疊（即相互獨立）的情形，對于子問題重疊的情形分治法具有較高的時間復雜度，動態(tài)規(guī)劃是針對這類情形的有效算法?！鰷y試算法斐波納契數(shù)列在現(xiàn)代物理、準晶體結(jié)構(gòu)、化學等領(lǐng)域都有直接的應用。斐波那契數(shù)列指的是這樣一個數(shù)列：1、1、2、3、5、8、13、21、……，這個數(shù)列從第三項開始，每一項都等于前兩項之和，即:'('(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ù)計算時間。對于n的多項式個數(shù)的子問題，顯然指數(shù)計算時間是不現(xiàn)實的?；趧討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]算法的時間復雜度為。3)。實驗內(nèi)容編程實現(xiàn)以上求斐波納契數(shù)的分治算法和動態(tài)規(guī)劃算法。對于每個算法，記錄隨著斐波納契數(shù)數(shù)列大小增加基本操作的執(zhí)行次數(shù)，分析并以圖形方式展現(xiàn)增長率；對比這兩個算法，隨著數(shù)列大小增加算法增長率的變化趨勢；測試、驗證、對比理論結(jié)論。實驗步驟和要求“加法”是以上兩個斐波納契數(shù)算法的基本操作。編程實現(xiàn)以上DAC_f和DP_f算法，并進行測試，在其中設置加法執(zhí)行次數(shù)的計數(shù)器變量。分別測試不同n值(n=5,10,15,20,25,30)情形下DAC_f和DP_f算法的加法次數(shù)，記錄加法次數(shù)，并使用MSExcel圖表繪制工具生成各不同n值情形下以上兩個算法加法次數(shù)的對比曲線圖(2條折線)。與兩個算法時間復雜度的理論結(jié)論進行對比分析，總結(jié)分治與動態(tài)規(guī)劃算法的適用條件和特點，