動態(tài)規(guī)劃dynamicprogrammingdp-閱讀頁
2025-08-02 12:37本頁面
【正文】 ths: APSP)n 最短路徑 :假設(shè) G為有向圖 ,其中每條邊都有一個成本 (cost),圖中每條有向路徑的長度 (或成本 )定義為該路徑上各邊的成本之和n 對于每對頂點 (i,的所有路徑中 ,具有最小長度的路徑為從 i的最短路徑n 求每對點間的最短路n 假定圖上無負成本的環(huán)路APSP: 例 1515n 如 圖 154所示。1,2,5,31,4,31,2,5,8,6,31,4,6,3n 由該圖可知 ,各路徑相應(yīng)的長度為 19,2是該圖中頂點 1到頂點 3的最短路徑。ifelseforkq c(i,n)是要求的 i到 j的最短路長度n 我們建立 c(i,j,k)和 c(i,j,k1)之間的遞歸關(guān)系A(chǔ)PSP:遞歸式n 對于任意 k＞ 0，q j,c(i,k1)+j,值的時間減少到 O(n3).n 迭代算法的偽代碼如圖 155所示。j)),即圖的鄰接矩陣 .n 算法迭代計算 C(k)(i,k)=C(k1)(i,k)n C(k)q 對 k行 k列以外的元素n C(k)(i,j)=max{C(k1)(i,C(k1)(i,給出某圖的長度矩陣 a， 156b為對應(yīng)的 kay值。中的 kay 值，可知從 1到 5的最短路徑是從 1到 kay[1][5]=4的最短路徑再加上從4到 5的最短路徑，因為 kay[4][5]=0，所以從 4到 5的最短路徑無中間頂點。重復(fù)以上過程，最后可得 1到 5的最短路徑為： 1， 2， 3， 4， 5。j)=c(i,有唯一一個 Ci對應(yīng)，稱為網(wǎng) (i,Ci)n (i,Ci)與 (j,Cj)組成非交叉子網(wǎng)，若（ ij） ? uiCuj且任何兩個子網(wǎng)是非交叉子網(wǎng) }q size(i,j)=|size(1,j)=0,size(1,j)=1,j=8,9,10forsize(2,7)=size(1,6)+1=1按 i則 MNS(i,j)包含 LCS: Longest Common Subsequencesn Sequencemeasurementq Substringnumberchangesoneanotherq Longestsubsequencesn Givensequences.m]y[1.findlongestmonthemforceO(n2m)q DPO(nm)Definition 1: subsequencen Definition 1: GivensequenceanotherZ=z1z2...zkaofifexistsstrictly increasingi1i2...ikindicesXthatallwexij=zj.n Example 1:X=abcdefg,issubsequenceX.twoXY,sequenceismon subsequenceXYissubsequencebothandX=abcdefgY=aaadgfd.ismonofandlongest mon subsequenceXYasubsequenceXYthelength.lengthaisnumberletterstheacdabdLCS.q LetandtwoandbeLCSofandxm=yn,zk=xm=ynZ[1..k1]anofY[1..n1].q If?yn,zk?xmthatisLCSX[1..m1]Y.q If?yn,zk?ynthatisLCSXY[1..n1].c[i,j]theofLCSX[1...i]Y[1...j].n c[i,j]beasarec[i,j]’s.weputeinspecific0 if i=0 or j=0c[i–1, j–1] + 1 if x[i] = y[j], max{c[i–1, j], c[i, j–1]} otherwise.c[i, j] =Algorithm of LCS 1. for i=1 to m do 2. c[i,0]=0。5. for i=1 to m do6. for j=1 to n do7. { 8. if x[I] ==y[j] then9. c[i,j]=c[i1,j1]+1。 11. else if c[i1,j]=c[i,j1] then 12. c[i,j]=c[i1,j]13. b[i,j]=2。14 }b[i,j] stores the directions. 1—diagnal, 2up, 3forward.Example 1 of an LCS X=BDCABAY=ABCBDABConstructing an LCSPrintLCS(b,X,i,j)1. i=m2. j=n。4. if b[i,j]==1 then { i=i1。 print “xi”。01234iXiABCYj BB ACD00000000001000 11 21 11 1 21221 1 2 2 3BB C BLCSorder):B C B(straightλ(ΩIΩO,B,)n ΩI=of=of===|Itii):probability===|=symbol=πip(I1ii):statei1,...iTisstateisoutputGivenλoutputO,p(O|GivenλoutputO,findstateXthat:{p(O,λ)}n LearningGivensequencefindmodelsuchmaximizeI|O(min{2n,nΣ1≤i≤npi提示 :|P(i)|≤為 n個正數(shù)的集合 ,試找出和數(shù)不超過 M且最大的 S的子集n 該問題是 NP難度問題 ,試用動態(tài)規(guī)劃法設(shè)計一算法練習(xí) (3)n r=(10,20,50,1,100),給出優(yōu)化的乘法順序和元素乘法數(shù)目練習(xí) (4),習(xí)題 19n T(i,j)=任務(wù) i按第 j種方式所需成本 (j=1,2)n 任務(wù)是拓撲排序的，必須先完成任務(wù) 1才能完成任務(wù)2…n 要求在時間 t之前完成所有任務(wù)且成本最小n cost(i,j)＝任務(wù) 1到 i能在 j時間內(nèi)完成的最小成本n cost(1,j)=∞jT(1,1)=C(1,1)T(1,2)=jcost(i1,jT(i,2))+C(i,2)}T=(2,1,4。2,3,4)， t=8分號前為第一種選擇；分號后為第二種選擇。n 分析算法的復(fù)雜性練習(xí) (5),習(xí)題 20n 假定一機器由 n種元件
高考資料相關(guān)推薦
鄂ICP備17016276號-1