算法設(shè)計與分析sorrybitlate

1、Last Section減 治插入排序: n2, n, n2/4快速排序+插入排序拓撲排序: 減一生成排列+ Johnson-Trotter生成子集+比特串方法假幣問題俄式乘法約瑟夫斯問題歐幾里德算法插值查找二叉查找樹變治_實例化簡預(yù)排序檢驗數(shù)組中元素的惟一性： n(n-1)/2, nlogn+n模式計算： n(n-1)/2+n-1, nlogn+(n)高斯消去法Partial pivotingLU 分解矩陣的逆AVL樹: 1.39logn, 1.01logn變治_改變表現(xiàn)變換為同樣實例的不同表現(xiàn)改變表現(xiàn)(Representation Change)2-3 樹堆和堆排序霍納法則二進制冪變治變換

2、為另一個問題的實例， 這種問題的算法是已知的問題化簡(Problem reduction)。Lcm圖中的路徑數(shù)量函數(shù)極值綜合除法凸包，解析幾何線性規(guī)劃簡化為圖MST vs. Element Uniqueness動態(tài)規(guī)劃動態(tài)規(guī)劃是解決多階段決策過程最優(yōu)化的一種方法。動態(tài)規(guī)劃模型的分類：離散確定性順序解法與可逆過程兩個弱點：得出目標(biāo)函數(shù)方程后，尚無統(tǒng)一的處理方法，必須根據(jù)具體問題的性質(zhì)結(jié)合相應(yīng)的數(shù)學(xué)技巧來求解；維數(shù)障礙。動態(tài)規(guī)劃的基本概念和基本方程例1最短路線問題給出一個線路網(wǎng)絡(luò)， 從A點要鋪設(shè)一條管道到G點，其兩點之間連線上的數(shù)字表示兩點間的距離；要求選擇一條由A到G的鋪管線路，使總距離為最短。

3、如圖AE2D2B2B1C4C3C2C1D3D1E1E3F2F1G336625533432122335386631485768最短路線問題最短路線問題從A到G可以分為6個階段。各個階段的決策不同，鋪管路線就不同。明顯地，當(dāng)某段的始點給定時，它直接影響著后面階段的引進路線和整個路線的長短，而后面各階段的路線的發(fā)展不受這點以前各段路線的影響。問題的要求是：在各個階段選取一個恰當(dāng)?shù)臎Q策，使由這些決策組成的一個策略所決定的一條路線，其總路程最短-最優(yōu)策略窮舉法：共有2 * 3 * 2 * 2 * 2 * 1=48 條路線動態(tài)規(guī)劃的基本概念階段(Stage)把所給問題的過程，恰當(dāng)?shù)貏澐殖扇舾蓚€相互聯(lián)系的階

4、段，以便于求解。通常用k表示階段變量。例中第一階段為AB，包含2條支路：A B1和A B2狀態(tài)（State）狀態(tài)表示某段的出發(fā)位置。它既是該段某支路的始點，同時也是前一段某支路的終點。通常一個階段包含若干個狀態(tài)。描述過程狀態(tài)的變量，稱為狀態(tài)變量。常用xk表示在第k段的某一狀態(tài)。第k段狀態(tài)集合可表示為Xk = xk(1), xk(2), , xk(i) , , xk(r)故例中第三階段的狀態(tài)集合就可記為X3 = x3(1), x3(2), x3(3) , x3(4)=1, 2, 3, 4或X3 = C1, C2, C3, C4動態(tài)規(guī)劃的基本概念決策（Decision）決策就是某階段狀態(tài)給定以后，

5、從該狀態(tài)演變到下一階段某狀態(tài)的選擇。描述決策的變量，稱為決策變量。常用uk(xk)表示第k段當(dāng)狀態(tài)處于xk 時的決策變量。決策變量的取值往往限制在某一范圍之內(nèi)，此范圍稱為允許決策集合。通常以Dk(xk)表示第k段當(dāng)狀態(tài)處于xk 時的允許決策集合。uk(xk) Dk(xk)動態(tài)規(guī)劃的基本概念決策（Decision）決策就是某階段狀態(tài)給定以后，從該狀態(tài)演變到下一階段某狀態(tài)的選擇。描述決策的變量，稱為決策變量。常用uk(xk)表示第k段當(dāng)狀態(tài)處于xk 時的決策變量。決策變量的取值往往限制在某一范圍之內(nèi)，此范圍稱為允許決策集合。通常以Dk(xk)表示第k段當(dāng)狀態(tài)處于xk 時的允許決策集合。uk(xk)

6、 Dk(xk)例中第二階段狀態(tài)集合X2=B1，B2；則從B1出發(fā)的允許決策集合D2 ( B1 )=C1，C2， C3；若選擇點C2， 則u2 ( B1 )=C2。AE2D2B2B1C4C3C2C1D3D1E1E3F2F1G336625533432122335386631485768最短路線問題動態(tài)規(guī)劃的基本概念策略（Policy）由過程的第1階段開始到終點為止的過程，稱為問題的全過程。由每段的決策ui(xi)(i=1,2,n)組成的決策函數(shù)序列就稱為全過程策略，簡稱策略，記為p1,n。即p1,n(xk)= u1(x1), u2(x2), , un(xn)由第k段開始到終點的過程稱為原過程的后部

7、子過程（或稱為k子過程）。其決策函數(shù)序列 uk(xk)，, un(xn)稱為k子過程策略，簡稱子策略。即pk,n(xk)=uk(xk), uk+1(xk+2), , un(xn)在實際問題中，可供選擇的策略有一定的范圍，此范圍稱為允許策略集合，用P表示。從允許策略中找出達到最優(yōu)效果的策略稱為最優(yōu)策略。動態(tài)規(guī)劃的基本概念指標(biāo)函數(shù)在多階段決策過程最優(yōu)化問題中，指標(biāo)函數(shù)是用來衡量所實現(xiàn)過程的優(yōu)劣的一種數(shù)量指標(biāo)，它是一個定義在全過程和所有后部子過程上的確定數(shù)量函數(shù)，常用Vk,n表示。即Vk,n= Vk,n(xk ,uk ,xk+1 ,xn+1) k=1,2,n不同的問題中，指標(biāo)的含義也不同：距離、利潤

8、、成本、產(chǎn)量、資源消耗等。例中， Vk,n表示第k階段由點xk至終點G的距離；第k階段由點xk至uk(xk)的距離為階段指標(biāo)（階段效益），可記為k(xk ,uk ) 。(E1, F1) 。動態(tài)規(guī)劃的基本概念最優(yōu)指標(biāo)函數(shù)指標(biāo)函數(shù)Vk,n的最優(yōu)值，稱為相應(yīng)的最優(yōu)指標(biāo)函數(shù)。記為fk(xk). 例中，fk(xk)表示從第k段xk點到終點G的最短距離。如f4(D1)就表示從第4段中的D1點到G 點的最短距離。動態(tài)規(guī)劃的基本思想和基本方程生活中平常的事例，即可深刻揭示最短路線的重要特性：如果最短路線在第K站通過點Pk, 則由點Pk出發(fā)到達終點的這條路線，對于從點Pk出發(fā)到達終點的所有可能選擇的不同路線來說

9、，必定也是最短路線。動態(tài)規(guī)劃的方法是從終點逐段向始點方向?qū)ふ易疃搪肪€的一種方法。AE2D2B2B1C4C3C2C1D3D1E1E3F2F1G336625533432122335386631485768最短路線問題最短路線問題按照動態(tài)規(guī)劃的方法，從最后一段開始計算，由后向前逐步推移至A點：當(dāng)k = 6 時，f6(F1)表示在第6段由F1至G的最短距離，故f6(F1)=4。同理，f6(F2)=3。當(dāng)k = 5 時，若從E1出發(fā)，則有兩個選擇，一是至F1，一是至F2，則f5(E1)=min= min= 7這說明，由E1至終點G的最短距離為7，其最短路線是E1F1G，而相應(yīng)的決策變量u5(E1)=F1

10、.最短路線問題若從E2出發(fā)，也有兩個選擇，一是至F1，一是至F2，則f5(E2)=min= min= 5這說明，由E2至終點G的最短距離為5，其最短路線是E2F2G，而相應(yīng)的決策變量u5(E2)=F2.etc.AE2D2B2B1C4C3C2C1D3D1E1E3F2F1G336625533432122335386631485768最短路線問題動態(tài)規(guī)劃的函數(shù)基本方程在求解的各個階段，我們利用了k階段與k+1階段之間的如下關(guān)系： k = 6,5,4,3,2,1 f7(x7)= 0 (或?qū)懗?f6(x6) = d6(x6, G)動態(tài)規(guī)劃最優(yōu)化原理 動態(tài)規(guī)劃最優(yōu)化原理：作為整個過程的最優(yōu)策略具有這樣的性

11、質(zhì)：即無論過去的狀態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略?？赡孢^程順序解法：以G為始端，以A為終端的左行解法程序稱為順序解法逆序解法可以把段次顛倒過來求最優(yōu)解的多階段決策過程稱為可逆過程。順序解法和逆序解法只表示行進方向的不同或始端的顛倒。但用動態(tài)規(guī)劃方法求最優(yōu)解時，都是在行進方向規(guī)定后，均要逆著這個規(guī)定的行進方向，從最后一段向前逆推計算，逐段找出最優(yōu)途徑。 與窮舉法的對比 減少了計算量窮舉法：要對48條路線進行比較，比較運算要進行47次；求各條路線的距離（288次加法），即使使用逐段累加方法，也要進行0+6+12+32+48+48=146次加法運算。動態(tài)規(guī)劃

12、方法：比較運算（從k=5段開始向前算）共進行3+3+4+4+1=15次。每次比較運算對應(yīng)兩次加法運算，再去掉中間重復(fù)兩次（即B1C1， B2C4各多算了一次），實際只有28次加法運算。AE2D2B2B1C4C3C2C1D3D1E1E3F2F1G336625533432122335386631485768最短路線問題與窮舉法的對比豐富了計算結(jié)果在逆序解法中，使我們得到的不僅僅是由A點出發(fā)到終點G的最短路線及相應(yīng)的最短距離；而且得到了從所有各中間點出發(fā)到終點的最短路線及相應(yīng)的距離。即，求出的不是一個最優(yōu)策略，而是一族的最優(yōu)策略。這對許多實際問題有重要意義。構(gòu)成動態(tài)規(guī)劃模型的條件 建立動態(tài)規(guī)劃模型時

13、，除了要將實際問題恰當(dāng)?shù)貏澐秩舾蓚€階段（一般是根據(jù)時間和空間而劃分的）外，主要明確以下四個方面：正確選擇狀態(tài)變量xk, 使它既能描述過程的狀態(tài)，又要滿足無后效性。動態(tài)規(guī)劃中的狀態(tài)與一般所說的狀態(tài)概念是不同的，它必須具有三個特性：要能夠用來描述受控過程的演變特征。要滿足無后效性。 所謂無后效性是指：如果某段狀態(tài)給定，則在這段以后過程的發(fā)展不受前面各階段狀態(tài)的影響?？芍?。即是規(guī)定的各段狀態(tài)變量的值，由直接或間接都是可以知道的。構(gòu)成動態(tài)規(guī)劃模型的條件2 確定決策變量uk及每段的允許決策集合Dk(xk)=uk。3 寫出狀態(tài)轉(zhuǎn)移方程如果給定第k段狀態(tài)變量xk的值，則該段的決策變量uk一經(jīng)確定，第k+1

14、段狀態(tài)變量xk+1的值也就完全確定。 xk+1的值隨xk和uk的值的變化而變化的這種對應(yīng)關(guān)系，用xk+1 = Tk(xk, uk) 表示。它表示由k段到k+1段的整體轉(zhuǎn)移規(guī)律，稱為狀態(tài)轉(zhuǎn)移方程。構(gòu)成動態(tài)規(guī)劃模型的條件4 根據(jù)題意，列出指標(biāo)函數(shù)Vk,n 關(guān)系，并要滿足遞推性。正確列出指標(biāo)函數(shù)關(guān)系，必須使它具有三個性質(zhì)：它是定義在全過程和所有后部子過程上的數(shù)量函數(shù)；要滿足遞推關(guān)系。即 Vk,n（xk, uk，xk+1 , ，xn+1）= 對其變元Vk+1,n來說要嚴(yán)格單調(diào)。構(gòu)成動態(tài)規(guī)劃模型的條件常見的指標(biāo)函數(shù)是取各段指標(biāo)和的形式。即其中表示第 j 段的指標(biāo)。它顯然是滿足上述三個性質(zhì)的。所以上式可寫

15、成構(gòu)成動態(tài)規(guī)劃模型的條件當(dāng)初始狀態(tài)給定，過程的策略也確定了時，指標(biāo)函數(shù)也就確定了。因此，指標(biāo)函數(shù)是初始狀態(tài)和策略的函數(shù)。記為Vk,nxk,pk,n(xk)。 故上面遞推關(guān)系又可寫成：構(gòu)成動態(tài)規(guī)劃模型的條件因其子策略pk,n(xk)可看成是由決策uk(xk)和pk+1,n(xk+1)組合而成。即對于最優(yōu)策略的指標(biāo)函數(shù)值，有P*k,n(xk) 表示初始狀態(tài)為xk的后部子過程所有子策略中的最優(yōu)子策略構(gòu)成動態(tài)規(guī)劃模型的條件由上述四個條件（組成部分）得出動態(tài)規(guī)劃的基本方程：動態(tài)規(guī)劃的基本方程 若從xk出發(fā)，有： k =n, n-1, 1動態(tài)規(guī)劃的基本方程于是可得：fk(xk) = 及fn+1(xn+1)

16、 = 0動態(tài)規(guī)劃的基本方程以上是逆序解法的基本方程。其遞推過程從k = n開始，逐段向前推移，一直到求出f1(x1)時，就得到了整個過程的最優(yōu)解，包括最優(yōu)策略和相應(yīng)的最優(yōu)指標(biāo)函數(shù)值。問題舉例例1最短路線問題給出一個線路網(wǎng)絡(luò)， 從A點要鋪設(shè)一條管道到G點，其兩點之間連線上的數(shù)字表示兩點間的距離；要求選擇一條由A到G的鋪管線路，使總距離為最短。AE2D2B2B1C4C3C2C1D3D1E1E3F2F1G336625533432122335386631485768最短路線問題 4 3 7 5 9 7 6 81310 912131618AE2D2B2B1C4C3C2C1D3D1E1E3F2F1G336

17、625533432122335386631485768最短路線問題問題舉例例2 機器負荷分配問題某種機器，可以在高低兩種不同的負荷下進行生產(chǎn)。在高負荷下進行生產(chǎn)時，產(chǎn)品的年產(chǎn)量s1和投入生產(chǎn)的機器數(shù)量u1的關(guān)系為s1 = g (u1)這時，機器的年折損率為a，即如果年初完好機器的數(shù)量為u，到年終時完好的機器就為au, 0a1. 在低負荷下生產(chǎn)時，產(chǎn)品的年產(chǎn)量s2和投入生產(chǎn)的機器數(shù)量u2的關(guān)系為s2= h (u2)相應(yīng)的機器的年折損率為b, 0bk0時以及計算二項式系數(shù) 可以用動態(tài)規(guī)劃技術(shù)來對它求解。把二項式系數(shù)記錄在一張n+1行k+1列的表中，行從0到n 計數(shù)，列從0到k計數(shù)。為了計算C（n,

18、k），逐行填充表格，從行0開始，到行n結(jié)束。每一行（0in）從左向右填充，第一個數(shù)字填1，因為C（n,0）=1。行0直到行k也是以1結(jié)束在表的主對角線上：當(dāng)0ik時，C(i,i)=1。用上述公式計算其他單元格的值，即把前一行前一列那個單元格的值和前一行當(dāng)前列那個單元格的值相加。（帕斯卡三角形）計算二項式系數(shù) 算法Binomial(n,k)/用動態(tài)規(guī)劃算法計算C(n,k)/輸入：一對非負整數(shù)nk0/輸出：C(n,k)的值for i 0 to n dofor j0 to min(i,k) doif j= 0 or j=iCi,j 1else Ci,j Ci-1,j-1+Ci-1,jreturn C

19、n,k計算二項式系數(shù) 該算法的基本操作是加法，所以把A（n,k）記作該算法在計算C(n,k)時所作的加法總次數(shù)。 因為表格的前k+1行構(gòu)成了一個三角形，而余下的n-k行構(gòu)成了一個矩形，將求和表達式A（n,k）分成兩個部分,有：最長公共子序列一個給定序列的子序列是在該序列中刪去若干元素后得到的序列。存在一個嚴(yán)格遞增下標(biāo)序列。例如，序列Z= B，C，D，B是序列X= A，B，C，B，D，A，B的子序列， 相應(yīng)的遞增下標(biāo)序列為2，3，5，7。給定兩個序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時，稱Z是序列X和Y的公共子序列。例如， 若X= A，B，C，B，D，A，B，Y= B，D，C，A，B，A則序列B，C，A是X和Y的一個公共子序列。最長公共子序列問題：給定兩個序列X= x1, x2, , xm和Y= y1, y2, , yn， 找出X和Y的一個最長公共子序列。最長公共子序列蠻力搜索的方法：令A(yù)= a1a2an和B= b1b2bm。例舉A所有的2n個子序列， 對于每一個子序列在(m) 時間內(nèi)來確定它是否也是B的子序列。此方法的時間復(fù)雜性是