目錄
一、實驗目的
二、實驗環境
三、實驗內容
四、核心代碼
五、記錄與處理
六、思考與總結
七、完整報告和成果文件提取鏈接
一、實驗目的
????????掌握動態規劃求解問題的思想；針對不同的問題，會利用動態規劃進行設計求解以及時間復雜度分析，并利用JAVA/C/C++等編程語言開展編碼實踐（語言自選）。
????????理解兩組序列的最長公共子序列問題，能夠利用動態規劃，開展問題的最優子結構性質分析、子結構遞歸關系構建、自底向上最優值求解以及最優解構造。
二、實驗環境
????????1、機房電腦? Window11
????????2、Eclipse/Dev-C++等
三、實驗內容
????????實驗要求：
????????①掌握動態規劃求解問題的策略及思路；
????????①基于動態規劃開展最長公共子序列問題的算法設計與優化；
????????③對上述算法進行時間復雜性分析，并輸出程序運行時間及運行結果。
實驗原理：
1、按照自己的理解，總結描述動態規劃求解問題的思路策略；
??? 動態規劃是針對于遞歸分治所存在的缺點而設計出來的算法思想，遞歸分治算法存在大量子問題被重復計算，效率低下的問題，如下圖，多個子節點在不同的遞歸表達式中被重復計算，增加了算法冗余度。
????? 而在動態規劃的算法中，雖然與分治法類似，但是動態規劃卻在思考如果能夠保存已解決的子問題的答案，而在需要時再直接找出已求得的節點，就可以避免大量重復計算，從而得到多項式時間算法，這樣就可以避免同一個問題被多次計算的問題，如下圖。
動態規劃是解決具有重疊子問題和最優子結構性質的問題的有效方法。 它的基本原理是將大問題分解為小問題，通過保存中間結果來避免重復計算，從而提高算法的效率。動態規劃方法所耗時往往遠少于一般解法。
2、針對最長公共子序列問題，如何利用動態規劃進行建模設計與優化；
①給出求解過程及建模思路，以及子序列的構造原理；
????? 用動態規劃算法可以解決最長公共子序列這一經典問題，公共子序列問題，尋找兩個字符串中都存在的最長子序列，這個最長子序列可以不是連續的，但是要保證其相對順序一樣
先找出最優問題特點：設有兩個序列X={ x1
, x2
,…, xm
}和Y={ y1
, y2
,…, yn
}的最長公共子序列為Z={ z1
, z2
,…, zk
}
(1)若xm
=yn
，則zk
=xm
=yn
，且zk-1
是xm-1
和yn-1
的最長公共子序列。
(2)若xm
≠yn
?且Zk
≠xm
，則zk
是xm-1
和Y的最長公共子序列。
(3)若xm
≠yn
?且Zk
≠yn
，則zk
是X和yn-1
的最長公共子序列。
所以2個序列的最長公共子序列包含了這2個序列的前綴的最長公共子序列，最長公共子序列問題具有最優子結構性質。
定義遞歸關系；根據以上已經求得的最長公共子序列問題的性質，我們可以知道如下圖：
根據此遞歸關系我們可以求得以下遞歸方程，其中c [i][j]數組記錄序列的最長公共子序列長度。首先當i=0或j=0時，有一個序列為空，所以c [i][j]=0
該算法的時間復雜度為O(m n)
②針對序列X={a,b,a,d,e},Y={a,r,f,a,e}，給出子結構二維數組。
根據上列的c[i][j]表達式可以求出：
| X Y | ? | a | b | a | d | e |
| ? | 0 | 0 | 0 | 0 | 0 | 0 |
| a | 0 | 1 | 1 | 1 | 1 | 1 |
| r | 0 | 1 | 1 | 1 | 1 | 1 |
| f | 0 | 1 | 1 | 1 | 1 | 1 |
| a | 0 | 1 | 1 | 2 | 2 | 2 |
| e | 0 | 1 | 1 | 2 | 2 | 3 |
由此表可知公共子序列長度為3，是aae
四、核心代碼
int c[10001][10001]; //數組記錄序列的最長公共子序列長度
int b[10001][10001]; //標記是遞歸關系中的哪一種情況 void LCS_num(int m,int n,char *X,char *Y){for(int i=1;i<=m;i++){ //首先當i=0或j=0時，代表有一個序列為空，所以c [i][j]=0c[i][0]=0;}for(int j=1;j<=n;j++){c[0][j]=0;}for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(X[i-1]==Y[j-1]){ //當X序列的第i個元素和Y序列的第j個元素相等時 c[i][j]=c[i-1][j-1]+1; //那么當前i元素一定再最長公共子序列里，長度+1 b[i][j]=1; //b數組用來標記1，表示此情況}else if(c[i-1][j]>=c[i][j-1]){ //如果不相等，此時分兩種情況進行比較 c[i][j]=c[i-1][j]; b[i][j]=2; }else{ c[i][j]=c[i][j-1];b[i][j]=3; }}}五、記錄與處理
實驗數據及結果分析：
輸入實例中的數據，與自行計算的結果一致，同時還輸出了b數組，代表每個字符進行匹配的情況。
b數組標記1，表示X序列的第i個元素和Y序列的第j個元素相等；
b數組標記2，表示{X減去最后一個元素}與Y的最長公共子序列的序列較大；
b數組標記3，X與 {Y減去最后一個元素}的最長公共子序列的序列較大。
最長公共子序列為3，aae
六、思考與總結
動態規劃算法通常分為以下幾個步驟：
找出最優問題特點：明確問題的最優解具有什么樣的性質，這是使用動態規劃的前提。
定義遞歸關系：根據問題的最優子結構，建立子問題之間的遞歸關系，這是動態規劃的核心。
自底向上計算每一步結果：利用遞歸關系，從最小的子問題開始，逐步求解更大的子問題，直到求解出原問題。
構造最優解：根據保存的中間結果，構造出原問題的最優解。
七、完整報告和成果文件提取鏈接
完整可運行代碼以及相關實驗報告以下鏈接可獲取：
鏈接: https://pan.baidu.com/s/1iss6-C2nxZQGkEpo-WDn0A?pwd=g5cg 提取碼: g5cg?
)
)
