算法設(shè)計(jì)與分析第07章(存儲(chǔ)版)
【正文】 )X,1(fjj ????????????????現(xiàn)用 Sj表示函數(shù)曲線 f(j,X)的全部階躍點(diǎn)的集合 ，Sj={(Xi,Pi)| 函數(shù)曲線 f(j,X)的全部階躍點(diǎn) }， 1?j?n1，其中 S1={(0,0)}。 Si=MergerPurge(Si1,S1i)。 在最壞情況下，算法的時(shí)間復(fù)雜度是 O(2n)。完成這些任務(wù)的時(shí)間由矩陣 M給定 。 每個(gè)作業(yè)加工的順序總是先在 P1上加工 ， 然后在 P2上加工 。 這樣做能得到最優(yōu)調(diào)度方案 (1)如果 min{a0,a1,… ,an?1, b0,b1,… ,bn?1}是 ai， 則 ai應(yīng)是最優(yōu)排列的第一個(gè)作業(yè)； (2)如果 min{a0,a1,… ,an1,b0,b1,… ,bn?1}是 bj， 則 bj應(yīng)是最優(yōu)排列的最后一個(gè)作業(yè)； (3) 繼續(xù) （ 1） 和 （ 2） 的做法 ， 直到完成所有作業(yè)的排列 。 對(duì)三元組表的每一項(xiàng) d[i]， 0?in， 從左和右兩端生成最優(yōu)作業(yè)排列 c[j], 0?jn， c[j]是作業(yè)號(hào) 。i++) if(a[i]b[i]) { d[i].jobNo=i。 for (i=0。besti, amp。k=j。besti, amp。 if(thissumsum){ sum=thissum。則s1+s2即為出現(xiàn)情形 C時(shí)的最優(yōu)值。lefts=0。i=right。由此可得計(jì)算 bj的動(dòng)態(tài)規(guī)劃遞歸式 bj=max{bj1+aj， aj}， 1≤j≤n。 } return sum。 else b=a[i]。 } return sum。rights=0。 int rightsum=MaxSubSum(a,center+1,right)。對(duì)于情形 C，容易看出，a[n/2]與 a[n/2+1]在最優(yōu)子序列中。j=n。 } ? 算法有 3重循環(huán)，復(fù)雜性為 O(n3)。j++){ int thissum=0。當(dāng)所有整數(shù)均為負(fù)值時(shí)定義其最大子段和為 0。 } Sort(d,n)。 for(int i=0。 建立由三元組 （ 作業(yè)號(hào) ,處理時(shí)間 ,設(shè)備號(hào) ） 組成的三元組表 d。 如果在調(diào)度方案的作業(yè)排列中 ， 作業(yè) i和 j滿足min{bi,aj}?min{bj,ai}， 則稱作業(yè) i和 j滿足 Johnson不等式 。 本節(jié)只討論當(dāng) m=2時(shí)獲得 OFT的調(diào)度方案的算法 ，這就是 雙機(jī)流水作業(yè)調(diào)度 問(wèn)題 。 這就是 流水線作業(yè)調(diào)度(flow shop schedule)問(wèn)題 。 回溯確定 xn－ 2,xn3,? ,x0。in1。設(shè) (x0, x1,… , xn－ 1)， xi?{0,1}是 0/1背包的最優(yōu)解，那么， (x1 ,x2,… , xn－ 1) 必然是 0/1背包子問(wèn)題的最優(yōu)解：背包載重M?w0x0，共有 n1件物品，第 i件物品的重量為 wi，效益 pi， wi0， pi0， 1?in。 w[i][j]=w[i][j1]+p[j]+q[j]。 } w[n][n]=q[n]。 } void CreateOBST(float* p,float* q, float **c,int **r,float**w,int n) { for (int i=0。 這里 p和 q都已乘了 16。 s[i][j]=k。 【 程序 7－ 4】 矩陣連乘的備忘錄方法 int MatrixChain::LookupChain(int i, int j) { if (m[i][j]0) return m[i][j]。 } void MatrixChain::Traceback() { cout39。 Traceback(i,s[i][j])。s[i][j]=k。i=nr。 int *p,**m,**s,n。 這就是說(shuō) ， 矩陣連乘問(wèn)題的最優(yōu)解具有最優(yōu)子結(jié)構(gòu)特性 。 完全加括號(hào) 的矩陣連乘積可遞歸地定義為： 單個(gè)矩陣是完全加括號(hào)的； 矩陣連乘積 A是完全加括號(hào)的 ， 則 A可表示為兩個(gè)完全加括號(hào)的矩陣連乘積 B和 C的乘積并加括號(hào) ，即 A=(BC)。i++) for (j=0。 if (i!=j amp。path=new int *[n]。 最優(yōu)解的遞推關(guān)系 1nk1 ,]j][k[d]k][i[d ],j][i[dm i n {]j][i[d Ej,i Ej,i )j,i(w]j][i[d1k1k1kk1???????????????????? 若若重疊子問(wèn)題 ：為了計(jì)算 dk[i][j]時(shí)，必須先計(jì)算 dk－ 1[i][j]、 dk－ 1[i][k]和 dk－ 1[i][k]， dk?1的元素被多個(gè) dk的元素的計(jì)算共享。 delete []cost。q=v。 cost[n1]=0,d[n1]=1。 基本要素 一個(gè)最優(yōu)化多步?jīng)Q策問(wèn)題適合用動(dòng)態(tài)規(guī)劃法求解有兩個(gè)要素： 最優(yōu)子結(jié)構(gòu)特性和重疊子問(wèn)題。 分治法的子問(wèn)題相互獨(dú)立 ， 相同的子問(wèn)題被重復(fù)計(jì)算 ， 動(dòng)態(tài)規(guī)劃法解決這種子問(wèn)題重疊現(xiàn)象 。 一般方法 最優(yōu)性原理 指出，一個(gè)最優(yōu)策略具有這樣的性質(zhì)，不論過(guò)去狀態(tài)和決策如何，對(duì)前面的決策所形成的狀態(tài)而言，其余決策必定構(gòu)成最優(yōu)策略。對(duì)所有邊u,v?E，多段圖要求若 u?Vi，則 v?Vi＋ 1， 1?ik，每條邊的權(quán)值為 c(u,v)。j){ float min=INFTY。 } p[0]=0。 求總收益最大的資源分配方案 。 在算法的第 k步上應(yīng)作出決策：從 i到 j的最短路徑上是否包含結(jié)點(diǎn) k。i++){ d[i]=new T [n]。 else path[i][j]=1。 path[i][j]=path[k][j]。于是矩陣連乘 A0A1…A n1可記作 A{0:n1}。 int MChain()。in。 s[i][j]=i。A39。 if(s[i][j]+1j)cout39。cout39。 s[i][j]=i。 } int MatrixChain::LookupChain() { return LookupChain(0,n1)。 for (int m=i+1。c[i][i]=。 for (int m=2。 r[i][j]
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1