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

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