動態(tài)規(guī)劃ppt課件-文庫吧資料
2024-11-09 18:12本頁面
【正文】 ti=i。k++) thissum+=a[k]。 for(k=i。j=n。i=n。bestj) { int sum=0。 依此定義，所求的最優(yōu)值為： 例如，當 (a1,a2, a3, a4, a5,a6)=( 2,11,4,13,5,2 )時，最大子段和為： ?????? ?????jikknji a1 m a x,0m a x? ? 202141142???????kka34 1. 一個簡單算法 int MaxSum(int n, int *a, int amp。 } 計算最優(yōu)值 0 1 2 3 4 5 6 yi B D C A B A 0 xi 0 0 0 0 0 0 0 1 A 0 0 0 0 1 1 1 2 B 0 1 1 1 1 2 2 3 C 0 1 1 2 2 2 2 4 B 0 1 1 2 2 3 3 5 D 0 1 2 2 2 3 3 6 A 0 1 2 2 3 3 4 7 B 0 1 2 2 3 4 4 i j 0 1 2 3 4 5 6 yi B D C A B A 0 xi 1 A ↑ ↑ ↑ ↖ ← ↖ 2 B ↖ ← ← ↑ ↖ ← 3 C ↑ ↑ ↖ ← ↑ ↑ 4 B ↖ ↑ ↑ ↑ ↖ ← 5 D ↑ ↖ ↑ ↑ ↑ ↑ 6 A ↑ ↑ ↑ ↖ ↑ ↖ 7 B ↖ ↑ ↑ ↑ ↖ ↑ i j 33 最大子段和 問題描述： 給定由 n個整數(shù)（包含負整數(shù)）組成的序列 a1,a2,...,an，求該序列子段和的最大值。 } else if (b[i][j]== 2) LCS(i1， j， x， b)。 if (b[i][j]== 1){ LCS(i1， j1， x， b)。 b[i][j]=3。 b[i][j]=2。 b[i][j]=1。 j = n。 i = m。 i++) c[0][i] = 0。 for (i = 1。 i = m。 0 1 2 3 4 ... n 0 0 0 0 0 0 … 0 1 0 2 0 3 0 4 0 … … m 0 i j 30 void LCSLength(int m， int n， char *x， char *y， int **c， int **b) { int i， j。 b[i][j]=3。 b[i][j]=2。 b[i][j]=1。 j = n。 i = m。 i++) c[0][i] = 0。 for (i = 1。 i = m。 其它情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下： 29 void LCSLength(int m， int n， char *x， char *y， int **c， int **b) { int i， j。 當 i=0或 j=0時，空序列是 Xi和 Yj的最長公共子序列。 用 c[i][j]記錄序列和的最長公共子序列的長度。0,。 3. 若 xm≠yn且 zk≠yn，則 Z是 X和 yn1的最長公共子序列。 最長公共子序列的結(jié)構(gòu) 設(shè)序列 X={x1,x2,…,x m}和 Y={y1,y2,…,y n}的最長公共子序列為 Z={z1,z2,…,z k} ，則 1. 若 xm=yn，則 zk=xm=yn，且 zk1是 xm1和 yn1的最長公共子序列。 27 1. 2個序列的最長公共子序列包含了這 2個序列的前綴的最長公共子序列 。 給定 2個序列 X和 Y，當另一序列 Z既是 X的子序列又是 Y的子序列時，稱 Z是序列 X和 Y的 公共子序列 。 26 最長公共子序列 若給定序列 X={x1,x2,…,x m}，則另一序列 Z={z1,z2,…,z k}，是 X的子序列是指存在一個嚴格遞增下標序列 {i1,i2,…,i k}使得對于所有 j=1,2,…,k 有： zj=xij。 return u。 s[i][j] = k。 k++) { int t = LookupChain(i， k) + LookupChain(k+1， j) + p[i1]*p[k]*p[j]。 for (int k = i+1。 int u = LookupChain(i， i) + LookupChain(i+1， j) + p[i1]*p[i]*p[j]。 } 1:4 4:4 1:3 3:4 1:2 2:4 1:1 4:4 2:3 3:4 2:2 4:4 3:3 2:2 1:1 3:3 1:2 2:3 1:1 3:3 2:2 4:4 3:3 2:2 1:1 3:3 2:2 已經(jīng)計算 過的單元 25 int LookupChain(int i， int j) { if (m[i][j] 0) return m[i][j]。 s[i][j] = k。 k++) { int t = RecurChain(i， k) + RecurChain(k+1， j) + p[i1]*p[k]*p[j]。 for (int k = i+1。 int u = RecurChain(i， i) + RecurChain(i+1， j) + p[i1]*p[i]*p[j]。因此用動態(tài)規(guī)劃算法只需要多項式時間，從而獲得較高的解題效率。 動態(tài)規(guī)劃算法，對每一個子問題只解一次，而后將其解保存在一個表格中，當再次需要解此子問題時，只是簡單地用常數(shù)時間 查看一下 結(jié)果。 同一個問題可以有多種 方式刻劃它的最優(yōu)子結(jié)構(gòu)，有些表示方法的求解速度更快（空間占用小，問題的維度低） 23 → ↓ r 動態(tài)規(guī)劃算法的基本要素 二、重疊子問題 遞歸算法求解問題時，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計算多次。 22 動態(tài)規(guī)劃算法的基本要素 一、最優(yōu)子結(jié)構(gòu) 利用問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，以自底向上的方式遞歸地從子問題的最優(yōu)解逐步構(gòu)造出整個問題的 最優(yōu)解。 這種性質(zhì)稱為 最優(yōu)子結(jié)構(gòu)性質(zhì) 。 printf(Multiply A%d,%d and A%d,%d\n, i,s[i][j],s[i][j]+1,j)。 TraceBack(i,s[i][j])。照此遞推下去，最終可以確定 A[1:n]的最優(yōu)完全加括號方式，即構(gòu)造出問題的一個最優(yōu)解。 20 構(gòu)造最優(yōu)解 s[i][j]已經(jīng)存儲了構(gòu)造最優(yōu)解所需要的足夠的信息。 因此算法的計算 時間上界為 O(n3)。 2. 循環(huán)體內(nèi)的計算量為O(1)。 s[i][j] = k。 k++) { int t = m[i][k] + m[k+1][j] + p[i1]*p[k]*p[j]。 for (int k = i+1。 m[i][j] = m[i+1][j]+ p[i1]*p[i]*p[j]。 i = n r+1。 r = n。 i++) m[i][i] = 0。 → ↓ r 19 計算最優(yōu)值 void MatrixChain(int *p， int n， int **m， int **s) { for (int
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1