動態(tài)規(guī)劃策略教材(已修改)
2025-03-12 21:43 本頁面
【正文】 動 態(tài) 規(guī) 劃 河海大學(xué)計算機(jī)信息學(xué)院 丁海軍 [例 1]：求出從 頂點 1點到 頂點 7點的最短路徑 方法？ 一、導(dǎo)言 ?最優(yōu)性原理 ?根據(jù)窮舉法， (1,3,5,7)為優(yōu)化解。 ?優(yōu)化原理指：相對于初始決策 1－ 3造成的問題狀態(tài)，（ 3， 5， 7）必須是 3到 7的最短路。否則（ 1， 3， 5， 7）也不可能是優(yōu)化的。 ?無論第一步?jīng)Q策取 {2,3,4}中那一節(jié)點，其后的決策序列必須是該節(jié)點到目的節(jié)點的最短路 ?節(jié)點 1到目的節(jié)點的最短路長度可從 2,3,4到目的節(jié)點的最短路長度＋節(jié)點 1到這些節(jié)點的邊成本經(jīng)枚舉得到 ?應(yīng)用優(yōu)化原理設(shè)計算法的過程如下： ?選擇子問題的表示：設(shè) f(i)為 i到目的節(jié)點的最短路長度 ?建立 f(i)的遞歸方程 ?設(shè) A[i]為與 i相鄰的結(jié)點集合，則有 )}(),({co s)()}(),1({co s)1(minmin][]1[jfjitifjfjtfiAjAj??????初始 f(7)=0 依次計算 f(6),… ,f(1)： f(6)=1,f(5)=2, f(4)=8+f(6) f(3)=min{1+f(5),5+f(6)} f(2)=min{7+f(5),6+f(6)} f(1)=min{1+f(2),4+f(3),6+f(4)} 遞歸還可從前向后： f(i)=節(jié)點 1到節(jié)點 i的最短路的長度；遞歸從 f(1)=0開始。 ?例 1: (數(shù)字三角問題 )如圖所示的數(shù)字三角形，從頂部出發(fā)，在每一個節(jié)點可以選擇向左走或者向右走，一直走到底部，要求找到一條路徑，使路徑上的數(shù)字和最大。 貪心法？ 窮舉法？ F1() F3() F4() F5() F2() 用函數(shù) fi(x)表示第 i層節(jié)點到底部（假設(shè)是第 N層）的路徑上數(shù)字和的最大值。 顯而易見： f1(9)=9+max{f2(12)+f2(15)} 問題變成： f1(9)=? f2(12)=12+max{f3(10)+f3(6)} f2(15)=15+max{f3(6)+f3(8)} fi(x)=x+max{fi+1(x1)+fi+1(x2)+…… } 遞歸公式的終止條件： fN(19)=19 fN(7)=7 …… 思考： ① 請同學(xué)們手工計算一下結(jié)果？ ② 如何編程？ 如何編程與數(shù)據(jù)結(jié)構(gòu)有關(guān)：將原始數(shù)塔寫成下面的形式，用 data[i][j]表示這個矩陣 用矩陣 d[i][j]表示上面的 fi(x) 用矩陣表示的遞歸公式是什么樣子？ D[i][j]= data[i][j] +max{d[i+1][j],d[i+1][j+1]} D[n][j]=data[i][j] i=n1,n2,… ,2,1 最終的 結(jié)果 d[1][1]=？ 下一個問題：求的 d[i][j]后如何讓具體最大值路徑？ b=d[i][j]data[i][j] if(b==d[i+1][j]), then (i,j)?(i+1,j) if(b==d[i+1][j+1]), then (i,j)?(i+1,j+1) ?總結(jié)：動態(tài)規(guī)劃問題的設(shè)計要素？ ?劃分子問題 ?用參數(shù)表達(dá)子問題的邊界，將問題求解轉(zhuǎn)化為多步判斷問題 ?確定優(yōu)化目標(biāo)函數(shù) ?根據(jù)問題性質(zhì)，以函數(shù)的極大或者極小為依據(jù)，確定是否滿足最優(yōu)原理 ?列出關(guān)于優(yōu)化函數(shù)的遞推方程和邊界、約束條件 ?注意：遞推方程中總會存在極大或極小運算 ?求解遞推方程 ?兩種求解遞推方程的方法 –自頂向下：遞歸方法 –自底向上：迭代方法 例 2: (資源分配問題 )設(shè)有 n個單位的資源 (比如 n萬元的資金 ),分配給 m個項目， gi(x)為第 i個項目的到 x單位的資源所產(chǎn)生的利潤。求利潤總和為最大的資源分配方案。 下表是 n=7萬元資金分配給三個項目 A、 B、 C的利潤表 分析：根據(jù)題意，本質(zhì)上是求下面的優(yōu)化問題 J(x1,x2,..,xm)=max{g1(x1)+g2(x2)+… +gm(xm)} x1+x2+… +xm=n 0≤xi≤n， 要求 xi是整數(shù) 這是一個整數(shù)規(guī)劃問題。 解法 1：最笨的求解方法？窮舉發(fā) 解法 2：動態(tài)規(guī)劃方法 關(guān)鍵：找到一個遞歸公式 假設(shè)，將數(shù)量為 x單位的資源分配前 i個項目的最大利潤為 fi(x),可以寫出下面的遞歸公式 ? ? ? ? ? ?? ? ? ?nxmixgxfyxfygxfiixyi??????????0 ,... ,2,1}{1110max初始條件：最終所需要的最大值是： fm(n)=? 如何編程？需要解決數(shù)據(jù)結(jié)構(gòu)問題 ? ? ? ? ? ?? ? ? ?nxmixgxfyxfygxf iixyi??????? ???0 ,... ,2,1}{1110max初始條件：n1,2, ...,j ,... ,2,1]][1[]][1[]}][1[]][[{]][[ max0?????????mijgjfkjifkigjifjk初始條件：將函數(shù)用數(shù)組表示， x用 j表示， y用 k表示，可寫出下面的遞歸公式 f[m][n]就是所需要的最大利潤。 實際編程時，還缺少一個東西？每個項目到底分配到多少資源量？
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1