我們先來看乙個簡單的多階段決策問題。
現有一張地圖，各結點代表城市，兩結點間連線代表道路，線上數字表示城市間的距離。如圖1所示，試找出從結點1到結點10的最短路徑。
第一階段第二階段第三階段第四階段第五階段
圖1本問題的解決可採用一般的窮舉法，即把從結點1至結點10的所有道路列舉出來，計算其長度，再進行比較，找出最小的一條。雖然問題能解決，但採用這種方法，當結點數增加，其運算量將成指數級增長，故而效率是很低的。
我們可以用深度優先搜尋法來解決此問題，該問題的遞迴式為
其中是與v相鄰的節點的集合，w(v,u)表示從v到u的邊的長度。
具體演算法如下：
int mindistance(v)
}}}開始時標記所有的頂點未訪問過，mindistance(a)就是從a到e的最短距離。
這個程式的效率如何呢？我們可以看到，每次除了已經訪問過的城市外，其他城市都要訪問，所以時間複雜度為o(n!)，這是乙個「指數級」的演算法，那麼，還有沒有更好的演算法呢？
分析圖1可知，各結點的排列特徵：
(1) 可將各結點分為5個階段；
(2) 每個階段上的結點只跟相鄰階段的結點相連，不會出現跨階段或同階段結點相連的情況，如不會出現結點1與結點4連、結點4與結點5連的情況。
(3) 除起點1和終點10外，其它各階段的結點既是上一階段的終點，又是下一階段的起點。例如第三階段的結點4、5、6，它即是上一階段結點2、3中某結點的終點，又是下一階段結點7、8、9中某結點的起點。
根據如上特徵，若對於第三階段的結點5，選擇1-2-5和1-3-5這兩條路徑，後者的費用要小於前者。那麼考慮一下，假設在所求的結點1到結點10最短路徑中要經過結點5，那我們在結點1到結點5之間會取那條路徑呢？顯然，無論從結點5出發以後的走法如何，前面選擇1-3-5這條路都總是會優於1-2-5的。
也就是說，當某階段結點一定時，後面各階段路線的發展不受這點以前各階段的影響。反之，到該點的最優決策也不受該點以後的發展影響。
由此，我們可以把原題所求分割成幾個小問題，從階段1開始，往後依次求出結點1到階段2、3、4、5各結點的最短距離，最終得出答案。在計算過程中，到某階段上一結點的決策，只依賴於上一階段的計算結果，與其它無關。例如，已求得從結點1到結點5的最優值是6，到結點6的最優值是5，那麼要求到下一階段的結點8的最優值，只須比較min即可。
這樣，運用動態規劃思想大大節省了計算量。可以看出，動態規劃是解決此類多階段決策問題的一種有效方法。
演算法如下：
void short_path()
輸出f1[a];
}一、動態規劃
1、什麼是動態規劃
動態規劃：與分治法相似，把問題分解按層次分成子問題，直到可以直接求解的子問題，然後一級一級地向上求解。
與分治法的出別在於：動態規劃適用有許多重複子問題出現的問題，它保留已求出問題的解。
例如，計算矩陣連乘積。
問題：（1）矩陣相乘的定義
（2）設矩陣的階分別為
如按計算需要的計算次數為：
50*5*100+50*100*10=75000。
如按計算需要的計算次數為：
50*5*10+5*100*10=7500。
（3）n個矩陣連乘時，怎樣規劃它們的乘積次序，使得所有的乘法次數最少
2、動態規劃中的主要概念，名詞術語
1) 階段：把問題分成幾個相互聯絡的有順序的幾個環節，這些環節即稱為階段。是對整個過程的自然劃分。通常根據時間順序或空間特徵來劃分階段，以便按階段的次序解優化問題。
2) 狀態：某一階段的出發位置稱為狀態。通常乙個階段包含若干狀態。如圖1中，階段3就有三個狀態結點4、5、6。
3) 決策：從某階段的乙個狀態演變到下乙個階段某狀態的選擇。
4) 策略：由開始到終點的全過程中，由每段決策組成的決策序列稱為全過程策略，簡稱策略。
5) 狀態轉移方程：前一階段的終點就是後一階段的起點，前一階段的決策選擇匯出了後一階段的狀態，這種關係描述了由k階段到k+1階段狀態的演變規律，稱為狀態轉移方程。
6) 目標函式與最優化概念：目標函式是衡量多階段決策過程優劣的準則。最優化概念是在一定條件下找到乙個途徑，經過按題目具體性質所確定的運算以後，使全過程的總效益達到最優。
3、運用動態規劃需符合的條件
1）、最優化原理
最優化原理：乙個最優化策略具有這樣的性質，不論過去狀態和決策如何，對前面的決策所形成的狀態而言，餘下的諸決策必須構成最優策略。簡而言之，乙個最優化策略的子策略總是最優的。
圖2 如圖2中，若路線i和j是a到c的最優路徑，則根據最優化原理，路線j必是從b到c的最優路線。這可用反證法證明：假設有另一路徑j』是b到c的最優路徑，則a到c的路線取i和j』比i和j更優，這與原名題矛盾。
從而證明j』必是b到c的最優路徑。
最優化原理是動態規劃的基礎，任何問題，如果失去了最優化原理的支援，就不可能用動態規劃方法計算。
2）、無後效性
「過去的步驟只能通過當前狀態影響未來的發展，當前的狀態是歷史的總結」。這條特徵說明動態規劃只適用於解決當前決策與過去狀態無關的問題。狀態，出現在策略任何乙個位置，它的地位相同，都可實施同樣策略，這就是無後效性的內涵。
由上可知，最優化原理，無後效性，是動態規劃必須符合的兩個條件。
4、動態規劃的基本思路
對於一道題，怎樣具體運用動態規劃方法呢？
1) 首先，分析題意，考察此題是否滿足最優化原理與無後效性兩個條件。
2) 接著，確定題中的階段，狀態，及約束條件。
3) 推導出各階段狀態間的函式基本方程，進行計算。
具體求解則有多種方法。
1) 前向與後向動態規劃法：所謂前向與後向，指的是從起點出發，層層遞推，直到終點，或從終點出發，逆向求解。這兩種方法本質上是一樣的，具體解題時，可根據實際情況來選用。
2) 具有隱含階段的問題（即階段不明顯）：動態規劃的乙個重要環節是階段劃分，可有些題目無明顯階段，但也符合最優化原理。
二、舉例
1、矩陣連乘
在科學計算中經常要計算矩陣的乘積。矩陣a和b可乘的條件是矩陣a的列數等於矩陣b的行數。若a是乙個p×q的矩陣，b是乙個q×r的矩陣，則其乘積c=ab是乙個p×r的矩陣。
其標準計算公式為：
由該公式知計算c=ab總共需要p*q*r次的數乘。
現在的問題是，給定n個矩陣。其中ai與ai+1是可乘的，i=1,2,…,n-1。要求計算出這n個矩陣的連乘積a1a2…an。
由於矩陣乘法滿足結合律，故連乘積的計算可以有許多不同的計算次序。這種計算次序可以用加括號的方式來確定。若乙個矩陣連乘積的計算次序已完全確定，也就是說該連乘積已完全加括號，則我們可以通過反覆呼叫兩個矩陣相乘的標準演算法計算出矩陣連乘積。
例如，矩陣連乘積a1a2a3 a4可以有以下5種不同的完全加括號方式：
(a1(a2(a3a4)))，
(a1((a2a3)a4)),
((a1a2)(a3a4)),
((a1(a2a3))a4),
(((a1a2)a3)a4)。
每一種完全加括號方式對應於一種矩陣連乘積的計算次序，而這種計算次序與計算矩陣連乘積的計算量有著密切的關係。
為了說明在計算矩陣連乘積時加括號方式對整個計算量的影響，我們來看乙個計算3個矩陣的連乘積的例子。設這3個矩陣的維數分別為10×100，100×5和5×50。若按第一種加括號方式((a1a2)a3)來計算，總共需要10×100×5+10×5×50=7500次的數乘。
若按第二種加括號方式(a1(a2a3))來計算，則需要的數乘次數為100×5×50+10×100×50=75000。第二種加括號方式的計算量是第一種加括號方式的計算量的10倍。由此可見，在計算矩陣連乘積時，加括號方式，即計算次序對計算量有很大影響。
於是，人們自然會提出矩陣連乘積的最優計算次序問題，即對於給定的相繼n個矩陣(其中ai的維數為pi-1×pi ，i=1,2,…,n)，如何確定計算矩陣連乘積a1a2…an的乙個計算次序(完全加括號方式)，使得依此次序計算矩陣連乘積需要的數乘次數最少。
下面我們來考慮用動態規劃法解矩陣連乘積的最優計算次序問題。此問題是動態規劃的典型應用之一。
1).分析最優解的結構
首先，為方便起見，將矩陣連乘積aiai+1…aj簡記為ai…j。我們來看計算a1…n的乙個最優次序。設這個計算次序在矩陣ak和ak+1之間將矩陣鏈斷開，1<=k這個問題的乙個關鍵特徵是：
計算a1…n的乙個最優次序所包含的計算a1…k的次序也是最優的。事實上，若有乙個計算a1…k的次序需要的計算量更少，則用此次序替換原來計算a1…k的次序，得到的計算a1…n的次序需要的計算量將比最優次序所需計算量更少，這是乙個矛盾。同理可知，計算a1…n的乙個最優次序所包含的計算矩陣子鏈ak+1…n的次序也是最優的。
根據該問題的指標函式的特徵也可以知道該問題滿足最優化原理。另外，該問題顯然滿足無後向性，因為前面的矩陣鏈的計算方法和後面的矩陣鏈的計算方法無關。
第4講相似
一 知識梳理 1.比例線段的有關概念 b d叫後項，d叫第四比例項，如果b c，那麼b叫做a d的比例中項.把線段ab分成兩條線段ac和bc，使ac2 ab bc，叫做把線段ab 分割，c叫做線段ab的 分割點.2.比例性質 3.平行線分線段成比例定理 定理 三條平行線截兩條直線，所得的對應線段成比...
第4講遺傳規律
遺傳規律的實質 例1.某植物紅花和白花這對相對性狀同時受多對等位基因控制 如a a b b c c 當個體的基因型中每對等位基因都至少含有乙個顯性基因時 即a b c 才開紅花，否則開白花。現有甲 乙 丙 丁4個純合白花品系，相互之間進行雜交，雜交組合 後代表現型及其比例如下 根據雜交結果回答問題 ...
第3章動態規劃
動態規劃是本書介紹的五種演算法設計方法中難度最大的一種，它建立在最優原則的基礎上。採用動態規劃方法，可以優雅而高效地解決許多用貪婪演算法或分而治之演算法無法解決的問題。在介紹動態規劃的原理之後，本章將分別考察動態規劃方法在解決揹包問題 圖象壓縮 矩陣乘法鏈 最短路徑 無交叉子集和元件摺疊等方面的應用...