版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃什么是動(dòng)態(tài)規(guī)劃?(一)動(dòng)態(tài)規(guī)劃是解決多階段決策問題的一種方法。什么是動(dòng)態(tài)規(guī)劃?(一)動(dòng)態(tài)規(guī)劃是解決多階段決策問題的一種方法多階段決策問題
對(duì)于整個(gè)問題,可以根據(jù)其時(shí)間或其他順序分成若干個(gè)前后相關(guān)聯(lián)的子問題,問題的全局最優(yōu)包含其子問題的局部最優(yōu),即滿足最優(yōu)子結(jié)構(gòu)性質(zhì),并且無后效性,有邊界條件,且一般劃分為很明顯的階段,存在一條或多條狀態(tài)轉(zhuǎn)移方程。多階段決策問題對(duì)于整個(gè)問題,可以根據(jù)其時(shí)間或其他“最優(yōu)性原理”可陳述為:不論初始狀態(tài)和第一步?jīng)Q策是什么,余下的決策相對(duì)于前一次決策所產(chǎn)生的新狀態(tài),構(gòu)成一個(gè)最優(yōu)決策序列。最優(yōu)決策序列的子序列,一定是局部最優(yōu)決策子序列。包含有非局部最優(yōu)的決策子序列,一定不是最優(yōu)決策序列。最優(yōu)性原理“最優(yōu)性原理”可陳述為:不論初始狀態(tài)和第一步?jīng)Q策是什么,余下
如圖,已知一個(gè)有向圖,求一條從最左邊的點(diǎn)走到最右邊點(diǎn)的方案(只能從左往右走),使得所經(jīng)過的權(quán)值和除以4的余數(shù)最小。MOD4余數(shù)最小問題如圖,已知一個(gè)有向圖,求一條從最左邊的點(diǎn)走到最右邊點(diǎn)的
設(shè)所有點(diǎn)從左至右編號(hào)為1…4,MIN(i)表示前I個(gè)點(diǎn)的最優(yōu)值,很容易得出一個(gè)方程:
Min(i)=min{(Min(I-1)+num[I-1,1])mod4,Min(I-1)+num[I-1,2])mod4}
通過這個(gè)方程可以求出一條路徑為(2+3+1)MOD4=2但最優(yōu)值實(shí)際上是(2+1+1)MOD4=0。為什么會(huì)出錯(cuò)呢?分析設(shè)所有點(diǎn)從左至右編號(hào)為1…4,MIN(i)表
觀察以上數(shù)據(jù)發(fā)現(xiàn)取Min(3)的時(shí)候,動(dòng)態(tài)規(guī)劃求出來的最優(yōu)值為1,而正確的值應(yīng)該為0,由此可知本題對(duì)應(yīng)于一條最優(yōu)路徑,并不是這條路徑上的所有點(diǎn)的最優(yōu)值都是從點(diǎn)1到該點(diǎn)可得的最優(yōu)值,對(duì)于每一個(gè)階段都取最優(yōu)值并不能保證求出最優(yōu)解,即不滿足最優(yōu)化原理,因此這種規(guī)劃方法在本題行不通。動(dòng)態(tài)規(guī)劃2概述ppt課件
讓我們來換一個(gè)思路思考本題,因?yàn)楸绢}是要求總和除以4余數(shù)最小的一條路徑,我們先撇開最小余數(shù)不去管它,而是將本題改為從點(diǎn)1到點(diǎn)4的所有路徑中,求出每條路上權(quán)值和除以4的不同余數(shù)的個(gè)數(shù)。我們?cè)O(shè)一個(gè)數(shù)組can[I,j]表示從點(diǎn)1至點(diǎn)I可不可以求出一條路徑是該路徑的權(quán)值總和除以4的余數(shù)為J,那么又可以得出一個(gè)方程:
can[I,j]:=can[I-1,k]and((k+num[I,p])mod4=j)(0<=k<=3,1<=p<=2)can[1,0]=truecan[1,1]=falsecan[1,2]=falsecan[1,3]=false
通過這個(gè)方程我們可以求出從點(diǎn)1至點(diǎn)I可以達(dá)到的所有余數(shù),我們只要從這些余數(shù)中選出一個(gè)值最小的輸出就行。讓我們來換一個(gè)思路思考本題,因?yàn)楸绢}是要求總和除以4動(dòng)態(tài)規(guī)劃的指導(dǎo)思想是:
在做每一步?jīng)Q策時(shí),列出各種可能的局部解,之后依據(jù)某種判定條件,舍棄那些肯定不能得到最優(yōu)解的局部解。這樣,在每一步都經(jīng)過篩選,以每一步都是最優(yōu)的來保證全局是最優(yōu)的。篩選相當(dāng)于最大限度地有效剪枝(從搜索角度看),效率會(huì)十分高。但它又不同于貪心法。貪心法只能做到局部最優(yōu),不能保證全局最優(yōu),因?yàn)橛行﹩栴}不符合最優(yōu)性原理。動(dòng)態(tài)規(guī)劃的指導(dǎo)思想是:兩種算法的差別在于,貪心法產(chǎn)生一個(gè)按貪心策略形成的判定序列,該序列不保證解是全局最優(yōu)的。而動(dòng)態(tài)規(guī)劃會(huì)產(chǎn)生許多判定序列,再按最優(yōu)性原理對(duì)這些序列加以篩選,去除那些非局部最優(yōu)的子序列。兩種算法的差別在于,貪心法產(chǎn)生一個(gè)按貪心策略形成的判定序列,什么是動(dòng)態(tài)規(guī)劃?(二)動(dòng)態(tài)規(guī)劃實(shí)際上就是一種排除重復(fù)計(jì)算的算法,更具體的說,動(dòng)態(tài)規(guī)劃就是用空間換取時(shí)間。什么是動(dòng)態(tài)規(guī)劃?(二)動(dòng)態(tài)規(guī)劃實(shí)際上就是一種排除重復(fù)計(jì)算的算問題:給定一個(gè)具有N層的數(shù)字三角形如下圖,從頂至底有多條路徑,每一步可沿左斜線向下或沿右斜線向下,路徑所經(jīng)過的數(shù)字之和為路徑得分,請(qǐng)求出最大路徑得分。738810
274445265問題:給定一個(gè)具有N層的數(shù)字三角形如下圖,從頂至底有多條路徑
初看此題不難想到本題可以用遞歸算法來解決:FunctionMax(I,J:integer):longint;{從當(dāng)前位置開始的可得的最優(yōu)值}Vars1,s2:Longint;{記錄從左右斜線向下走的可達(dá)的最優(yōu)值}BeginIf(I>n)Or(J>I)ThenMax:=-1{當(dāng)前位置不存在,最優(yōu)值為-1}ElseBeginS1:=Max(I+1,j)+triangle[I,j];{沿左斜線向下走}S2:=Max(I+1,j+1)+triangle[I,j];{沿右斜線向下走}Ifs1>s2thenMax:=s1Elsemax:=s2;{選取最優(yōu)走法}End;End;
由以上算法不難算出其時(shí)間復(fù)雜度為2^n,而本題N最大為100,顯然當(dāng)N比較大時(shí)是無法在規(guī)定時(shí)間內(nèi)出解的,但本題又很難找出理想的剪枝方法。初看此題不難想到本題可以用遞歸算法來解決:
通過以下搜索樹可以看出在求Max(2,1),Max(2,2)的時(shí)候兩次調(diào)用函數(shù)Max(3,2),也就是說,函數(shù)Max(3,2)被重復(fù)計(jì)算了兩次,其實(shí)在這棵搜索樹中有很多結(jié)點(diǎn)都被重復(fù)計(jì)算了多次,程序時(shí)效顯然就會(huì)大打折扣了,實(shí)際上這也是搜索之所以會(huì)效率低下的一大原因。既然知道了上述搜索算法效率低的原因。對(duì)于同一個(gè)函數(shù)值搜索多次是沒有必要的,因此我們可以每求出一個(gè)函數(shù)的值便可將其用數(shù)組保存下來,到了下次要用的時(shí)候直接從數(shù)組里調(diào)出來用就可以了。這樣時(shí)間復(fù)雜度一下子降成了O(N*N){函數(shù)個(gè)數(shù)最多不超過N*N個(gè)。}通過以下搜索樹可以看出在求Max(2,1),Max(FunctionMax(I,J:integer):longint;{從當(dāng)前位置開始的可得的最優(yōu)值}Vars1,s2:Longint;{記錄從左右斜線向下走的可達(dá)的最優(yōu)值}BeginIfA[I,j]<>-1ThenBegin{函數(shù)I,J已求出,直接賦值即可}Max:=A[I,j];Exit;End;If(I>n)Or(J>I)ThenMax:=0{當(dāng)前位置不存在,最優(yōu)值為0}ElseBeginS1:=Max(I+1,j)+triangle[I,j];{沿左斜線向下走}S2:=Max(I+1,j+1)+triangle[I,j];{沿右斜線向下走}Ifs1>s2thenA[I,j]:=s1ElseA[I,j]:=s2;{選取最優(yōu)走法}Max:=A[I,j];{記錄該函數(shù)值}End;End;FunctionMax(I,J:integer):動(dòng)態(tài)規(guī)劃問題具有以下基本特征:1、問題具有多階段決策的特征。2、每一階段都有相應(yīng)的“狀態(tài)”與之對(duì)應(yīng),描述狀態(tài)的量稱為“狀態(tài)變量”。3、每一階段都面臨一個(gè)決策,選擇不同的決策將會(huì)導(dǎo)致下一階段不同的狀態(tài)。4、每一階段的最優(yōu)解問題可以遞歸地歸結(jié)為下一階段各個(gè)可能狀態(tài)的最優(yōu)解問題,各子問題與原問題具有完全相同的結(jié)構(gòu)。動(dòng)態(tài)規(guī)劃的基本模型動(dòng)態(tài)規(guī)劃問題具有以下基本特征:動(dòng)態(tài)規(guī)劃的基本模型階段:據(jù)空間順序或時(shí)間順序?qū)栴}的求解劃分階段。狀態(tài):描述事物的性質(zhì),不同事物有不同的性質(zhì),因而用不同的狀態(tài)來刻畫。對(duì)問題的求解狀態(tài)的描述是分階段的。決策:根據(jù)題意要求,對(duì)每個(gè)階段所做出的某種選擇性操作。狀態(tài)轉(zhuǎn)移方程:用數(shù)學(xué)公式描述與階段相關(guān)的狀態(tài)間的演變規(guī)律。動(dòng)態(tài)規(guī)劃的幾個(gè)概念階段:據(jù)空間順序或時(shí)間順序?qū)栴}的求解劃分階段。動(dòng)態(tài)規(guī)劃的幾動(dòng)態(tài)規(guī)劃問題的一般解題步驟1、判斷問題是否具有最優(yōu)子結(jié)構(gòu)性質(zhì),若不具備則不能用動(dòng)態(tài)規(guī)劃。2、把問題分成若干個(gè)子問題(分階段)。3、建立狀態(tài)轉(zhuǎn)移方程(遞推公式)。4、找出邊界條件。5、將已知邊界值帶入方程。6、遞推求解。動(dòng)態(tài)規(guī)劃問題的一般解題步驟1、判斷問題是否具有最優(yōu)子結(jié)構(gòu)性質(zhì)線性規(guī)劃模型
例1:機(jī)器分配問題。總公司擁有高效生產(chǎn)設(shè)備M臺(tái),準(zhǔn)備分給下屬的N個(gè)公司。各分公司若獲得這些設(shè)備,可以為國家提供一定的盈利。問:如何分配這M臺(tái)設(shè)備才能使國家得到的盈利最大?求出最大盈利值。其中M<=150,N<=100。分配原則:每個(gè)公司有權(quán)獲得任意數(shù)目的設(shè)備,但總臺(tái)數(shù)不得超過總設(shè)備數(shù)M。數(shù)據(jù)文件格式為:第一行保存兩個(gè)數(shù),第一個(gè)數(shù)是設(shè)備臺(tái)數(shù)M,第二個(gè)數(shù)是分公司數(shù)N。接下來是一個(gè)N*M的矩陣,表明了第I個(gè)公司分配J臺(tái)機(jī)器的盈利。
線性規(guī)劃模型例1:機(jī)器分配問題。分析用機(jī)器數(shù)來做狀態(tài),數(shù)組F[I,J]表示前I個(gè)公司分配J臺(tái)機(jī)器的最大盈利。則狀態(tài)轉(zhuǎn)移方程為:F[I,J]=Max{F[I-1,K]+Value[I,J-K]}(1<=I<=N,1<=J<=M,0<=K<=J)初始值:F(0,0)=0時(shí)間復(fù)雜度O(N*M2)分析用機(jī)器數(shù)來做狀態(tài),數(shù)組F[I,J]表示前I個(gè)公司分配J臺(tái)最長不下降序列
設(shè)有整數(shù)序列b1,b2,b3,…,bm,若存在下標(biāo)i1<i2<i3<…<in,且bi1<bi2<bi3<…<bin,則稱
b1,b2,b3,…,bm中有長度為n的不下降序列bi1,
bi2,bi3,…,bin
。求序列b1,b2,b3,…,bm中所有長度(n)最大不下降子序列輸入:整數(shù)序列。輸出:最大長度n和所有長度為n的序列個(gè)數(shù)。最長不下降序列設(shè)有整數(shù)序列b1,b2,b3,…,bm,若存分析(1)設(shè)f(i)為前i個(gè)數(shù)中的最大不下降序列長度
,則f(i)=max{f(j)+1}(1<=j<i<=m,bj<bi)邊界為F(1)=1(2)設(shè)t(i)為前i個(gè)數(shù)中最長不下降序列的個(gè)數(shù),則t(i)=∑t(j)(1<=j<i<=m,bj<bi,f(i)=f(j)-1)初始為t(i)=1當(dāng)f(i)=n時(shí),將t(i)累加舉例:
1234658109f:123455677t:111111222答案:f=7時(shí),邊界為∑t=4分析(1)設(shè)f(i)為前i個(gè)數(shù)中的最大不下降序列長度,則進(jìn)一步(3)求本質(zhì)不同的最長不下降序列個(gè)數(shù)有多少個(gè)?如:1234658109有,
12346810,12345810,1234689,1234589
都是本質(zhì)不同的。但對(duì)于
1223354f1223344t1112244
答案有8個(gè),其中4個(gè)1235,4個(gè)1234進(jìn)一步(3)求本質(zhì)不同的最長不下降序列個(gè)數(shù)有多少個(gè)?改進(jìn)算法上例顯然對(duì)于相兩個(gè)相同的數(shù),重復(fù)算了多次因此,我們對(duì)算法進(jìn)行改進(jìn):對(duì)原序列按b從小到大(當(dāng)bi=bj時(shí)按F從大到?。┡判颍鲈O(shè)Order(i)記錄新序列中的i個(gè)數(shù)在原序列中的位置??梢?,求t(i)時(shí),當(dāng)f(j)=f(j+1),b(j)=b(j+1)且Order(j+1)<Order(i)時(shí),便不累加t(j)。這樣就避免了重復(fù)。
上述算法的時(shí)間復(fù)雜度為O(n2)改進(jìn)算法上例顯然對(duì)于相兩個(gè)相同的數(shù),重復(fù)算了多次因此,我們對(duì)進(jìn)一步(3)求本質(zhì)不同的最長上升序列個(gè)數(shù)有多少個(gè)?如:1234658109有,
12346810,12345810,1234689,1234589
都是本質(zhì)不同的。但對(duì)于
1223354f1223344t1112244
答案有8個(gè),其中4個(gè)1235,4個(gè)1234進(jìn)一步(3)求本質(zhì)不同的最長上升序列個(gè)數(shù)有多少個(gè)?改進(jìn)算法上例顯然對(duì)于兩個(gè)相同的數(shù),重復(fù)算了多次因此,我們對(duì)算法進(jìn)行改進(jìn):對(duì)原序列按b從小到大(當(dāng)bi=bj時(shí)按F從大到?。┡判?,增設(shè)Order(i)記錄新序列中第i個(gè)數(shù)在原序列中的位置??梢姡髏(i)時(shí),當(dāng)f(j)=f(j+1),b(j)=b(j+1)且Order(j+1)<Order(i)時(shí),便不累加t(j)。這樣就避免了重復(fù)。
上述算法的時(shí)間復(fù)雜度為O(n2)改進(jìn)算法上例顯然對(duì)于兩個(gè)相同的數(shù),重復(fù)算了多次
有一條河從東向西將某地區(qū)分為南北2個(gè)部分。河的兩岸各有N個(gè)城市。北岸的每個(gè)城市都與南岸的某個(gè)城市是友好城市,而且關(guān)系是一一對(duì)應(yīng)的?,F(xiàn)在要求在2個(gè)友好城市之間建立一條航線,但由于天氣的緣故,所有的航線都不能相交,因此,就不能給所有的友好城市建立友好航線。請(qǐng)?jiān)O(shè)計(jì)一個(gè)修建航線的方案,能建最多的航線而且不相交。輸入:第一行為一個(gè)正整數(shù)N(N<=1000)以下N行,記第i行有一個(gè)正整數(shù)j,表示北岸的城市i與南岸的城市j互為友好城市。其中城市編號(hào)是按從東到西排列的。輸出:僅一行,即最多的航線數(shù)。
船(ceoi)有一條河從東向西將某地區(qū)分為南北2個(gè)部分。河的兩
首先我們需要判定對(duì)于給定的兩條航線是否相交,設(shè)北岸城市i1,j1(i1<j1)分別與南岸城市i2,j2互為友好城市,那么這兩條航線不相交
(以下簡稱為i1,j1相容
)的充要條件是I2<=J2。(結(jié)論1)由下圖就可以很容易地得到這個(gè)結(jié)論。
i1j2i2j1j2i2j1i1北岸:
南岸:
圖
一
圖
二
分析首先我們需要判定對(duì)于給定的兩條航線是否相交,設(shè)北岸城
從上面的結(jié)論可以看出,最優(yōu)的選擇方案中,如果將所有航線按北岸村莊號(hào)從小到大排序,序列中每一個(gè)北岸村莊對(duì)應(yīng)的南岸村莊號(hào)必然滿足B1<B2<B3……<Bn(n為選出來的航線數(shù))。同樣,對(duì)于任一個(gè)方案,如果北岸村莊排好序后,與之對(duì)應(yīng)的南岸村莊也是按升序排列,那么該方案必然不存在相交的兩條航線;相反,如果南岸村莊不是按升序排列,必存在兩條相交的航線。因此,我們可以先將各航線按北岸村莊號(hào)排一個(gè)序,那么最優(yōu)的方案必然是從相對(duì)應(yīng)的南岸村莊中找出一個(gè)最長不下降序列,該序列的長度即為問題的解。
凸多邊形三角劃分
給定一個(gè)具有N(N<50)個(gè)頂點(diǎn)(從1到N編號(hào))的凸多邊形,每個(gè)頂點(diǎn)的權(quán)均已知。問如何把這個(gè)凸多邊形劃分成N-2個(gè)互不相交的三角形,使得這些三角形頂點(diǎn)的權(quán)的乘積之和最???輸入文件:第一行頂點(diǎn)數(shù)N
第二行N個(gè)頂點(diǎn)(從1到N)的權(quán)值輸出格式:最小的和的值各三角形組成的方式輸入示例:5122123245231輸出示例:Theminimumis:12214884Theformationof3triangle:345,153,123凸多邊形三角劃分給定一個(gè)具有N(N<50)個(gè)頂點(diǎn)(從1到N分析設(shè)F[I,J](I<J)表示從頂點(diǎn)I到頂點(diǎn)J的凸多邊形三角剖分后所得到的最大乘積,我們可以得到下面的動(dòng)態(tài)轉(zhuǎn)移方程:F[I,J]=Min{F[I,K]+F[K,J]+S[I]*S[J]*S[K]}(0<I<K<J<=N)初始條件:F[1,2]=0目標(biāo)狀態(tài):F[1,N]但我們可以發(fā)現(xiàn),由于這里為乘積之和,在輸入數(shù)據(jù)較大時(shí)有可能超過長整形范圍,所以還需用高精度計(jì)算
分析設(shè)F[I,J](I<J)表示從頂點(diǎn)I到頂點(diǎn)J的凸多邊形三在數(shù)字串中插入若干(K個(gè))乘號(hào)使總的乘積最大。分析:定義從l到r加入k個(gè)乘號(hào)的最大乘積值為p(l,r,k)。p(l,r,k)=max{d(l,q)*p(q+1,r,k-1)}數(shù)字最大乘積在數(shù)字串中插入若干(K個(gè))乘號(hào)使總的乘積最大。數(shù)字最大乘積
解題思路
定義:從l到r加入k個(gè)乘號(hào)的最大乘積值p(l,r,k)。p(l,r,k)=max{d(l,q)*p(q+1,r,k-1)}
解題思路樹形動(dòng)態(tài)規(guī)劃(皇宮看守)
太平王世子事件后,陸小鳳成了皇上特聘的御前一品侍衛(wèi)?;蕦m以午門為起點(diǎn),直到后宮嬪妃們的寢宮,呈一棵樹的形狀;某些宮殿間可以互相望見。大內(nèi)保衛(wèi)森嚴(yán),三步一崗,五步一哨,每個(gè)宮殿都要有人全天候看守,在不同的宮殿安排看守所需的費(fèi)用不同??墒顷懶▲P手上的經(jīng)費(fèi)不足,無論如何也沒法在每個(gè)宮殿都安置留守侍衛(wèi)。編程任務(wù):幫助陸小鳳布置侍衛(wèi),在看守全部宮殿的前提下,使得花費(fèi)的經(jīng)費(fèi)最少。數(shù)據(jù)輸入:輸入數(shù)據(jù)由文件名為INPUT.TXT的文本文件提供。輸入文件中數(shù)據(jù)表示一棵樹,描述如下:第1行n,表示樹中結(jié)點(diǎn)的數(shù)目。第2行至第n+1行,每行描述每個(gè)宮殿結(jié)點(diǎn)信息,依次為:該宮殿結(jié)點(diǎn)標(biāo)號(hào)i(0<i<=n),在該宮殿安置侍衛(wèi)所需的經(jīng)費(fèi)k,該邊的兒子數(shù)m,接下來m個(gè)數(shù),分別是這個(gè)節(jié)點(diǎn)的m個(gè)兒子的標(biāo)號(hào)r1,r2,...,rm。對(duì)于一個(gè)n(0<n<=1500)個(gè)結(jié)點(diǎn)的樹,結(jié)點(diǎn)標(biāo)號(hào)在1到n之間,且標(biāo)號(hào)不重復(fù)。數(shù)據(jù)輸出:輸出到OUTPUT.TXT文件中。輸出文件僅包含一個(gè)數(shù),為所求的最少的經(jīng)費(fèi)。樹形動(dòng)態(tài)規(guī)劃(皇宮看守)輸入數(shù)據(jù)示例
輸出數(shù)據(jù)示例
25輸入數(shù)據(jù)示例輸出數(shù)據(jù)示例問題分析求給定的帶權(quán)樹的符合下面條件的子頂點(diǎn)集合V:
1.若點(diǎn)i∈V,則所有與i相鄰的點(diǎn)j可被標(biāo)號(hào)。
2.任意一個(gè)點(diǎn)j,若j不屬于V,則j可被標(biāo)號(hào)。
3.S=∑(Weight[i],i∈V),并且S最小。
問題分析求給定的帶權(quán)樹的符合下面條件的子頂點(diǎn)集合V:
考慮到樹本身的特性:除了根節(jié)點(diǎn)外,每一個(gè)節(jié)點(diǎn)都僅與該節(jié)點(diǎn)的父節(jié)點(diǎn)與兒子節(jié)點(diǎn)有關(guān)系;大多數(shù)情況下,每個(gè)節(jié)點(diǎn)的狀況都是由它的兒子節(jié)點(diǎn)的狀況決定的。這與動(dòng)態(tài)規(guī)劃的無后效性要求相符,再加上本題求的又是最優(yōu)方案,這一切都與動(dòng)態(tài)規(guī)劃算法不謀而合。
考慮到樹本身的特性:除了根節(jié)點(diǎn)外,每一個(gè)節(jié)點(diǎn)都僅與該節(jié)
要求覆蓋以節(jié)點(diǎn)i為頂點(diǎn)的樹的最佳方案Vi,顯然只需考慮節(jié)點(diǎn)i屬于或不屬于集合V兩種情況,兩者擇優(yōu)即可。即Vi=min{Vi1,Vi2選與不選}(1表示屬于,2表示不屬于)
要求覆蓋以節(jié)點(diǎn)i為頂點(diǎn)的樹的最佳方案Vi,顯然只需考慮(一)若i∈V,則對(duì)于i的任一兒子j,也只有屬于或不屬于集合V兩種情況:(1)若j∈V,則問題轉(zhuǎn)化到求Vj1的小一級(jí)規(guī)模問題,轉(zhuǎn)化成功;
(2)若j不屬于V,則要不求Vj2,要不就是j不能被j的任意一個(gè)兒子標(biāo)號(hào),則求所有Vk(k為j的兒子),Vi1求好了。(一)若i∈V,則對(duì)于i的任一兒子j,也只有屬于或不屬
(二)若i不屬于V,i一定要能被i的某個(gè)兒子j標(biāo)號(hào),這時(shí)求所有Vj(j為i的兒子)。若所有的j都是j被j的兒子標(biāo)號(hào)時(shí)最“省”(即所有Vj=Vj2),那么實(shí)際上按這樣的方案沒有一個(gè)j∈V,造成了i不能被標(biāo)號(hào)。這時(shí)只要找一個(gè)"犧牲"最小的i的兒子j,把方案Vj2換成Vj1。這樣就求出了"覆蓋以節(jié)點(diǎn)i為頂點(diǎn)且不包括節(jié)點(diǎn)i的最佳節(jié)點(diǎn)集Vi2"。(二)若i不屬于V,i一定要能被i的某個(gè)兒子j標(biāo)號(hào),這時(shí)狀態(tài)轉(zhuǎn)移方程
通過上面的分析,我們很容易得到下面這組狀態(tài)轉(zhuǎn)移方程:
F(i)=min{F(i,1),F(i,2)}{選或者不選}
F(i,1)=Weight(i)+∑min{F(j),∑min{F(k,1),F(k,2)}}
{選,i點(diǎn)以下最小花費(fèi)=i花+min{i兒子,min{孫子選不選}}}
F(i,2)=∑F(j);若所有F(j)<F(j,1),則換取代價(jià)最小的F(j,2)
(以上j為i兒子,k為j兒子)邊界條件
F(i)=F(i,1)
F(i,1)=Weight(i)
F(i,2)=+∞
(以上i為葉子節(jié)點(diǎn))狀態(tài)轉(zhuǎn)移方程
通過上面的分析,我們很容易得到下面這組狀態(tài)轉(zhuǎn)移動(dòng)態(tài)規(guī)劃模型的建立1、一般動(dòng)態(tài)規(guī)劃某些問題在狀態(tài)的選擇上會(huì)遇到一些困難,我們可以采用一種類似于枚舉的動(dòng)態(tài)規(guī)劃。動(dòng)態(tài)規(guī)劃模型的建立1、一般動(dòng)態(tài)規(guī)劃例題1:骨牌游戲
一張骨牌可被分為兩個(gè)正方形。每個(gè)正方形為空或有1至6個(gè)點(diǎn)。如下圖上面的一排正方形點(diǎn)數(shù)總和為6+1+1+1=9,底下一排的點(diǎn)數(shù)為1+5+3+2=11。上部和底部之差為2。任一張骨牌能被轉(zhuǎn)動(dòng)180°,保持其正面始終朝上。為了使骨牌上下點(diǎn)數(shù)之差最少,求所需旋轉(zhuǎn)的次數(shù)最少為多少?例如上圖,至多只需將最后一張骨牌旋轉(zhuǎn)一次,便能使差值為0,因此在此情況下,答案為1。例題1:骨牌游戲一張骨牌可被分為兩個(gè)正方形。每個(gè)分析我們不妨先不考慮最少旋轉(zhuǎn)次數(shù),而是找出一個(gè)使上下兩行絕對(duì)值差最小的方案。也許有人會(huì)想到用F[I]表示前I張骨牌能夠成的最小差值,構(gòu)造一個(gè)動(dòng)態(tài)規(guī)劃方程來解決該問題。但只要細(xì)想就會(huì)發(fā)現(xiàn),該問題用這種方式規(guī)劃不滿足最優(yōu)性原理,用這種形式的動(dòng)態(tài)規(guī)劃實(shí)際上是一種貪心,有反例!注意到骨牌上的點(diǎn)數(shù)范圍很小,只可取0到6,因此,我們可以用F[I,J]表示前I張骨牌能否構(gòu)造出上下差為J的方案。于是我們可以列出如下動(dòng)態(tài)轉(zhuǎn)移方程:f[I,j]=f[I–1,j–(a[I]–b[I])]orf[I–1,j–(b[I]-a[I])]其中A[I]、B[I]分別表示第I張骨牌最初上下兩面的點(diǎn)數(shù)。對(duì)應(yīng)的兩種轉(zhuǎn)移方式則分別表示第I張骨牌翻動(dòng)與第I張骨牌不翻動(dòng)的情況。邊界:f[0,0]=True至于最后求出的最少差值,只要從F[n,j]中尋找一個(gè)可以取到的絕對(duì)最小的J即可。由于n最大為1000,骨牌上的點(diǎn)數(shù)為0到6,所以最小差值的范圍也只是-6000到6000,該算法在最壞的情況下要計(jì)算1000*12000次,時(shí)間效率比起搜索,要快很多。分析我們不妨先不考慮最少旋轉(zhuǎn)次數(shù),而是現(xiàn)在的問題是如何求出最少翻動(dòng)的骨牌數(shù)。受到前面方程的啟發(fā),我們可以重新定義一下F數(shù)組,用F[I,J]表示前I張骨牌構(gòu)成差值J要翻動(dòng)的最小骨牌數(shù)。類似的,我們可以列出如下方程:f[I,j]=min{f[I–1,j–(a[I]–b[I])],f[I–1,j–(b[I]–a[I])]+1}
由于第一種選擇不翻動(dòng)第I張骨牌,所以最小翻動(dòng)次數(shù)在原基礎(chǔ)上不變。而第二種選擇要翻動(dòng)骨牌I,所以最小翻動(dòng)次數(shù)要加1。邊界:f[0,0]=0初始化:將整個(gè)F數(shù)組的值都附成一個(gè)足夠大的數(shù)MAX,不難想到,如果用前I張骨牌不可構(gòu)成差值J,最后F[I,J]的值一定為MAX。要求出最小差值和最小翻動(dòng)次數(shù),只要從F[N,J]中選出一個(gè)不為max,且絕對(duì)值最小的J,選出的J對(duì)應(yīng)的F[I,J]的值即為問題的解。
注意:因?yàn)閱栴}的處理涉及到絕對(duì)值,所以如果F[I,J]與F[I,-J]的情況都有可能取到,我們應(yīng)該從這兩個(gè)量中選出一個(gè)小的作為最小翻動(dòng)骨牌數(shù)。
現(xiàn)在的問題是如何求出最少翻動(dòng)的骨牌數(shù)小優(yōu)化假設(shè)前I-1張骨牌可以翻出的最小差值為min,可以翻出的最大差值為max。注意,這個(gè)最小差值與問題中描述的不同,它是上面一行的和減去下面一行的和,而不是上面一行的和減去下面一行和的絕對(duì)值。易知,前I張骨牌能夠翻出的最小差值不會(huì)小于min-abs(a[I]–b[I]),最大差值不會(huì)大于max+abs(a[I]–b[I]),利用這一規(guī)律,在求F[I,J]的值時(shí),我們可以將J循環(huán)的起始值和終值設(shè)為min和max。min和max的值也在計(jì)算過程中不斷更新。這樣可以減少一些不必要的計(jì)算,提高程序的效率。小優(yōu)化假設(shè)前I-1張骨牌可以翻出的最小差動(dòng)態(tài)規(guī)劃模型的建立2、多次動(dòng)態(tài)規(guī)劃有些問題的求解過程對(duì)應(yīng)多個(gè)狀態(tài)轉(zhuǎn)移方程;或者雖對(duì)應(yīng)一個(gè)狀態(tài)轉(zhuǎn)移方程,但由于內(nèi)存空間限制,一次動(dòng)態(tài)規(guī)劃僅能計(jì)算出最有解的值,無法構(gòu)造最有解的形成過程。在這種情況下,需要進(jìn)行多次動(dòng)態(tài)規(guī)劃。動(dòng)態(tài)規(guī)劃模型的建立2、多次動(dòng)態(tài)規(guī)劃最長公共子串問題
有兩個(gè)字符串A,B,當(dāng)存在一個(gè)嚴(yán)格遞增的整數(shù)序列i1,i2,…,im,滿足a1=bi1,a2=bi2,…,am=bim,我們則說A包含于B。例如,“adg”包含于“abcdefg”,而不包含于“gfedcba”?,F(xiàn)在有三個(gè)字符串A,B,C,要求你找出一個(gè)滿足以下條件的最長的字符串D。①D包含于A;②D包含于B;③D包含于C。輸入:A,B,C。輸出:D。最長公共子串問題有兩個(gè)字符串A,B分析首先,定義一個(gè)字串“前綴”的概念:給定一個(gè)字串s=s1…sm。對(duì)于I=0..m,定義s的第I個(gè)前綴為s’I=s1…si。三個(gè)輸入串A,B,C的所有前綴組成了最長公共子串的子問題空間。由此,我們發(fā)現(xiàn)最長公共子串的最優(yōu)子結(jié)構(gòu)性質(zhì)。設(shè):A={a1,…,am};B={b1,…,bn};C={c1,…,ch}。A,B,C的最長公共子串為D={d1,…,dk},D的長度為k。分析首先,定義一個(gè)字串“前綴”的概念:
性質(zhì)1:am=bn=ch,則dk=am=bn=ch且d’k-1是a’m-1,b’n-1,c’h-1的一個(gè)最長公共子串。性質(zhì)2:am≠bn,am≠ch,bn=ch,則dk≠am,蘊(yùn)含D是a’m-1和B、C的一個(gè)最長公共子串。
性質(zhì)1:am=bn=ch,則dk=am=bn=ch性質(zhì)3:bn≠am,bn≠ch,am=ch,則dk≠bn,蘊(yùn)含D是b’n-1和A、C的一個(gè)最長公共子串。性質(zhì)4:ch≠am,ch≠bn,am=bn,則dk≠ch,蘊(yùn)含D是c’h-1和A、B的一個(gè)最長公共子串。性質(zhì)3:bn≠am,bn≠ch,am=ch,則dk≠bn,蘊(yùn)
由此可見,字串A、B和C的最長公共字串包含了三個(gè)字串前綴的最長公共字串,說明該問題具備最優(yōu)子結(jié)構(gòu)的性質(zhì)。由此可見,字串A、B和C的最長公共字串包設(shè)f[I,j,k]為a’i,b’j,c’k的一個(gè)最長公共子串的長度(0≤i≤m,0≤j≤n,0≤k≤h)。f[m,n,h]為問題的解,則狀態(tài)轉(zhuǎn)移方程為:當(dāng)(j=0)or(k=0)時(shí),f[I,j,k]=0;當(dāng)(ai=bj=ck)時(shí),f[I,j,k]= f[I-1,j-1,k-1]+1;當(dāng)(ai≠bj)或(bj≠ck)時(shí),f[I,j,k]=max{f[I-1,j,k],f[I,j-1,k],f[I,j,k-1]}。設(shè)f[I,j,k]為a’i,b’j,c’k的一個(gè)最長公共子串
由于A,B,C三個(gè)字串的長度上限為10000,空間耗費(fèi)較大,為此:(1)采用指針類型:f[I]^[j,k];(2)及時(shí)收回內(nèi)存:由于計(jì)算f[I]時(shí),只需要f[I-1],因此可及時(shí)釋放內(nèi)存空間。
由于A,B,C三個(gè)字串的長度上限為10(3)進(jìn)行兩次動(dòng)態(tài)程序設(shè)計(jì):由于f[1]…f[I-2]已釋放,無法根據(jù)狀態(tài)轉(zhuǎn)移方程構(gòu)造完整的最長公共子串,因此必須進(jìn)行兩次動(dòng)態(tài)規(guī)劃:①第一次動(dòng)態(tài)方程設(shè)計(jì),根據(jù)f[r]…f[m]構(gòu)造ar…am中所含的最長公共子串。②第二次動(dòng)態(tài)程序設(shè)計(jì),根據(jù)f[1]…f[I-2]構(gòu)造a1…ar-1中所含的最長公共子串,并與第一次動(dòng)態(tài)規(guī)劃產(chǎn)生的公共子串拼接,形成完整的公共子串D。(3)進(jìn)行兩次動(dòng)態(tài)程序設(shè)計(jì):由于f[1]…f[I-2]已釋放雙層動(dòng)態(tài)規(guī)劃農(nóng)
田
個(gè)
數(shù)(count.pas)
你的老家在河北農(nóng)村。過年時(shí),你回老家去拜年。你家有一片NM農(nóng)田,將其看成一個(gè)NM的方格矩陣,有些方格是一片水域。你的農(nóng)村伯伯聽說你是學(xué)計(jì)算機(jī)的,給你出了一道題:他問你:這片農(nóng)田總共包含了多少個(gè)不存在水域的正方形農(nóng)田。兩個(gè)正方形農(nóng)田不同必須至少包含下面的兩個(gè)條件中的一條:邊長不相等左上角的方格不是同一方格雙層動(dòng)態(tài)規(guī)劃農(nóng)田個(gè)數(shù)(count.pas)輸入
輸入數(shù)據(jù)第一行為兩個(gè)由空格分開的正整數(shù)N、M(1<=m<n<=1000)
第2行到第N+1行每行有M個(gè)數(shù)字(0或1),描述了這一片農(nóng)田。0表示這個(gè)方格為水域,否則為農(nóng)田(注意:數(shù)字之間沒有空格,而且每行不會(huì)出現(xiàn)空格)
輸出
滿足條件的正方形農(nóng)田個(gè)數(shù)。樣例輸入樣例輸出
335110110000
輸入分析
(1)設(shè)F[I,J]表示以方格(I,J)為右下角,可以得到的最大無水正方形邊長,那么顯然如果(I,J)是水域,F(xiàn)[I,J]=0;否則F[I,J]=Min{F[I-1,J],F(xiàn)[I,J-1],F(xiàn)[I-1,J-1]}+1(2)求出了F數(shù)組的值后,我們可以用F1[I]表示F數(shù)組中,值為I的個(gè)數(shù)。(3)顯然,假定邊長為I的正方形數(shù)目為Sum[I],那么有Sum[I]=Sum[I+1]+F1[I]
(4)最后只要算出Sum數(shù)組各個(gè)值的和為問題的解。分析(1)設(shè)F[I,J]表示以方格(I,J)為右下角動(dòng)態(tài)規(guī)劃時(shí)間效率的優(yōu)化一、減少狀態(tài)總數(shù)1、改進(jìn)狀態(tài)表示狀態(tài)的規(guī)模與狀態(tài)表示的方法密切相關(guān),通過改進(jìn)狀態(tài)表示減小狀態(tài)總數(shù)是應(yīng)用較為普遍的一種方法。動(dòng)態(tài)規(guī)劃時(shí)間效率的優(yōu)化一、減少狀態(tài)總數(shù)
有一批編號(hào)為1至N且尺寸規(guī)格一樣的箱子?,F(xiàn)在要將其中某些箱子疊放起來,使疊放的高度最大,箱子疊放的規(guī)則如下:一、每個(gè)箱子上最多只能直接疊放一個(gè)箱子;二、編號(hào)較小的箱子不能放在編號(hào)較大的箱子之上;{決定不會(huì)產(chǎn)生后效性}三、每個(gè)箱子都給出了自身重量與可承受重量,每個(gè)箱子上的所有箱子重量之和不得超過該箱的可承受重量。輸入箱子數(shù)N(1≤N≤1000)及每個(gè)箱子的自身重量與可承受重量,兩個(gè)數(shù)值均為小于等于3000的正整數(shù)。輸出最多可疊放的箱子總數(shù)M和每個(gè)箱子的編號(hào)。例題3:疊放箱子有一批編號(hào)為1至N且尺寸規(guī)格一樣的箱子?,F(xiàn)在要將
箱子是按編號(hào)順序疊放,所以可用動(dòng)態(tài)規(guī)劃求解。設(shè):
Weight[I]表示第I個(gè)箱子的重量。
Support[I]表示第I個(gè)箱子的承受重量。
F(i,j)表示前i個(gè)箱子中最多可選出F(i,j)個(gè)疊放,還可承受重量j。{線性的劃分}
F(i,j)=Max{F(i-1,j-Weight[i])+1,F(i-1,j)}。{放,不放}(其中,J<=support[I])算法分析箱子是按編號(hào)順序疊放,所以可用動(dòng)態(tài)規(guī)劃求解。設(shè):算
上述算法的狀態(tài)總數(shù)為O(n*Total_Weight),每個(gè)狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)為O(1),每次狀態(tài)轉(zhuǎn)移的時(shí)間為O(1)??倳r(shí)間復(fù)雜度=1000*3000=3*106上述算法的狀態(tài)總數(shù)為O(n*Total_Weight),改進(jìn)一下狀態(tài)的表示方式,設(shè)F[I,j]表示前i個(gè)箱子疊放j個(gè)箱子時(shí)可承受的最小重量。
F[i,j]:=Min{F[i-1,j],F(xiàn)[i-1,j-1]+Weight[i]}Ans:=Max(J|F[i,j])(F[i,j]〈=support[i]〉)上述算法的狀態(tài)總數(shù)為O(n*n),每個(gè)狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)為O(1),每次狀態(tài)轉(zhuǎn)移的時(shí)間為O(1),所以總的時(shí)間復(fù)雜度=1000*1000=1*10^6。算法優(yōu)化改進(jìn)一下狀態(tài)的表示方式,設(shè)F[I,j]表示前i個(gè)箱子疊放j個(gè)
改進(jìn)后的算法的時(shí)間復(fù)雜度是改進(jìn)前的1/3。但如果在Tot-Weight的值很小,而n的值相當(dāng)大,前面一種方法更好。對(duì)于不同的題目,要從多方面分析,選擇適合的最優(yōu)方法。改進(jìn)后的算法的時(shí)間復(fù)雜度是改進(jìn)前的1/3。但如果在To2、選擇適當(dāng)?shù)囊?guī)劃方向規(guī)劃方向的選擇主要有兩種:順推和逆推。若初始狀態(tài)確定,目標(biāo)狀態(tài)不確定,則應(yīng)考慮采用順推,反之,若目標(biāo)狀態(tài)確定,而初始狀態(tài)不確定,就應(yīng)該考慮采用逆推。那么,若是初始狀態(tài)和目標(biāo)狀態(tài)都已確定,可以選用雙向規(guī)劃。動(dòng)態(tài)規(guī)劃時(shí)間效率的優(yōu)化2、選擇適當(dāng)?shù)囊?guī)劃方向動(dòng)態(tài)規(guī)劃時(shí)間效率的優(yōu)化
雙向規(guī)劃與雙向搜索的主要思想類似:在狀態(tài)空間十分龐大,而初始狀態(tài)和目標(biāo)狀態(tài)又都已確定,為了減少狀態(tài)的規(guī)模,分別從初始狀態(tài)和目標(biāo)狀態(tài)兩個(gè)方向進(jìn)行擴(kuò)展,并在兩者的交匯處得到問題的解。雙向規(guī)劃與雙向搜索的主要思想類似:在狀態(tài)空例題4:Divide(Merc`2000)
有價(jià)值分別為1..6的大理石各a[1..6]塊,現(xiàn)要將它們分成兩部分,使得兩部分價(jià)值和相等,問是否可以實(shí)現(xiàn)。其中大理石的總數(shù)不超過20000。動(dòng)態(tài)規(guī)劃時(shí)間效率的優(yōu)化例題4:Divide(Merc`2000)動(dòng)態(tài)規(guī)劃時(shí)間效率令S=∑(i*a[i]),若S為奇數(shù),則不可能實(shí)現(xiàn),否則令Mid=S/2,問題轉(zhuǎn)化為能否從給定的數(shù)中中選取部分?jǐn)?shù),使其和為Mid。設(shè)m[i,j]表示能否從價(jià)值為1..i的大理石中選出部分大理石,使其價(jià)值和為j,若能,則用true表示,否則用false表示。則狀態(tài)轉(zhuǎn)移方程為:
m[i,j]=m[i,j]ORm[i-1,j-i*k](0≤k≤a[i])
規(guī)劃的邊界條件為:m[i,0]=true;0≤i≤6若m[i,Mid]=true,0≤i≤6,則可以實(shí)現(xiàn)題目要求,否則不可能實(shí)現(xiàn)。算法分析令S=∑(i*a[i]),若S為奇數(shù),則不可能實(shí)現(xiàn),否則令M
上述算法每個(gè)狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)為a[i],每次狀態(tài)轉(zhuǎn)移的時(shí)間為O(1),狀態(tài)總數(shù)是所有值為true的狀態(tài)的總數(shù)。上述算法每個(gè)狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)為a[i],每次狀態(tài)轉(zhuǎn)移的時(shí)
本題在i較小時(shí),值為true的狀態(tài)也較少,但隨著i的增大,值為true的狀態(tài)也急劇增多,影響了算法的時(shí)間效率。我們分別求出從價(jià)值為1..3的大理石中選出部分大理石所能獲得的所有價(jià)值和,和從價(jià)值為4..6的大理石中選出部分大理石所能獲得的所有價(jià)值和。再判斷是否存在和為Mid的價(jià)值和,從而得出問題的解。算法優(yōu)化本題在i較小時(shí),值為true的狀態(tài)也較少,但隨著i狀態(tài)轉(zhuǎn)移方程改進(jìn)為:當(dāng)i≤3時(shí):m[i,j]=m[i,j]O
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2024年跨境電商融資咨詢與市場拓展合同協(xié)議3篇
- 2024年貨物水運(yùn)合同3篇
- 2024某某投資合伙企業(yè)投資組合管理及調(diào)整補(bǔ)充協(xié)議3篇
- 2024影視劇組演員保密合同及個(gè)人隱私保護(hù)協(xié)議3篇
- 2024房屋個(gè)體戶租賃合同范本
- 2024年裝修工程清包勞動(dòng)力服務(wù)協(xié)議范本版B版
- 2024年甲乙雙方關(guān)于油茶苗木種植與收購的詳細(xì)協(xié)議
- 2024年空中飛行區(qū)使用協(xié)議
- 2024年股東出資協(xié)議樣本2篇
- 2024水果種植基地與旅游項(xiàng)目采購合同3篇
- 2025年國家圖書館招聘筆試參考題庫含答案解析
- 機(jī)器人課程課程設(shè)計(jì)
- 南充市市級(jí)事業(yè)單位2024年公招人員擬聘人員歷年管理單位遴選500模擬題附帶答案詳解
- 安全知識(shí)考試題庫500題(含答案)
- 2024-2025學(xué)年上學(xué)期南京小學(xué)數(shù)學(xué)六年級(jí)期末模擬試卷
- 河北省保定市定興縣2023-2024學(xué)年一年級(jí)上學(xué)期期末調(diào)研數(shù)學(xué)試題(含答案)
- 2025年中國蛋糕行業(yè)市場規(guī)模及發(fā)展前景研究報(bào)告(智研咨詢發(fā)布)
- 護(hù)理組長年底述職報(bào)告
- 護(hù)理不良事件分析 課件
- 糖尿病患者健康管理測試試題(三套題-有答案)
- 《住院患者身體約束的護(hù)理》團(tuán)體標(biāo)準(zhǔn)解讀課件
評(píng)論
0/150
提交評(píng)論