算法實驗06動態(tài)規(guī)劃

1、課程實驗報告課程名稱算法分析與設(shè)計班級實驗日期姓名學(xué)號實驗成績實驗名稱實驗6：動態(tài)規(guī)劃的應(yīng)用實 驗 目 的 及 要 求1.理解動態(tài)規(guī)劃算法的基本要素；2 .掌握動態(tài)規(guī)劃的基本步驟；3.掌握動態(tài)規(guī)劃的基本思想。實驗環(huán)境操作系統(tǒng)：WindowsIDE： Visual C+實 驗 內(nèi) 容數(shù)塔問題從數(shù)塔的頂層出發(fā)，在每一個結(jié)點可以選擇向左走或向右走，一直走到最底層， 要求找出一條路徑，使得路徑上的數(shù)值和最大。要求隨機生成一個高度為N的 數(shù)塔(N=4,8,16,32)，分別用動態(tài)規(guī)劃法和任一種其它方法(例如蠻力法、回 溯法、分治法等)進行求解，分析兩種方法的時間復(fù)雜度，并畫出時間隨N變 化的曲線圖。動態(tài)

2、規(guī)劃運行過程試過程v 1 I 3 -V IT 5W MT 、J V3378 92?1 36 7827 34 73 15100 50 27 39 2949 13 15 8 18 2330 54 24 47 56 27 757 6 44 59 50 57 80 36最大值為：476最大值的路徑為：33789127100495444所用時間為：。毫秒3378 92?1 36 7827 34 73 15100 50 27 39 2949 13 15 8 13 2330 54 24 47 56 27 757 6 44 59 50 57 80 363H 04 亍蛀 S AO CH OO f!7 O1運行到

3、一定規(guī)模：位W4471明%處4tJ&95678082879132975557833779939669915096 SO 6754858272507*9872947373347760768286987152991009556783所用時間為：4毫秒7294 605 2893 53 41 9164 17 94 3? 2018 1 53 65 65 3781 33 84 74 47 93 19C 44 M2 44 OT C4 母M采用遞歸算法：|J J 4/ 4Z00744uIV4086 81 40 315304510988686657038 2 45 93811355743844959347597

4、8 85 55 5661 6228 45 36 4 7179555 97 98 14 60 62 55 21 65 94 97 35 55 17 65最大路徑值為：1059所用時間為：15毫秒5861 1063 12 7663 39 30 10033 23 58 7 2199 15 12 83 6159 10 100 75 5 65 61S9 6 25 24 48 66 98 29總結(jié)通過分析動態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移方程dpij = max(dpi + 1j, dpi + 1j+1) + dataij,最后的結(jié)果保存在dp00中，可以得出時間復(fù)雜度為：O(n), 而采用遞歸的方法，運行到規(guī)模為32的

5、就顯得比較吃力。l2E+091E+09/r600000000/一200000000/123456789附錄#include#include #include#include#include#define MAX 1000using namespace std;int N; /輸入規(guī)模clock_t begintimes, endtimes; /clock_t為clock()函數(shù)返回的變量類型double duration;/運行時間計算隨機數(shù)產(chǎn)生int number()(int a = rand() % 100 + 1;return a;定義結(jié)構(gòu)體typedef struct (int x,

6、y;int value;Node;定義一個二維數(shù)組存儲塔Node AMAXMAX;Node BMAXMAX;輸出函數(shù)，兩重for循環(huán)輸出void show()(for (int i = 0; i N; i+)(for (int j = 0; j=i; j+)cout Aij.value ”;cout endl;初始化函數(shù)void init()(srand(unsigned)time(NULL); /給一個時間種子for (int i = 0; i N; i+)(for (int j = 0; j = i; j+)(Aij.value = number();return;/動態(tài)規(guī)劃函數(shù)void

7、dp()(begintimes = clock(); /計時開始int t, x1, y1; /臨時計數(shù)for (int m = 0; mN; m+) /初始化B結(jié)構(gòu)體數(shù)組for (int n = 0; n= 0; j-) for (int i = 0; i Aj + 1i + 1.value) /當(dāng)前數(shù)大于 后邊數(shù)t = Aj + 1i.value; /規(guī)劃Aji.x = j + 1;Aji.y = i;else/當(dāng)前數(shù)小于后邊數(shù)t = Aj + 1i + 1.value;Aji.x = j + 1; 規(guī)劃 Aji.y = i + 1;Aji.value = Aji.value + t;en

8、dtimes = clock();/計時結(jié)束x1 = A00.x;y1 = A00.y;cout 最大值為： A00.value endl;cout最大值的路徑為：endl;coutB00.value”;for (int i = 0; iN-1; i+)(t = x1;coutBx1y1.value” ;x1 = Aty1.x;y1 = Aty1.y;cout endl;/回溯遞歸求解，較簡單，但是時間復(fù)雜度高int MaxSum(int l, int r)if (l = N)return Alr.value;elsereturn max(MaxSum(l + 1, r), MaxSum(l

9、+ 1, r + 1) + Alr.value;/主函數(shù)int main()N = 4;do (N *= 2; 依次增大輸入規(guī)模init(); /進行初始化show(); 進行原始塔展示這里是遞歸回溯法begintimes = clock(); /計時開始 int result=MaxSum(0,0);endtimes = clock(); /計時結(jié)束cout 最大路徑值為： result endl;/dp();/動態(tài)規(guī)劃求解duration = 1000 * (double)(endtimes - begintimes) / CLK_TCK; /總共 用時(毫秒)cout 所用時間為： duration 毫秒” endl;記錄實驗結(jié)果，注意運行一次手動進行數(shù)據(jù)轉(zhuǎn)移，清除數(shù)據(jù)/