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