第六章 動(dòng)態(tài)規(guī)劃1.ppt

第六章動(dòng)態(tài)規(guī)劃 信工計(jì)算機(jī)系2008 6 1資源分配問(wèn)題 假設(shè)資源總數(shù)為m份 工程個(gè)數(shù)為n 給每項(xiàng)工程投入的資源不同 所獲得的利潤(rùn)也不同 要求把總數(shù)為m的資源 分配給n個(gè)工程 以獲得最大利潤(rùn)分配方案 數(shù)學(xué)描述 假設(shè)用函數(shù)Gi k 1 i n 0 k m 表示將k份資源分配給工程i獲得的利潤(rùn) 設(shè)工程i分配xi份資源 資源分配問(wèn)題數(shù)學(xué)描述為 設(shè)其最優(yōu)解為X x1 x2 xn 資源分配問(wèn)題求解 最優(yōu)值 opt max fi x 1 i n 0 x m 記k i fi x opt p x fi x opt k p含義 分配p份資源給前k個(gè)工程時(shí)利潤(rùn)最大 即 xk 1 0 xk 2 0 xn 0 fi x 的計(jì)算 解資源分配問(wèn)題實(shí)例 有8個(gè)份額的資源 分配給3個(gè)工程 其利潤(rùn)函數(shù)如下表 求資源的最優(yōu)分配方案 計(jì)算過(guò)程 解 初始 f1 x G1 x d1 x xopt max f1 x 0 x 8 53k 1p 8 計(jì)算過(guò)程 其它及計(jì)算f3 x 同理 結(jié)果如下表 計(jì)算過(guò)程 opt 140k 3p 8 計(jì)算過(guò)程 計(jì)算最優(yōu)解 最大利潤(rùn)opt 140第3個(gè)工程分配資源x3 d3 p 4份第2個(gè)工程分配資源x2 d2 p x3 4份第1個(gè)工程分配資源x1 d1 p x3 x2 0份最優(yōu)解X 0 4 4 時(shí)間復(fù)雜性 初始化 O m 計(jì)算f2 x f3 x fn x O nm2 計(jì)算opt k p O nm 回溯 O n 時(shí)間復(fù)雜性 O nm2 算法分析 關(guān)于資源分配求解過(guò)程 上述解資源分配所采用的算法 動(dòng)態(tài)規(guī)劃 6 2動(dòng)態(tài)規(guī)劃的基本思想 動(dòng)態(tài)規(guī)劃也稱多階段決策 由狀態(tài)和決策組成 從初始狀態(tài)開(kāi)始 根據(jù)各階段決策使?fàn)顟B(tài)轉(zhuǎn)移 到達(dá)最終狀態(tài) 動(dòng)態(tài)規(guī)劃的一般決策過(guò)程示意圖 Sn是最終狀態(tài)集 S1 Sn中至少有一個(gè)狀態(tài)是最優(yōu)狀態(tài) 最優(yōu)值 假設(shè)為Sk kn 設(shè)狀態(tài)Si si 1 si 2 si r 從Sk kn向前回溯可得到最優(yōu)解或最優(yōu)決策序列 P1 k1 P2 k2 Pk kn 即 動(dòng)態(tài)規(guī)劃最優(yōu)解的確定 S0 Sk kn Pk kn S1 k1 P1 k1 各階段賴以決策的策略或目標(biāo) 稱為動(dòng)態(tài)規(guī)劃函數(shù) 資源分配問(wèn)題動(dòng)態(tài)規(guī)劃函數(shù) fi x 動(dòng)態(tài)規(guī)劃函數(shù)可以遞歸定義 或用遞推公式表達(dá) 動(dòng)態(tài)規(guī)劃函數(shù) 動(dòng)態(tài)規(guī)劃算法的設(shè)計(jì)步驟 找出最優(yōu)解的性質(zhì) 并刻畫(huà)其結(jié)構(gòu)特征 fi x 遞歸的定義最優(yōu)值 fi x max Gi k fi 1 x k 以自底向上的方式計(jì)算最優(yōu)值 表格根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息 構(gòu)造最優(yōu)解 回溯 動(dòng)態(tài)規(guī)劃算法的基本要素 可用動(dòng)態(tài)規(guī)劃求解的問(wèn)題應(yīng)具有以下兩個(gè)基本要素 最優(yōu)子結(jié)構(gòu)問(wèn)題的最優(yōu)解包含了其子問(wèn)題的最優(yōu)解 動(dòng)態(tài)規(guī)劃算法 利用問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì) 自底向上的方式遞歸地從子問(wèn)題的最優(yōu)解構(gòu)造出整個(gè)問(wèn)題的最優(yōu)解 動(dòng)態(tài)規(guī)劃算法的基本要素 重疊子問(wèn)題在用動(dòng)態(tài)規(guī)劃遞歸地自底向上求解問(wèn)題時(shí) 每次產(chǎn)生的子問(wèn)題不是新問(wèn)題 有些被反復(fù)計(jì)算多次 動(dòng)態(tài)規(guī)劃算法利用這些子問(wèn)題的重疊性質(zhì) 對(duì)每個(gè)子問(wèn)題只計(jì)算一次 將結(jié)果保存在表格中 后續(xù)計(jì)算只需查找表格 從而節(jié)省時(shí)間 資源分配問(wèn)題重疊子問(wèn)題示意圖 注 只畫(huà)出fi x x 4的情況 其它同理 6 3多段圖最短路徑問(wèn)題 多段圖的最短路徑問(wèn)題 是求從源點(diǎn)s到收點(diǎn)t的最小花費(fèi)的通路 假設(shè)用鄰接矩陣C cij 存儲(chǔ)圖G 多段圖最短路徑問(wèn)題的動(dòng)態(tài)規(guī)劃函數(shù) 最優(yōu)值 cost 0 按子集順序 對(duì)多段圖各頂點(diǎn)編號(hào) 假設(shè)源點(diǎn)為0 收點(diǎn)為n 1 動(dòng)態(tài)規(guī)劃函數(shù)的遞歸表示 初始化 cost i INT MAX path i 10 i ncost n 1 0 i n 1若i 0 轉(zhuǎn) 4 否則轉(zhuǎn) 3 i 根據(jù)式 6 1 和 6 2 計(jì)算cost i path i 轉(zhuǎn) 2 i 0 route i 0 若route i n 1 終止 否則 轉(zhuǎn) 6 i route i path route i 1 轉(zhuǎn) 5 動(dòng)態(tài)規(guī)劃解多段圖最短路徑算法描述 其中 數(shù)組route存放從0到n 1的最短路徑 動(dòng)態(tài)規(guī)劃解多段圖最短路徑問(wèn)題實(shí)例 計(jì)算過(guò)程 解 cost 6 0cost 5 4 cost 6 4path 5 6cost 4 5 cost 6 5path 4 6cost 3 min 8 cost 4 9 cost 6 9 cost 5 9path 3 6cost 2 min 5 cost 3 7 cost 5 11path 2 5cost 1 min 6 cost 3 6 cost 4 11 計(jì)算過(guò)程 path 1 4cost 0 min 4 cost 1 5 cost 2 8 cost 3 15最優(yōu)值path 0 1回溯求最優(yōu)解 route 0 0route 1 1route 2 4route 3 6最優(yōu)解 0 1 4 6 時(shí)間復(fù)雜性 鄰接矩陣 初始化 O n 計(jì)算cost 循環(huán)n 1次 每次訪問(wèn)鄰接表一行 O n2 計(jì)算route O k 故為O n2 考慮鄰接表存儲(chǔ)的時(shí)間復(fù)雜性 動(dòng)態(tài)規(guī)劃解多段圖最短路徑算法分析 6 4貨郎擔(dān)問(wèn)題 假設(shè)用鄰接矩陣C cij 存儲(chǔ)網(wǎng) 分別求從城市i出發(fā)的哈密爾頓回路 最后求n條回路的最小值 貨郎擔(dān)問(wèn)題的動(dòng)態(tài)規(guī)劃函數(shù) 最優(yōu)值 d i V i 貨郎擔(dān)問(wèn)題動(dòng)態(tài)規(guī)劃函數(shù)的遞歸表示 4個(gè)城市1 2 3 4 鄰接矩陣如下表 動(dòng)態(tài)規(guī)劃解貨郎擔(dān)問(wèn)題實(shí)例 解 以從城市1出發(fā)為例 求哈密爾頓回路 其它城市同理 第一階段d 1 2 3 4 min c12 d 2 3 4 c13 d 3 2 4 c14 d 4 2 3 第二階段d 2 3 4 min c23 d 3 4 c24 d 4 3 d 3 2 4 min c32 d 2 4 c34 d 4 2 計(jì)算過(guò)程 d 4 2 3 min c42 d 2 3 c43 d 3 2 第3階段d 3 4 c34 d 4 2 3 5 3 4 1 d 4 3 c43 d 3 5 6 11 4 3 1 d 2 4 c24 d 4 3 3 6 2 4 1 d 4 2 c42 d 2 7 5 12 4 2 1 d 2 3 c23 d 3 2 6 8 2 3 1 d 3 2 c32 d 2 4 5 9 3 2 1 計(jì)算過(guò)程 回溯第2階段d 2 3 4 min 2 5 3 11 7 2 3 4 1 d 3 2 4 min 4 6 2 12 10 3 2 4 1 d 4 2 3 min 7 8 5 9 14 4 3 2 1 回溯第1階段d 1 2 3 4 min 3 7 6 10 7 14 10 1 2 3 4 1 計(jì)算過(guò)程 動(dòng)態(tài)規(guī)劃解貨郎擔(dān)問(wèn)題求解過(guò)程示意圖 動(dòng)態(tài)規(guī)劃解貨郎擔(dān)問(wèn)題算法分析 時(shí)間復(fù)雜性 O n22n 窮舉法 O n 貪心法 O n3 6 50 1背包問(wèn)題 0 1背包問(wèn)題數(shù)學(xué)模型 即求X x1 x2 xn 滿足上述優(yōu)化方程 貪心法解0 1背包問(wèn)題 例 有5個(gè)物體 其重量分別為6 2 6 5 4 價(jià)值分別為6 3 5 4 6 背包的載重量為10 求裝入背包的物體及其總價(jià)值 解 價(jià)值 重量降序排 2 5 1 3 4x2 1剩余重量8x5 1剩余重量4x1 0 x3 0 x4 0總價(jià)值 9 最優(yōu)解 1 0 0 0 1 最優(yōu)價(jià)值 12 0 1背包問(wèn)題的動(dòng)態(tài)規(guī)劃函數(shù) 最優(yōu)值 opt fn M 動(dòng)態(tài)規(guī)劃函數(shù)的遞歸表示 回溯求最優(yōu)解 1 若fn M fn 1 M 則xn 0 否則xn 1 2 令M M pnxn n 3 若n 0 終止 否則 轉(zhuǎn) 1 動(dòng)態(tài)規(guī)劃解0 1背包問(wèn)題實(shí)例 有5個(gè)物體 其重量分別為6 2 6 5 4 價(jià)值分別為6 3 5 4 6 背包的載重量為10 求裝入背包的物體及其總價(jià)值 計(jì)算過(guò)程 解 初始 計(jì)算過(guò)程 第一階段 f2 0 0f2 1 f1 1 0f2 2 max 3 f1 0 f1 2 3f2 3 max 3 f1 1 f1 3 3f2 4 max 3 f1 2 f1 4 3其它同理 結(jié)果見(jiàn)下表 計(jì)算過(guò)程 計(jì)算過(guò)程 回溯求最優(yōu)解 f5 10 f4 10 x5 1