最新NOIP初賽復習14基本算法思想總結

1、NOIP初賽復習14基本算法思想一個程序往往要包含兩個方面的描述：一是對數據組織的描述，就是數據的類型和數據的組織形式（例如數組），稱作數據結構；一是對程序操作流程的描述，就是程序的操作步驟，也就是所謂算法。正如著名的計算機科學家沃思（Nikiklaus Wirth）提出的公式：數據結構+算法=程序。算法，廣義地講就是解決問題的方法和過程?？梢允褂米匀徽Z言、偽代碼、流程圖等多種不同的方法來描述。如果把一個程序比喻成一個具有生命的人，那么數據結構就是這個人的軀體，而算法則是這個人的靈魂。枚舉枚舉法，又稱窮舉法，或稱為暴力破解法，是一種針對于密碼的破譯方法，即將密碼進行逐個推算直到找出真正的密碼為

2、止?；舅枷耄涸诳赡艿慕饪臻g中窮舉出每一種可能的解，并對每一個可能解進行判斷，從中得到問題的答案。雖然枚舉法本質上屬于搜索策略，但是它與后面講的回溯法或寬度優(yōu)先搜索有所不同?？偟膩碚f，枚舉就是通過列舉所有的可能性進行一一判斷檢查。適用條件：1、可預先確定每個狀態(tài)的元素個數n。2、可預先確定每個狀態(tài)元素a1,a2,an的值域。注意事項：使用枚舉思想解決實際問題，最關鍵的步驟是劃定問題的解空間，并在該解空間中一一枚舉每一個可能的解。這里有兩點需要注意。一是解空間的劃定必須保證覆蓋問題的全部解。如果解空間集合用H表示，問題的解集用h表示，那么只有當時，才能使用枚舉法求解。二是解空間集合及問題的解集一

3、定是離散的集合，也就是說集合中的元素是可列的、有限的。常見類型：枚舉排列、枚舉子集。常見方法：遞歸地枚舉，這種方法往往更為直觀；遞推（循環(huán)）地枚舉，這種方法往往寫起來更為簡潔。主要優(yōu)點：由于枚舉算法一般是現實問題的“直譯”，且是建立在考察大量狀態(tài)、甚至是窮舉所有狀態(tài)的基礎之上的，因此比較直觀，易于理解，其算法的正確性也比較容易證明。主要缺點：枚舉算法的效率取決于枚舉狀態(tài)的數量以及單個狀態(tài)枚舉的代價，因此效率比較低。在某些情況下，我們可以通過利用題目的特點去除相當大的一部分情況的列舉，從而提高枚舉的效率。算法優(yōu)化：1、提取有效信息;2、減少重復計算;3、將原問題化為更小的問題;4、根據問題的性質

4、進行截枝;5、引進其他算法。例：NOIP2016玩具謎題、NOIP2014生活大爆炸版石頭剪刀布等遞推遞推是一種用若干步可重復的簡運算（規(guī)律）來描述復雜問題的方法。給定一個數的序列H0,H1,Hn,若存在整數n0，使當nn0時,可以用等號(或大于號、小于號)將Hn與其前面的某些項Hi(0iCatalan數是比較復雜的遞推關系，尤其在競賽的時候，選手很難在較短的時間里建立起正確的遞推關系。當然，Catalan數類的問題也可以用搜索的方法來完成，但是，搜索的方法與利用遞推關系的方法比較起來，不僅效率低，編程復雜度也陡然提高。5、第二類Stirling數在五類典型的遞推關系中，第二類Stirling

5、是最不為大家所熟悉的。也正因為如此，我們有必要先解釋一下什么是第二類Strling數。定義：n個有區(qū)別的球放到m個相同的盒子中，要求無一空盒，其不同的方案數用S(n,m)表示，稱為第二類Stirling數。下面就讓我們根據定義來推導帶兩個參數的遞推關系第二類Stirling數。解：設有n個不同的球，分別用b1,b2,bn表示。從中取出一個球bn，bn的放法有以下兩種：1、bn獨自占一個盒子；那么剩下的球只能放在m-1個盒子中，方案數為S2(n-1,m-1)；2、bn與別的球共占一個盒子；那么可以事先將b1,b2,bn-1這n-1個球放入m個盒子中，然后再將球bn可以放入其中一個盒子中，方案數為

6、mS2(n-1,m)。綜合以上兩種情況，可以得出第二類Stirling數定理：S2(n,m)=mS2(n-1,m)+S2(n-1,m-1) (n1,m1)邊界條件可以由定義2推導出：S2(n,0)=0；S2(n,1)=1；S2(n,n)=1；S2(n,k)=0(kn)。小結：通過上面對五種典型的遞推關系建立過程的探討，可知對待遞推類的題目，要具體情況具體分析，通過找到某狀態(tài)與其前面狀態(tài)的聯系，建立相應的遞推關系。遞歸一個函數、過程、概念或數學結構，如果在其定義或說明內部又直接或間接地出現有其本身的引用，則稱它們是遞歸的或者是遞歸定義的。在程序設計中，過程或函數直接或者間接調用自己，就被稱為遞歸

7、調用。其中直接調用自己稱為直接遞歸，而將A調用B，B以調用A的遞歸叫做間接遞歸。基本思想：1、遞歸是借助于一個遞歸工作棧來實現。遞歸=遞推+回歸。2、遞推：問題向一極推進, 這一過程叫做遞推。這一過程相當于壓棧。3、回歸：問題逐一解決，最后回到原問題，這一過程叫做回歸。這一過程相當于彈棧。注意事項：1、遞歸就是在過程或函數里調用自身；2、在使用遞歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口。主要優(yōu)點：采用遞歸方法編寫的問題解決程序具有結構清晰，可讀性強等優(yōu)點，且遞歸算法的設計比非遞歸算法的設計往往要容易一些，所以當問題本身是遞歸定義的，或者問題所涉及到的數據結構是遞歸定義的，或者是問題

8、的解決方法是遞歸形式的時候，往往采用遞歸算法來解決。主要缺點：執(zhí)行的效率很低，尤其在邊界條件設置不當的情況下，極有可能陷入死循環(huán)或者內存溢出的窘境。遞歸實現的代價是巨大的?？臻g的耗費，那是因為過程每向前遞推一次，程序將本層的實在變量（值參和變參）、局部變量構成一個“工作記錄”壓入工作棧的棧頂，只有退出該層遞歸時，才將這一工作記錄從棧頂彈出釋放部分空間。由此可以想到，減少每個“工作記錄”的大小便可節(jié)省部分空間。例如某些變參可以轉換為全局變量，某些值參可以省略以及過程內部的精簡。應用分類：1、遞歸的定義問題。樹結構是由遞歸定義的。因此，在解決與樹有關的問題時，常常可以采用遞歸的方法。2、解決搜索問

9、題。因為搜索產生的節(jié)點成樹狀結構，所以可以用遞歸方法解決。這類例子很多，如“N皇后”問題，全排列，哈密頓回路，圖的可著色性等搜索問題。3、實現分治思想。不難發(fā)現，在各種時間復雜度為nlogn排序方法中，大都采用了遞歸的形式。因為無論是分治合并排序，還是堆排序、快速排序，都存在有分治的思想。只要分開處理，就可以采用遞歸。其實進行分治，也是一個建樹的過程。4、用于輸出動態(tài)規(guī)劃的中間過程。動態(tài)規(guī)劃對空間要求較高，若要保存中間過程用于輸出，則可能要增加一倍的空間需求。此時，如果采用遞歸輸出，就完全不需要浪費這寶貴的空間。【例】 給定n（n=1）,用遞歸的方法計算1+2+3+4+.+(n-1)+n。算法

10、分析：本題可以用遞歸方法求解，其原因在于它符合遞歸的三個條件：1、本題是累加問題：當前和=前一次和+當前項，而前一次和的計算方法與其相同，只是數據不同s(n)=s(n-1)+n;2、給定n,所以是有限次的遞歸調用；3、結束條件是當n=1，則s=1。【參考程序】#includeusing namespace std;int fac(int);/遞歸函數int main()int t;cint;/輸入t的值couts=fac(t)endl; /計算1到t的累加和，輸出結果int fac(int n)if (n=1) return 1;return (fac(n-1)+n);/調用下一層遞歸運行程序

11、，當T=5時，輸出結果：S=15，其遞歸調用執(zhí)行過程如下圖：（設T=3）遞歸調用過程，實質上是不斷調用過程或函數的過程，由于遞歸調用一次，所有子程序的變量（局部變量、變參等）、地址在計算機內部都有用特殊的管理方法棧（先進后出）來管理，一旦遞歸調用結束，計算機便開始根據棧中存儲的地址返回各子程序變量的值，并進行相應操作。遞歸遞推適合解決的問題1.問題本身是遞歸定義的，或者問題所涉及到的數據結構是遞歸定義的，或者是問題的解決方法是遞歸形式的2.需要利用分治思想解決的問題3.回溯、深度優(yōu)先搜索4.輸出動態(tài)規(guī)劃的中間過程1.能夠用遞推式計算的數學題2.動態(tài)規(guī)劃（必須使用遞推或記憶化搜索）特點結構清晰、

12、可讀性強目的性強速度較快、比較靈活思路不易想到編碼方式在函數中調用自己迭代（使用for循環(huán)等）替代方法問題的性質不同，改寫的方法也不同。 有的問題可以根據程序本身的特點，使用棧來模擬遞歸調用。 有的問題可以改寫成遞推或迭代算法。在拓撲關系不明顯時，可以采用記憶化搜索。搜索搜索，某種意義上就是對于枚舉算法的一種改進，通過在枚舉的過程中，不斷排除一些不可能達到的情況，從而達到優(yōu)化復雜度的效果。常見方法：1、深度優(yōu)先搜索（DFS）主要思想：從一個頂點沿一條路一直走，如果發(fā)現到不了目標節(jié)點，則返回上一個節(jié)點，沿另一條路一直走到底。總體來說，DFS就是一個一個一直處理到底，發(fā)現無法得到結果之后，逐步返回

13、尋求其它的出路。算法優(yōu)化：1、最優(yōu)化剪枝：求最優(yōu)值時，當前的狀態(tài)無論如何不可能比最優(yōu)值更優(yōu)，則退出，可與展望結合剪枝；2、可行性剪枝：提前判斷該狀態(tài)是否能得到可行解，如不能則退出；3、記憶化搜索：對于已經搜索過的狀態(tài)直接退出；4、改變搜索順序：對于看起來希望更大的決策先進行搜索；5、優(yōu)化搜索策略；6、預處理找到大體搜索翻譯；7、改寫成IDA*算法。2、寬度優(yōu)先搜索（BFS）主要思想：首先訪問起始節(jié)點的所有鄰接點，然后再訪問較遠的區(qū)域，逐步擴大范圍，直到找到了目標節(jié)點。BFS是一個處理不含邊權的圖當中求解最短路徑的一個非常有效的方法。這一算法也是很多重要的圖的算法的原型。Dijkstra單源最短

14、路徑算法和Prim最小生成樹算法都采用了和寬度優(yōu)先搜索類似的思想。注意事項：1、每生成一個子結點，就要提供指向它們父親結點的指針。當解出現時候，通過逆向跟蹤，找到從根結點到目標結點的一條路徑。當然不要求輸出路徑，就沒必要記父親。2、生成的結點要與前面所有已經產生結點比較，以免出現重復結點，浪費時間和空間，還有可能陷入死循環(huán)。3、如果目標結點的深度與“費用”（如：路徑長度）成正比，那么，找到的第一個解即為最優(yōu)解，這時，搜索速度比深度搜索要快些，在求最優(yōu)解時往往采用寬度優(yōu)先搜索；如果結點的“費用”不與深度成正比時，第一次找到的解不一定是最優(yōu)解。4、寬度優(yōu)先搜索的效率還有賴于目標結點所在位置情況，如

15、果目標結點深度處于較深層時，需搜索的結點數基本上以指數增長。算法優(yōu)化：1、判重的優(yōu)化：hash，二叉排序樹；2、雙向廣搜或啟發(fā)式搜索；3、改寫成A*算法；4、二分優(yōu)化。DFSBFS優(yōu)勢1. 比較適合回溯類搜索2. 參數傳遞、狀態(tài)修改和恢復都比較方便3. 自頂向下地處理問題4. 記憶化搜索容易實現5. 能很快到達解答樹的底端1. 解決“最少步數”、“深度最小”問題2. 問題的解靠近解答樹的根結點3. 啟發(fā)式搜索在BFS中更容易實現4. 能立刻停止搜索缺點1. 使用遞歸算法容易導致棧溢出2. 有時不容易輸出方案3. 不易立即結束搜索1. 空間一般比DFS大2. 狀態(tài)重復的排除有時耗時多3、迭代加深

16、搜索深度優(yōu)先搜索的優(yōu)點在于能較高效地逼近解，缺點在于初始遞歸方向錯誤會帶來很嚴重后果；寬度優(yōu)先搜索的優(yōu)點在于能迅速找到答案不算大的解，缺點在于解答案較大時所耗時間與空間都比較大。于是，在綜合以上兩個算法之后，出現了一個折中的方法：迭代加深搜索。主要思想：通過限定下界k，然后允許深度優(yōu)先搜索搜索k層，一旦仍沒有找到有效解，則增大下界。主要優(yōu)點：相對于深度優(yōu)先搜索并沒有大很多的時間開銷，但能部分解決深度優(yōu)先搜索的局限；無需寬度優(yōu)先搜索一般的大空間需求。【例】迷宮問題如下圖所示，給出一個N*M的迷宮圖和一個入口、一個出口。編一個程序，打印一條從迷宮入口到出口的路徑。這里黑色方塊的單元表示走不通（用-

17、1表示），白色方塊的單元表示可以走（用0表示）。只能往上、下、左、右四個方向走。如果無路則輸出“no way.”。入口0-1000000-10000-1000-1-100000-1-1-100-1-100000出口0000000-1-1算法分析：只要輸出一條路徑即可，所以是一個經典的回溯算法問題，本例給出了回溯（深搜）程序和寬搜程序?！旧钏褏⒖汲绦颉?include using namespace std;intn,m,desx,desy,soux,souy,totstep,a51,b51,map5151;bool f;int move(int x, int y,int step)mapxy=

18、step; /走一步，作標記，把步數記下來astep=x; bstep=y;/記路徑 if(x=desx)&(y=desy) f=1;totstep=step; else if(y!=m)&(mapxy+1=0)move(x,y+1,step+1);/向右 if(!f)&(x!=n)&(mapx+1y=0) move(x+1,y,step+1);/往下 if(!f)&(y!=1)&(mapxy-1=0) move(x,y-1,step+1);/往左 if(!f)&(x!=1)&(mapx-1y=0) move(x-1,y,step+1);/往上 int main() int i,j;cinnm

19、;/n行m列的迷宮 for(i=1;i=n;i+) /讀入迷宮，0表示通，-1表示不通for (j=1;jmapij;coutsouxsouy;/入口coutdesxdesy;/出口 f=0; /f=0表示無解；f=1表示找到了一個解move(soux,souy,1); if (f) for(i=1;i=totstep;i+)/輸出直迷宮的路徑coutai,biendl; elsecoutno way.endl;return 0;【寬搜參考程序】#include using namespace std;int u5=0,0,1,0,-1,w5=0,1,0,-1,0;intn,m,i,j,des

20、x,desy,soux,souy,head,tail,x,y,a51,b51,pre51,map5151;bool f;int print(int d) if (pred!=0)print (pred);/遞歸輸出路徑coutad,bdnm;/n行m列的迷宮 for(i=1;i=n;i+) /讀入迷宮，0表示通，-1表示不通for (j=1;jmapij;coutsouxsouy;/入口coutdesxdesy;/出口 head=0;tail=1; f=0;mapsouxsouy=-1;atail=soux; btail=souy;pretail=0; while(head!=tail) /隊

21、列不為空head+; for(i=1;i0)&(x0)&(y=m)&(mapxy=0) /本方向上可以走tail+;atail=x; btail=y; pretail=head;mapxy=-1;if (x=desx)&(y=desy) /擴展出的結點為目標結點f=1;print(tail);break; if(f) break; if (!f)coutno way.endl; return 0;輸入1：輸出1：輸入2：輸出2：8 5-1 -1 -1 -1 -10 0 0 0 -1-1 -1 -1 0 -1-1 0 0 0 -1-1 0 0 -1 -1-1 0 0 0 -1-1 -1 -1 0

22、 -1-1 0 0 0 -12 18 42,12,22,32,43,44,44,35,36,38 5-1 -1 -1 -1 -10 0 0 0 -1-1 -1 -1 0 -1-1 0 0 0 -1-1 0 0 -1 -1-1 0 0 0 -1-1 -1 -1 -1 -1-1 0 0 0 -12 18 4no way.分治基本思想：將一個較大規(guī)模的問題分成多個（一般是2個）較小規(guī)模的互相獨立且與原問題相同或相似的子問題，再把子問題分成更小的子問題直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并。當我們將問題分解成兩個較小問題求解時的分治方法稱之為二分法。適用條件：1、該問題的規(guī)?？s

23、小到一定的程度就可以容易地解決；2、該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結構性質；3、利用該問題分解出的子問題的解可以合并為該問題的解；4、該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子子問題。遞歸與分治的算法思想往往是相伴而生的，它們在各類算法中使用非常頻繁，應用遞歸和分治的算法思想有時可以設計出代碼簡潔且比較高效的算法來。解題步驟：1、分解，將要解決的問題劃分成若干規(guī)模較小的同類問題；2、求解，當子問題劃分得足夠小時，用較簡單的方法解決；3、合并，按原問題的要求，將子問題的解逐層合并構成原問題的解。應用分類：二分搜索；大整數乘法；Strassen

24、矩陣乘法；棋盤覆蓋；合并排序；快速排序；線性時間選擇；最接近點對問題；循環(huán)賽日程表；漢諾塔等。例：NOIP2012借教室；NOIP2013轉圈游戲等【例】用遞歸算法實現二分查找即：有n個已經從小到大排序好的數據，輸入一個數m，用二分查找算法，判斷它是否在這n個數中。#includeusing namespace std;int jc(int,int);int n,a1000,m;int main() intx,y,i;cinn; x=1;y=n; for(i=1;iai;cinm; /輸入要查找的數jc(x,y);/遞歸過程coutendl;int jc(int x,int y) /遞歸過程

25、int k;k=(x+y)/2;/取中間位置點 if(ak=m) coutthennum in ky)coutno findendl; /找不到該數else if (akm) jc(x,k-1);/在前半中查找 貪心基本思想：貪心，又稱貪婪算法。指的是在對問題求解過程中，總是做出目前來看最優(yōu)的選擇，也就是說貪心算法不會考慮全局最優(yōu)解，而只會不斷考慮局部最優(yōu)解。是一種對某些求最優(yōu)解問題的更簡單、更迅速的設計技術。往往可以以較低的代碼復雜度與時間復雜度而得到較優(yōu)的結果，對于求解近似值的作用很大。貪心算法沒有固定的算法框架，算法設計的關鍵是貪心策略的選擇。必須注意的是，貪心算法不是對所有問題都能得到

26、整體最優(yōu)解，選擇的貪心策略必須具備無后效性，即某個狀態(tài)以后的過程不會影響以前的狀態(tài)，只與當前狀態(tài)有關。當存在一些題目的正解想不出來，并且一個貪心原則又效果不好的情況下，可以采取多個貪心原則同時用，并取最優(yōu)的方案來解決。但對于相當一部分需要求解最優(yōu)值的問題，實際上我們會發(fā)現我們通?？梢圆捎脛討B(tài)規(guī)劃或者網絡流的方法取代貪心算法。適用條件：1、可通過局部的貪心選擇來達到問題的全局最優(yōu)解。運用貪心策略解題，一般來說需要一步步的進行多次的貪心選擇。在經過一次貪心選擇之后，原問題將變成一個相似的，但規(guī)模更小的問題，而后的每一步都是當前看似最佳的選擇，且每一個選擇都僅做一次。2、原問題的最優(yōu)解包含子問題的最

27、優(yōu)解，即問題具有最優(yōu)子結構的性質。在下面示例的背包問題中，第一次選擇單位重量價值最大的貨物，它是第一個子問題的最優(yōu)解，第二次選擇剩下的貨物中單位重量價值最大的貨物，同樣是第二個子問題的最優(yōu)解，依次類推。3、其次，如何選擇一個貪心標準？正確的貪心標準可以得到問題的最優(yōu)解，在確定采用貪心策略解決問題時，不能隨意的判斷貪心標準是否正確，尤其不要被表面上看似正確的貪心標準所迷惑。在得出貪心標準之后應給予嚴格的數學證明。解題步驟：1、建立數學模型來描述問題；2、把求解的問題分成若干個子問題；3、對每一子問題求解，得到子問題的局部最優(yōu)解；4、把子問題的解局部最優(yōu)解合成原來解問題的一個解。例：NOIP201

28、2國王游戲；NOIP2013積木大賽；NOIP2015跳石頭等?！纠坎糠直嘲鼏栴}給定一個最大載重量為M的卡車和N種食品，有食鹽，白糖，大米等。已知第i種食品的最多擁有Wi公斤，其商品價值為Vi元/公斤，編程確定一個裝貨方案，使得裝入卡車中的所有物品總價值最大。算法分析：因為每一個物品都可以分割成單位塊，單位塊的利益越大顯然總收益越大，所以它局部最優(yōu)滿足全局最優(yōu)，可以用貪心法解答，方法如下：先將單位塊收益按從大到小進行排列，然后用循環(huán)從單位塊收益最大的取起，直到不能取為止便得到了最優(yōu)解。因此我們非常容易設計出如下算法：問題初始化； /讀入數據按Vi從大到小將商品排序；i=1;do if (m=

29、0) break; /如果卡車滿載則跳出循環(huán) m=m-wi; if (m=0)/將第i種商品全部裝入卡車 else 將(m+wi) 重量的物品i裝入卡車; i=i+1; /選擇下一種商品while (m0&i=n);在解決上述問題的過程中，首先根據題設條件，找到了貪心選擇標準(Vi)，并依據這個標準直接逐步去求最優(yōu)解，這種解題策略被稱為貪心法?；厮莼舅枷耄涸诎瑔栴}的所有解的解空間樹中，按照深度優(yōu)先搜索的策略，從根結點出發(fā)深度探索解空間樹。當探索到某一結點時，要先判斷該結點是否包含問題的解，如果包含，就從該結點出發(fā)繼續(xù)探索下去；如果該結點不包含問題的解，那就說明以該結點為根結點的子樹一定不包

30、含問題的最終解，因此要跳過對以該結點為根的子樹的系統(tǒng)探索，逐層向其祖先結點回溯。這個過程叫做解空間樹的“剪枝”操作。如果應用回溯法求解問題的所有解，要回溯到解空間樹的樹根，這樣根結點的所有子樹都被探索到才結束。如果只要求解問題的一個解，那么在探索解空間樹時，只要搜索到問題的一個解就可以結束了。【例】素數環(huán):從1到20這20個數擺成一個環(huán)，要求相鄰的兩個數的和是一個素數。算法分析：非常明顯，這是一道回溯的題目。從1開始，每個空位有20種可能，只要填進去的數合法：與前面的數不相同；與左邊相鄰的數的和是一個素數。第20個數還要判斷和第1個數的和是否素數。算法流程：1、數據初始化；2、遞歸填數：判斷第

31、i個數填入是否合法A、如果合法：填數；判斷是否到達目標（20個已填完）：是，打印結果；不是，遞歸填下一個；B、如果不合法：選擇下一種可能?！緟⒖汲绦颉?include#include#include#includeusing namespace std;bool b21=0;int total=0,a21=0;int search(int);/回溯過程int print(); /輸出方案bool pd(int,int);/判斷素數int main() search(1);couttotalendl;/輸出總方案數int search(int t) int i; for(i=1;i=20;i+)

32、/有20個數可選 if(pd(at-1,i)&(!bi)/判斷與前一個數是否構成素數及該數是否可用 at=i;bi=1; if(t=20) if (pd(a20,a1) print();else search(t+1);bi=0; int print() total+;couttotal; for (intj=1;j=20;j+)coutaj ;coutendl; bool pd(int x,int y) intk=2,i=x+y; while(ksqrt(i) return 1; elsereturn 0;動態(tài)規(guī)劃基本思想：在多階段決策的問題中，各個階段采取的決策，一般來說是與時間或空間有關

33、的。決策依賴于當前狀態(tài)，又隨即引起狀態(tài)的轉移，一個決策序列就是在變化的狀態(tài)中產生出來，故有“動態(tài)”的含義，我們稱這種解決多階段決策最優(yōu)化的過程為動態(tài)規(guī)劃方法?；靖拍睿弘A段：把所求問題的過程按照時間或空間恰當地分成若干個相互聯系的階段。狀態(tài)：表示每個階段的客觀狀態(tài)，它既是某階段的出發(fā)位置，又是前一階段的終點。無后效性：如果給定某一階段的狀態(tài)，則在這一階段以后過程的發(fā)展不受這階段以前各段狀態(tài)的影響，所以各階段確定時，整個過程也就確定了。決策：一個階段的狀態(tài)給定以后，從該狀態(tài)演變到下一階段狀態(tài)的一種選擇(行動)。策略：由每個階段的決策組成的序列。最優(yōu)性原理：把一個大問題劃分成多個子問題，對于整個問

34、題必須最優(yōu)的情況時，問題也必須最優(yōu)，即問題具備最優(yōu)子結構的性質。適用條件：1、最優(yōu)子結構。如果問題的一個最優(yōu)解中包含了子問題的最優(yōu)解，則該問題具有最優(yōu)子結構。也稱最優(yōu)化原理。最優(yōu)子結構也可以理解為“整體最優(yōu)則局部最優(yōu)”。反之不一定成立。2、重疊子問題。在解決整個問題時，要先解決其子問題，要解決這些子問題，又要先解決他們的子子問題 。而這些子子問題又不是相互獨立的，有很多是重復的，這些重復的子子問題稱為重疊子問題。動態(tài)規(guī)劃算法正是利用了這種子問題的重疊性質，對每一個子問題只解一次，而后將其解保存在一個表中，以后再遇到這些相同問題時直接查表就可以，而不需要再重復計算，每次查表的時間為常數。3、無后

35、效性原則。已經求得的狀態(tài)，不受未求狀態(tài)的影響。解題步驟：1、判斷問題是否具有最優(yōu)子結構性質，若不具備，則不能用動態(tài)規(guī)劃；2、把問題分成若干個子問題(分階段)；3、建立狀態(tài)轉移方程(遞推公式)；4、找出邊界條件；5、設定初始值；6、遞推求解。狀態(tài)轉移方程的構造是動態(tài)規(guī)劃過程中最重要的一步，也是最難的一步。對于大多數的動態(tài)規(guī)劃，尋找狀態(tài)轉移方程有一條十分高效的通道，就是尋找變化中的不變量（已經求得的值）。例：背包型動態(tài)規(guī)劃：POJ1014,1068；序列型動態(tài)規(guī)劃：POJ 1044,1576,3027；區(qū)間型動態(tài)規(guī)劃：POJ 1048,1154,1166；棋盤性動態(tài)規(guī)劃：POJ 1010,1169

36、,1219,1220；劃分型動態(tài)規(guī)劃：POJ 1017,1039,1040；樹型動態(tài)規(guī)劃：POJ 1163,1380等【例1】最短路徑問題下圖給出了一個地圖，地圖中的每個頂點代表一個城市，兩個城市間的一條連線代表道路，連線上的數值代表道路的長度?，F在想從城市A到達城市E，怎樣走路程最短？最短路程的長度是多少？算法分析：把A到E的全過程分成四個階段，用K表示階段變量，第1階段有一個初始狀態(tài)A，有兩條可供選擇的支路A-B1、A-B2；第2階段有兩個初始狀態(tài)B1、B2，B1有三條可供選擇的支路，B2有兩條可供選擇的支路。用DK（XI，X+1J）表示在第K階段由初始狀態(tài)XI到下階段的初始狀態(tài)X+1J的

37、路徑距離，FK（XI）表示從第K階段的XI到終點E的最短距離，利用倒推的方法，求解A到E的最短距離。具體計算過程如下：S1： K = 4 有F4（D1）= 3，F4（D2）= 4，F4（D3）= 3；S2： K = 3 有F3（C1）= MIN D3（C1，D1）+ F4（D1），D3（C1，D2）+ F4（D2） = MIN 5+3，6+4 = 8F3（C2）= D3（C2，D1）+ F4（D1）= 5+3 = 8F3（C3）= D3（C3，D3）+ F4（D3）= 8+3 = 11F3（C4）= D3（C4，D3）+ F4（D3）= 3+3 = 6S3： K = 2 有F2（B1）= MI

38、N D2（B1，C1）+ F3（C1），D2（B1，C2）+ F3（C2），D2（B1，C3）+ F3(C3) = MIN 1+8,6+8,3+11 = 9F2（B2）= MIN D2（B2，C2）+ F3（C2），D2（B2，C4）+ F3（C4） = MIN 8+8，4+6 = 10S4： K = 1 有F1（A）= MIN D1（A，B1）+ F2（B1），D1（A，B2）+ F2（B2） = MIN 5+9，3+10 = 13因此由A點到E點的全過程最短路徑為AB2C4D3E；最短路程長度為13。從以上過程可以看出，每個階段中，都求出本階段的各個初始狀態(tài)到終點E的最短距離，當逆序倒推到過程起點A時，便得到了全過程的最短路徑和最短距離。在上例的多階段決策問題中，各個階段采取的決策，一般來說是與階段有關的，決策依賴于當前狀態(tài)，又隨即引起狀態(tài)的轉移，一個決策序列就是在變化的狀態(tài)