《算法設計與分析》第07章

l 指 出 ， 一 個 最 優(yōu) 策 略 具 有 這 樣 的 性質(zhì) ， 不 論 過 去 狀 態(tài) 和 決 策 如 何 ， 對 前 面 的 決 策 所形 成 的 狀 態(tài) 而 言 ， 其 余 決 策 必 定 構(gòu) 成 最 優(yōu) 策 略 。這 便 是 最 優(yōu) 決 策 序 列 的 最 優(yōu) 子 結(jié) 構(gòu) 特 性 。 l設 計 一 個 動 態(tài) 規(guī) 劃 算 法 ， 通 常 可 以 按 以 下 幾 個步 驟 進 行 ：（ 1） 刻 畫 最 優(yōu) 解 的 結(jié) 構(gòu) 特 性 ；（ 2） 遞 歸 定 義 最 優(yōu) 解 值 ；（ 3） 以 自 底 向 上 方 式 計 算 最 優(yōu) 解 值 ；（ 4） 根 據(jù) 計 算 得 到 的 信 息 構(gòu) 造 一 個 最 優(yōu) 解 。其 中 ， 第 （ 1） 至 （ 3） 步 是 動 態(tài) 規(guī) 劃 算 法 的 基 本步 驟 。 最 優(yōu) 解 值 是 最 優(yōu) 解 的 目 標 函 數(shù) 的 值 。 l 一 個 最 優(yōu) 化 多 步 決 策 問 題 適 合 用 動 態(tài) 規(guī) 劃 法 求解 有 兩 個 要 素 ： l多 段 圖 G=(V,E)是 一 個 帶 權(quán) 有 向 圖 ， 它 具 有 如 下 特性 ： 圖 中 的 結(jié) 點 被 劃 分 成 k2個 互 不 相 交 的 子 集 Vi，1ik。 其 中 V1和 Vk分 別 只 有 一 個 結(jié) 點 ， V1包 含 源 點（ source） s， Vk包 含 匯 點 （ sink） t。 對 所 有 邊E， 多 段 圖 要 求 若 uVi， 則 vVi 1， 1ik，每 條 邊 的 權(quán) 值 為 c(u,v)。 從 s到 t的 路 徑 長 度 是 這 條 路徑 上 邊 的 權(quán) 值 之 和 ， （ multistage graph problem） 是 求 從 s到 t的 一 條 長 度 最 短 的 路 徑 。 ltemplatelvoid Graph:FMultiGraph(int k,int *p)l/采 用 程 序 6 8的 鄰 接 表 存 儲 圖 G。l float *cost=new floatn;l int q,*d=new intn;l costn-1=0,dn-1=-1; for (int j=n-2;j=0;j-) float min=INFTY; for (ENode *r=aj;r;r=r-nextArc) int v=r-adjVex; if (r-w+costvw+costv;q=v; costj=min;dj=q; p0=0;pk-1=n-1; for(j=1;j=k-2;j+) pj=dpj-1; delete cost;delete d; l 將 n個 資 源 分 配 給 r個 項 目 ， 已 知 如 果 把 j個 資源 分 配 給 第 i個 項 目 ， 可 以 收 益 N(i,j)， 0jn，1ir。 求 總 收 益 最 大 的 資 源 分 配 方 案 。 l設 G=(V,E)是 一 個 有 n個 結(jié) 點 的 帶 權(quán) 有 向 圖 ， w(i,j)是 權(quán) 函 數(shù) ， l l每 對 結(jié) 點 間 的 最 短 路 徑 問 題 是 指 求 圖 中 任 意 一 對 結(jié)點 i和 j之 間 的 最 短 路 徑 。 Ej,i ji 0 Eji, j,i)j,i(w 如 果如 果如 果上 的 權(quán) 值邊 1nk1 ,jkdkid ,jidminjid Ej,i Ej,i )j,i(wjid 1k1k1kk1 若 若 ltemplatelvoid MGraph:Floyd(T*l d= new T*n;path=new int *n;l for(i=0;in;i+)l di=new T n;pathi=new intn;l for (j=0;jn;j+) l dij=aij;l if (i!=j l else pathij=-1;l l for (k=0;kn;k+) for (i=0;in;i+) for (j=0;jn;j+) if (dik+dkj dij ) dij=dik+dkj; pathij=pathkj; l弗 洛 伊 德 算 法 得 到 的 dij， 0i,jn-1是 從 i到 j的最 短 路 徑 。 l完 全 加 括 號 的 矩 陣 連 乘 積 可 遞 歸 地 定 義 為 ：l單 個 矩 陣 是 完 全 加 括 號 的 ；l矩 陣 連 乘 積 A是 完 全 加 括 號 的 ， 則 A可 表 示 為 兩個 完 全 加 括 號 的 矩 陣 連 乘 積 B和 C的 乘 積 并 加 括 號 ，即 A=(BC)。 l l 4個 矩 陣 連 乘 積 ABCD， 設 它 們 的 維 數(shù) 分 別 為A:5010， B:1040, C:4030, D:305。 l矩 陣 連 乘 AiAi+1Aj簡 記 為 Ai:j， ij。 于 是 矩 陣 連乘 A0A1An-1可 記 作 A0:n-1。 將 這 一 計 算 次 序 在 矩陣 Ak和 Ak+1， 0kn-1之 間 斷 開 ， 則 其 相 應 的 完 全 加括 號 形 式 為 （ （ A0A1Ak） （ Ak+1Ak+2An1） ） 。可 先 分 別 計 算 A0:k和 Ak+1:n-1， 然 后 將 兩 個 連 乘積 再 相 乘 得 到 A0:n-1。 l 矩 陣 連 乘 A0:n-1的 最 優(yōu) 計 算 次 序 的 計 算 量 等 于A0:k和 Ak+1:n-1兩 者 的 最 優(yōu) 計 算 次 序 的 計 算 量 之和 ， 再 加 上 A0:k和 Ak+1:n-1相 乘 的 計 算 量 。 如 果兩 個 矩 陣 子 序 列 的 計 算 次 序 不 是 最 優(yōu) 的 ， 則 原 矩 陣的 計 算 次 序 也 不 可 能 是 最 優(yōu) 的 。 這 就 是 說 ， 矩 陣 連乘 問 題 的 最 優(yōu) 解 具 有 最 優(yōu) 子 結(jié) 構(gòu) 特 性 。 ji pppj1kmkimmin ji 0jim 1j1kijki先 定 義 一 個 二 維 數(shù) 組 m， 用 來 保 存 矩 陣 連 乘 時 所 需 的最 少 計 算 量 。 private: void Traceback(int i,int j); int LookupChain(int i, int j); int *p,*m,*s,n; int MatrixChain:MChain() /求 A0:n-1的 最 優(yōu) 解 值 for (int i=0;in;i+) mii=0; for (int r=2; r=n;r+) for (int i=0;i=n-r;i+) int j=i+r-1; mij=mi+1j+pi*pi+1*pj+1; sij=i; for (int k=i+1;kj;k+) int t=mik +mk+1j+pi*pk+1*pj+1; if (tmij) mij=t;sij=k; return m0n-1; void MatrixChain:Traceback(int i,int j) if(i=j) coutAi;return; if (isij) cout(; Traceback(i,sij);if (isij)cout); if(sij+1j)cout(; Traceback(sij+1,j);if(sij+1j) cout);void MatrixChain:Traceback() cout(; Traceback(0,n-1);cout); cout0) return mij; if(i=j) return 0; int u=LookupChain(i+1,j)+pi*pi+1*pj+1; sij=i; for (int k=i+1;kj; k+) int t=LookupChain(i,k)+LookupChain(k+1,j) +pi*pk+1*pj+1; if (tu) u=t; sij=k; mij=u; return u; int MatrixChain:LookupChain() return LookupChain(0,n-1); n1i n0i 1)i(q)i(p n)w(0, n)c(k,1)kc(0, min n)c(k,1)kc(0,n) w(0, min n)c(0, nk1 nk1 l一 般 地 ， c(i,j) ,ij 是 元 素 值 集 合 ai+1,aj所 構(gòu) 造的 最 優(yōu) 二 叉 搜 索 樹 的 代 價 ， 設 r(i,j)=k為 該 樹 的 根 ，要 求 結(jié) 點 k滿 足 )jw(i, j)c(k,1)kc(i, min j)c(k,1)kc(i,j)w(i, minj)c(i, jk1i jk1i l設 n 4且 （ a1,a2,a3,a4） =(Mon,Thu,Tue,Wed)。 又設 p(1:4)=(3,3,1,1)和 q(0:4) (2,3,1,1,1)。 這 里 p和 q都已 乘 了 16。 void CreateOBST(float* p,float* q, float *c,int *r,float*w,int n) for (int i=0;i=n-1;i+) wii=qi;cii=0.0;rii=0; wii+1=qi+qi+1+pi+1; cii+1=qi+qi+1+pi+1; rii+1=i+1; wnn=qn;cnn=0.0;rnn=0; for (int m=2;m=n;m+) for (i=0;i0， pi0， 0in。所 謂 0/1背 包 問 題 是 指 在 物 品 不 能 分 割 ， 只 能 整 件裝 入 背 包 或 不 裝 入 的 情 況 下 ， 求 一 種 最 佳 裝 載 方案 使 得 總 收 益 最 大 。 nj0 p)wX,1 f(j ),X,1j(fmax)X,j(f 0X 0 0 X )X,1(f jj 設 有 0/1背 包 問 題 n=3， （ w0,w1,w2） =（ 2,3,4） ，（ p0,p1,p2） =（ 1,2,4） 和 M=6。 nj0 p)wX,1 f(j ),X,1j(fmax)X,j(f 0X 0 0 X )X,1(f jj l現(xiàn) 用 Sj表 示 函 數(shù) 曲 線 f(j,X)的 全 部 階 躍 點 的 集 合 ，Sj=(Xi,Pi)| 函 數(shù) 曲 線 f(j,X)的 全 部 階 躍 點 ， -1jn-1，其 中 S-1=(0,0)。 用 S1j表 示 函 數(shù) 曲 線 f(j-1,X-wj)+pj的全 部 階 躍 點 的 集 合 ， S1j=(Xj,Pj)| 函 數(shù) 曲 線 f(j-1,X-wj)+pj的 全 部 階 躍 點 ， 0jM的 階 躍 點 得 到 。 l對 于 有S 1=(0,0)， S10=(2,1) S0=(0,0),(2,1)， S11=(3,2),(5,3)S1=(0,0),(2,1),(3,2),(5,3)，S12=(4,4),(6,5)， (7,6),(9,7)S2=(0,0),(2,1),(3,2),(4,4),(6,5) void DKP(float *p,float *w,int n, float M, float for (i=0;iP1) xn 1=1; else xn 1=0;回 溯 確 定 xn 2,xn-3,x0; )2(O2|S| nn1i i1n 0i i 在 最 壞 情 況 下 ， 算 法 的 空 間 復 雜 度 是 O(2n)。在 最 壞 情 況 下 ， 算 法 的 時 間 復 雜 度 是 O(2n)。 l 設 有 三 臺 設 備 兩 個 作 業(yè) ， 每 個 作 業(yè) 包 含 三 項 任務 。 完 成 這 些 任 務 的 時 間 由 矩 陣 M給 定 。 l作 業(yè) i的 fi(S)是 指 在 調(diào) 度 方 案 S下 ， 該 作 業(yè)的 所 有 任 務 都 已 完 成 的 時 間 。 是 所 有 作 業(yè) 都 完 成 的 時 間 。 (mean flow time)MFT(S)定 義 為 ： )S(fmax)S(F ini0 1n 0i i )S(fn1)S(MFT l一 組 給 定 的 作 業(yè) 的 是 F(S)的 最 小 值 。表 示 指 非 搶 先 調(diào) 度 最 優(yōu) 完 成 時 間表 示 搶 先 調(diào) 度 最 優(yōu) 完 成 時 間 。 表 示 非 搶 先 調(diào) 度 最 優(yōu) 平 均 完 成 時 間 ， 表 示 搶 先 調(diào) 度 最 優(yōu) 平 均 完 成 時 間 。 l本 節(jié) 只 討 論 當 m=2時 獲 得 OFT的 調(diào) 度 方 案 的 算 法 ，這 就 是 。 描 述 為 ： 設 有 n個 作 業(yè) 的 集 合0， 1， ， n-1， 每 個 作 業(yè) 都 有 兩 項 任 務 要 求 在 2臺 設 備 P1和 P2組 成 的 流 水 線 上 完 成 加 工 。 每 個 作 業(yè)加 工 的 順 序 總 是 先 在 P1上 加 工 ， 然 后 在 P2上 加 工 。P1和 P2加 工 作 業(yè) i所 需 的 時 間 分 別 為 a i和 bi。 流 水作 業(yè) 調(diào) 度 問 題 要 求 確 定 這 n個 作 業(yè) 的 最 優(yōu) 加 工 順 序 ，使 得 從 第 一 個 作 業(yè) 在 設 備 P1上 開 始 加 工 ， 到 最 后 一個 作 業(yè) 在 設 備 P2上 加 工 完 成 所 需 的 時 間 最 少 。 即 求使 F(S)有 最 小 值 的 調(diào) 度 方 案 S。 流 水 作 業(yè) 調(diào) 度 問 題 具 有 最 優(yōu) 子 結(jié) 構(gòu) 的 性質(zhì) 。 l 如 果 在 調(diào) 度 方 案 的 作 業(yè) 排 列 中 ， 作 業(yè) i和 j滿 足minbi,ajminbj,ai， 則 稱 作 業(yè) i和 j滿 足l可 以 設 計 下 列 作 業(yè) 排 列 方 法 。 這 樣 做 能 得 到 最 優(yōu)調(diào) 度 方 案l(1)如 果 mina0,a1,an1, b0,b1,bn1是 ai， 則 ai應是 最 優(yōu) 排 列 的 第 一 個 作 業(yè) ；l(2)如 果 mina0,a1,an-1,b0,b1,bn1是 bj， 則 bj應是 最 優(yōu) 排 列 的 最 后 一 個 作 業(yè) ；l(3) 繼 續(xù) （ 1） 和 （ 2） 的 做 法 ， 直 到 完 成 所 有 作 業(yè)的 排 列 。 設 n 4， （ a0,a1,a2,a3） =(3,4,8,10)l （ b0,b1,b2,b3） =(6,2,9,15)。l設 =(0),(1),(2),(3)是 最 優(yōu) 作 業(yè) 排 列 。 l先 將 任 務 按 處 理 時 間 的 非 減 次 序 排 列 成 ：l （ b1,a0,a1,b0,a2,b2,a3,b3） =(2,3,4,6,8,9,10,15)l先 選 b1， 將 其 加 在 最 優(yōu) 作 業(yè) 排 列 的 最 后 ， 故 (3)=1l再 選 a0， 應 加 在 最 優(yōu) 作 業(yè) 排 列 的 最 前 面 ， 故 (0)=0l考 察 a1和 b0， 因 作 業(yè) 1和 0已 調(diào) 度 ，l接 著 考 察 a2， 應 有 (1)=2， 再 考 察 b2和 a3， 令 (2)=3。l所 以 最 優(yōu) 解 為 ： (0),(1),(2),(3) （ 0,2,3,1） 。 struct Triplet int operator (Triplet b)const return tb.t;int jobNo,t,ab; ; void FlowShop(int n, int *a,int *b,int *c) Triplet dmSize=0,0,0; for(int i=0;in;i+) if(aibi) di.jobNo=i;di.ab=0;di.t=ai; else di.jobNo=i;di.ab=1;di.t=bi; Sort(d,n); int left=0,right=n-1;for (i=0;in;i+) if(di.ab=0) cleft+=di.jobNo; else cright-=di.jobNo; Johnson算 法 的 時 間 取 決 于 對 作 業(yè) 集 合 的 排 序 ， 因此 ， 在 最 壞 情 況 下 算 法 的 時 間 復 雜 度 為 O(nlogn)，所 需 的 空 間 復 雜 度 為 O(n)。