動(dòng)態(tài)規(guī)劃策略教材-展示頁(yè)
2025-03-10 21:43本頁(yè)面
【正文】 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ù)，確定是否滿(mǎn)足最優(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)。 ?例 1: (數(shù)字三角問(wèn)題 )如圖所示的數(shù)字三角形，從頂部出發(fā)，在每一個(gè)節(jié)點(diǎn)可以選擇向左走或者向右走，一直走到底部，要求找到一條路徑，使路徑上的數(shù)字和最大。否則（ 1， 3， 5， 7）也不可能是優(yōu)化的。動(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的最短路。 ?無(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)始。 貪心法？ 窮舉法？ F1() F3() F4() F5() F2() 用函數(shù) fi(x)表示第 i層節(jié)點(diǎn)到底部（假設(shè)是第 N層）的路徑上數(shù)字和的最大值。求利潤(rù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)。 求的 a[i][j]之后，就可以求的每個(gè)項(xiàng)目分的資源量： j=n。i=1。 j=jx[i]?？疾爝@ n個(gè)矩陣的連乘積 A1A2A3… An ?由于矩陣乘法滿(mǎn)足結(jié)合律，所以計(jì)算矩陣的連乘可以有許多不同的計(jì)算次序。 ?若一個(gè)矩陣連乘積的計(jì)算次序完全確定，也就是說(shuō)該連乘積已完全加括號(hào)，則可以依此次序反復(fù)調(diào)用2個(gè)矩陣相乘的標(biāo)準(zhǔn)算法計(jì)算出矩陣連乘積 ?給定 n個(gè)矩陣｛ A1,A2,… ,An｝，其中 Ai與Ai+1是可乘的 (i=1,2 ,… ,n1)。 )/4()(11)()(1)( 2/311nnPnnknPkPnPnnk???????????? ????算法復(fù)雜度分析 ： ?對(duì)于 n個(gè)矩陣的連乘積，設(shè)其不同的計(jì)算次序?yàn)?P(n)。設(shè)這個(gè)計(jì)算次序在矩陣 Ak和 Ak+1之間將矩陣鏈斷開(kāi)， i≤kj，則其相應(yīng)完全加括號(hào)方式為 )...)(...( 211 jkkkii AAAAAA ???計(jì)算量： A[
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號(hào)-1