資源背包動態(tài)規(guī)劃ppt課件-資料下載頁
2025-05-03 18:27本頁面
【正文】 ? 如果前 x1條流水線只要生產(chǎn) i’漢堡， j’個薯條，生產(chǎn)的飲料為 f(x1,i’,j’) ? 因此有第 x條流水線必須生產(chǎn)了 ii’個漢堡， jj’個薯條，剩下的時間生產(chǎn) k個飲料。 ? 因為前 x條流水線生產(chǎn)的飲料 = 前 x1條流水線生產(chǎn)的飲料 + 第 x條流水線生產(chǎn)的飲料 ? 所以有， f(x,i,j)=max{f(x1,i’,j’)+k} 32*)39。(1*)39。(ppjjpiiTxk ?????流水線資源分配圖 32*)39。(1*)39。(ppjjpiiTxk ?????其中，思考？ ? f(x,i,j)=max{f(x1,i’,j’)+k} 1=x=n=10,0=i’=i=100, 0=j’=j=100 ? k可以實(shí)時求出 ? 時間復(fù)雜度為 10*1002*1002=109 ? 顯然超時！ 優(yōu)化 1. 求出最多可能生產(chǎn)多少套，減少不必要循環(huán)。 2. 淘汰一些沒有意義狀態(tài)，比如生產(chǎn)了過多第三種物質(zhì)，卻沒把前兩種生產(chǎn)滿。 3. 讓每條流水線大多數(shù)時間按成套時間生產(chǎn)，留下一些時間進(jìn)行動態(tài)規(guī)劃，這樣將在動態(tài)規(guī)劃時，極大地減少每種物品的產(chǎn)量從而極大地減少動態(tài)規(guī)劃的狀態(tài)數(shù)。 說明 ? 利用前兩個優(yōu)化基本可以出解 ? 第 3個優(yōu)化，對每條流水線進(jìn)行動態(tài)規(guī)劃的剩余時間多少比較難確定，否則正確性難以保證，剩余時間越多，正確率越高，速度越慢。下圖是對第 3個優(yōu)化的說明： 總結(jié) ? 第 1步：采用優(yōu)化方法 3，將每條流水線的 部分時間按成套生產(chǎn)，設(shè)第 i條流水線生產(chǎn)套餐 Wi套，剩下的時間為 Ti； ? 第 2步，對每條流水線的剩下時間進(jìn)行動態(tài)規(guī)劃 ,并采用優(yōu)化 1， 2； ? 第 3步，求總套數(shù) = 貪心總套數(shù) X + 動態(tài)規(guī)劃的套數(shù) Y。 ? 其中 X,Y計算如下， 進(jìn)行枚舉，對于所有 ji}},),(,{{1CjinfBjAiM INM A XYWiXni?? ??總結(jié) ? 對于資源類動態(tài)規(guī)劃問題，我們可以看出，問題描述必須有一個基本要素：資源，有時這種資源可能是金錢、空間或者時間，問題就是要對這些資源如何分配，一種基本的想法是將資源應(yīng)用于前 i個階段，然后考慮第 i個階段和前 i1個階段之間的關(guān)系。 ? 設(shè)前 i個點(diǎn)的消耗 j的資源得到的最優(yōu)值，研究前 i1個點(diǎn)消耗的資源的最優(yōu)值，利用第 i個點(diǎn)決策轉(zhuǎn)移，如下圖。 ? 狀態(tài)轉(zhuǎn)移方程一般可寫成 : fi(j) = min{ fi1 ( k) + ui (j,k)}
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1