動態規劃
動態規劃是本書介紹的五種演算法設計方法中難度最大的一種，它建立在最優原則的基礎上。採用動態規劃方法，可以優雅而高效地解決許多用貪婪演算法或分而治之演算法無法解決的問題。在介紹動態規劃的原理之後，本章將分別考察動態規劃方法在解決揹包問題、圖象壓縮、矩陣乘法鏈、最短路徑、無交叉子集和元件摺疊等方面的應用。
3.1 演算法思想
和貪婪演算法一樣，在動態規劃中，可將乙個問題的解決方案視為一系列決策的結果。不同的是，在貪婪演算法中，每採用一次貪婪準則便做出乙個不可撤回的決策，而在動態規劃中，還要考察每個最優決策序列中是否包含乙個最優子串行。
例3-1 [最短路經] 考察圖1 2 - 2中的有向圖。假設要尋找一條從源節點s= 1到目的節點d= 5的最短路徑，即選擇此路徑所經過的各個節點。第一步可選擇節點2，3或4。
假設選擇了節點3，則此時所要求解的問題變成：選擇一條從3到5的最短路徑。如果3到5的路徑不是最短的，則從1開始經過3和5的路徑也不會是最短的。
例如，若選擇的子路徑（非最短路徑）是3，2，5 (耗費為9 )，則1到5的路徑為1，3，2，5 (耗費為11 )，這比選擇最短子路徑3，4，5而得到的1到5的路徑1，3，4，5 (耗費為9) 耗費更大。
所以在最短路徑問題中，假如在的第一次決策時到達了某個節點v，那麼不管v 是怎樣確定的，此後選擇從v 到d 的路徑時，都必須採用最優策略。
例3-2 [0/1揹包問題] 考察1 3 . 4節的0 / 1揹包問題。如前所述，在該問題中需要決定x1 ..
xn的值。假設按i = 1，2，.，n 的次序來確定xi 的值。
如果置x1 = 0，則問題轉變為相對於其餘物品（即物品2，3，.，n），揹包容量仍為c 的揹包問題。若置x1 = 1，問題就變為關於最大揹包容量為c-w1 的問題。
現設r 為剩餘的揹包容量。
在第一次決策之後，剩下的問題便是考慮揹包容量為r 時的決策。不管x1 是0或是1，[x2 ，.，xn ] 必須是第一次決策之後的乙個最優方案，如果不是，則會有乙個更好的方案[y2，.
，yn ]，因而[x1，y2，.，yn ]是乙個更好的方案。
假設n=3, w=[100,14,10], p=[20,18,15], c= 11 6。若設x1 = 1，則在本次決策之後，可用的揹包容量為r= 116-100=16 。[x2，x3 ]=[0,1] 符合容量限制的條件，所得值為1 5，但因為[x2，x3 ]= [1，0] 同樣符合容量條件且所得值為1 8，因此[x2，x3 ] = [ 0，1] 並非最優策略。
即x= [ 1，0，1] 可改進為x= [ 1，1，0 ]。若設x1 = 0，則對於剩下的兩種物品而言，容量限制條件為11 6。總之，如果子問題的結果[x2，x3 ]不是剩餘情況下的乙個最優解，則[x1，x2，x3 ]也不會是總體的最優解。
例3-3 [航費] 某航線**表為：從亞特蘭大到紐約或芝加哥，或從洛杉磯到亞特蘭大的費用為$ 1 0 0；從芝加哥到紐約票價$ 2 0；而對於路經亞特蘭大的旅客，從亞特蘭大到芝加哥的費用僅為$ 2 0。從洛杉磯到紐約的航線涉及到對中轉機場的選擇。
如果問題狀態的形式為（起點，終點），那麼在選擇從洛杉磯到亞特蘭大後，問題的狀態變為（亞特蘭大，紐約）。從亞特蘭大到紐約的最便宜航線是從亞特蘭大直飛紐約，票價$ 1 0 0。而使用直飛方式時，從洛杉磯到紐約的花費為$ 2 0 0。
不過，從洛杉磯到紐約的最便宜航線為洛杉磯-亞特蘭大-芝加哥-紐約，其總花費為$ 1 4 0（在處理區域性最優路徑亞特蘭大到紐約過程中選擇了最低花費的路徑：亞特蘭大-芝加哥-紐約）。
如果用三維陣列（t a g，起點，終點）表示問題狀態，其中t a g為0表示轉飛， t a g為1表示其他情形，那麼在到達亞特蘭大後，狀態的三維陣列將變為（ 0，亞特蘭大，紐約），它對應的最優路徑是經由芝加哥的那條路徑。
當最優決策序列中包含最優決策子串行時，可建立動態規劃遞迴方程（ d y n a m i c -programming recurrence equation），它可以幫助我們高效地解決問題。
例3-4 [0/1揹包] 在例3 - 2的0 / 1揹包問題中，最優決策序列由最優決策子串行組成。假設f (i,y) 表示例1 5 - 2中剩餘容量為y，剩餘物品為i，i + 1，.，n 時的最優解的值，即：
和利用最優序列由最優子串行構成的結論，可得到f 的遞迴式。f ( 1 ,c) 是初始時揹包問題的最優解。可使用（ 1 5 - 2）式通過遞迴或迭代來求解f ( 1 ,c)。
從f (n, * )開始迭式， f (n, * )由（1 5 - 1）式得出，然後由（ 1 5 - 2）式遞迴計算f (i,*) ( i=n- 1，n- 2，.， 2 )，最後由（ 1 5 - 2）式得出f ( 1 ,c)。
對於例1 5 - 2，若0≤y＜1 0，則f ( 3 ,y) = 0；若y≥1 0，f ( 3 ,y) = 1 5。利用遞迴式（1 5 - 2），可得f (2, y) = 0 ( 0≤y＜10 )；f（2，y）= 1 5（1 0≤y＜1 4）；f（2，y）= 1 8（1 4≤y＜2 4）和f（2，y）= 3 3（y≥2 4）。因此最優解f ( 1 , 11 6 ) = m a x = m a x = m a x = 3 8。
現在計算xi 值，步驟如下：若f ( 1 ,c) =f ( 2 ,c)，則x1 = 0，否則x1 = 1。接下來需從剩餘容量c-w1中尋求最優解，用f (2, c-w1) 表示最優解。
依此類推，可得到所有的xi (i= 值。
在該例中，可得出f ( 2 , 11 6 ) = 3 3≠f ( 1 , 11 6 )，所以x1 = 1。接著利用返回值3 8 -p1=18 計算x2 及x3，此時r = 11 6 -w1 = 1 6，又由f ( 2 , 1 6 ) = 1 8，得f ( 3 , 1 6 ) = 1 4≠f ( 2 , 1 6 )，因此x2 = 1，此時r= 1 6 -w2 = 2，所以f (3,2) =0，即得x3 = 0。
動態規劃方法採用最優原則（ principle of optimality）來建立用於計算最優解的遞迴式。所謂最優原則即不管前面的策略如何，此後的決策必須是基於當前狀態（由上一次決策產生）的最優決策。由於對於有些問題的某些遞迴式來說並不一定能保證最優原則，因此在求解問題時有必要對它進行驗證。
若不能保持最優原則，則不可應用動態規劃方法。在得到最優解的遞迴式之後，需要執行回溯（t r a c e b a c k）以構造最優解。
編寫乙個簡單的遞迴程式來求解動態規劃遞迴方程是一件很誘人的事。然而，正如我們將在下文看到的，如果不努力地去避免重複計算，遞迴程式的複雜性將非常可觀。如果在遞迴程式設計中解決了重複計算問題時，複雜性將急劇下降。
動態規劃遞迴方程也可用迭代方式來求解，這時很自然地避免了重複計算。儘管迭代程式與避免重複計算的遞迴程式有相同的複雜性，但迭代程式不需要附加的遞迴棧空間，因此將比避免重複計算的遞迴程式更快。
3.2 應用
3.2.1 0/1揹包問題
1. 遞迴策略
在例3 - 4中已建立了揹包問題的動態規劃遞迴方程，求解遞迴式（ 1 5 - 2）的乙個很自然的方法便是使用程式1 5 - 1中的遞迴演算法。該模組假設p、w 和n 為輸入，且p 為整型，f(1,c) 返回f ( 1 ,c) 值。
程式15-1 揹包問題的遞迴函式
int f(int i, int y)
程式1 5 - 1的時間複雜性t (n)滿足：t ( 1 ) =a；t（n）≤2t（n- 1）+b（n＞1），其中a、b 為常數。通過求解可得t (n) =o( 2n)。
例3-5 設n= 5，p= [ 6 , 3 , 5 , 4 , 6 ]，w=[2,2,6,5,4] 且c= 1 0 ,求f ( 1 , 1 0 )。為了確定f ( 1 , 1 0 )，呼叫函式f ( 1 , 1 0 )。遞迴呼叫的關係如圖1 5 - 1的樹型結構所示。
每個節點用y值來標記。對於第j層的節點有i=j，因此根節點表示f ( 1 , 1 0 )，而它有左孩子和右孩子，分別對應f ( 2 , 1 0 )和f ( 2 , 8 )。總共執行了2 8次遞迴呼叫。
但我們注意到，其中可能含有重複前面工作的節點，如f ( 3 , 8 )計算過兩次，相同情況的還有f ( 4 , 8 )、f ( 4 , 6 )、f ( 4 , 2 )、f ( 5 , 8 )、f ( 5 , 6 )、f ( 5 , 3 )、f (5,2) 和f ( 5 , 1 )。如果保留以前的計算結果，則可將節點數減至1 9，因為可以丟棄圖中的陰影節點。
正如在例3 - 5中所看到的，程式1 5 - 1做了一些不必要的工作。為了避免f (i,y)的重複計算，必須定義乙個用於保留已被計算出的f (i,y)值的**l，該**的元素是三元組(i,y,f (i,y) )。在計算每乙個f (i,y)之前，應檢查表l中是否已包含乙個三元組(i,y, * )，其中*表示任意值。
如果已包含，則從該表中取出f (i,y)的值，否則，對f (i,y)進行計算並將計算所得的三元組(i,y,f (i,y) )加入表l。l既可以用雜湊（見7 . 4節）的形式儲存，也可用二叉搜尋樹(見11章)的形式儲存。
2. 權為整數的迭代方法
當權為整數時，可設計乙個相當簡單的演算法（見程式1 5 - 2）來求解f ( 1 ,c)。該演算法基於例3 - 4所給出的策略，因此每個f (i,y) 只計算一次。程式1 5 - 2用二維陣列f [ ][ ]來儲存各f 的值。
而回溯函式tr a c e b a c k用於確定由程式1 5 - 2所產生的xi 值。函式k n a p s a c k的複雜性為( n c），而tr a c e b a c k的複雜性為( n )。
未建模動態
3 劉興堂主編.應用自適應控制.西北工業大學出版社,2003年05月第1版.p42 2.6魯棒性概念 定義和有關定理 2.6.1魯棒性概念及分類 在設計控制系統 包括自適應控制系統 時，通常所假設的，如已知的模型階次 相對階降階 線性 無量測雜訊或雜訊的統計特性 時不變等條件，在實際中都有可能得不到...
數學建模線性規劃作業
1 北方化工廠月生產計畫安排 根據經營現狀和目標，合理制定生產計畫並有效組織生產，是乙個企業提高效益的核心，特別是對於乙個化工廠而言，由於其原料品種多，生產工藝複雜，原材料和產成品儲存費用較高，並有一定的危險性，對其生產計畫作出合理安排就顯得尤為重要。現要求對北方化工長的生產計畫作出合理安排。生產概...
數學建模中的線性規劃
它們以1 2 3 b b b 表示。產品i可在a,b任何一種規格裝置上加工。產品ii可在任何規 格的a 裝置上加工，但完成b 工序時，只能在1 b 裝置上加工 產品iii 只能在2 a 與2 b 裝置上加工。已知在各種工具機裝置的單件工時，原材料費，產品銷售 各種裝置有 效臺時以及滿負荷操作時工具機...