《2019-2020年高中信息技術 全國青少年奧林匹克聯(lián)賽教案 動態(tài)規(guī)劃法專題.doc》由會員分享，可在線閱讀，更多相關《2019-2020年高中信息技術 全國青少年奧林匹克聯(lián)賽教案 動態(tài)規(guī)劃法專題.doc（4頁珍藏版）》請在裝配圖網(wǎng)上搜索。

2019-2020年高中信息技術 全國青少年奧林匹克聯(lián)賽教案 動態(tài)規(guī)劃法專題 一、動態(tài)規(guī)劃的定義 在現(xiàn)實生活中，有一類活動的過程，由于它的特殊性，可將過程分成若干個互相聯(lián)系的階段，在它的每一階段都需要作出決策，從而使整個過程達到最好的活動效果。因此各個階段決策的選取不能任意確定，它依賴于當前面臨的狀態(tài)，又影響以后的發(fā)展。當各個階段決策確定后，就組成一個決策序列，因而也就確定了整個過程的一條活動路線。這種把一個問題看作是一個前后關聯(lián)具有鏈狀結構的多階段過程(如圖)就稱為多階段決策過程，這種問題稱為多階段決策問題。 在多階段決策問題中，各個階段采取的決策，一般來說是與時間有關的，決策依賴于當前狀態(tài)，又隨即引起狀態(tài)的轉移，一個決策序列就是在變化的狀態(tài)中產(chǎn)生出來的，故有"動態(tài)"的含義，我們稱這種解決多階段決策最優(yōu)化的過程為動態(tài)規(guī)劃方法。 應指出，動態(tài)規(guī)劃是考察求解多階段決策問題的一種途徑、一種方法，而不是一種特殊算法。不像線性規(guī)劃那樣，具有一個標準的數(shù)學表達式和明確定義的一組規(guī)劃。因此我們在學習時，除了要對基本概念和方法正確理解外，必須具體問題具體分析處理，以豐富的想象力去建立模型，用創(chuàng)造性的技巧去求解。 二、動態(tài)規(guī)劃最優(yōu)化原理 作為整個過程的最優(yōu)策略具有這樣的性質:即無論過去的狀態(tài)和決策如何，對以前的決策所形成的狀態(tài)而言，余下的諸決策必須構成最優(yōu)策略。（無論過程的初始狀態(tài)/初始決策是什么，其余決策活動必須相對于初始決策所產(chǎn)生的狀態(tài)構成一個最優(yōu)決策序列，才可能使整個決策活動構成最優(yōu)決策序列。） 簡單地說，一個整體過程的最優(yōu)策略的子策略一定是最優(yōu)策略。 利用這個原理，可以把多階段決策問題的求解過程看成是一個連續(xù)的逆推過程。由后向前逐步推算。在求解時，各種狀態(tài)前面的狀態(tài)和決策，對后面的子問題，只不過相當于其初始條件而己，不影晌后面過程的最優(yōu)策略。原理的證明可用反證法。在此把它略去。 三、動態(tài)規(guī)劃的求解方法 是先把問題分成多個子問題（一般地每個子問題是互相關聯(lián)和影響的），再依次研究逐個問題的決策。決策就是某個階段的狀態(tài)確定后，從該狀態(tài)演變到下一階段狀態(tài)的選擇。當全體子問題都解決時，整體問題也隨之解決。 用枚舉的方法從所有可能的決策序列中去選取最優(yōu)決策序列可能是較費時的笨拙的方法，但利用最優(yōu)性原理去找出遞推關系，再找最優(yōu)決策序列就可能使得枚舉數(shù)量大大下降，這就是動態(tài)規(guī)劃方法設計算法的主要思路。 四、動態(tài)規(guī)劃問題的經(jīng)典實例 首先，例舉一個典型的且很直觀的多階段決策問題: [例] 下圖表示城市之間的交通路網(wǎng)，線段上的數(shù)字表示費用，單向通行由A->E。試用動態(tài)規(guī)劃的最優(yōu)化原理求出A->E的最省費用。 如圖從A到E共分為4個階段，即第一階段從A到B，第二階段從B到C，第三階段從C到D，第四階段從D到E。除起點A和終點E外，其它各點既是上一階段的終點又是下一階段的起點。例如從A到B的第一階段中，A為起點，終點有B1，B2，B3三個，因而這時走的路線有三個選擇，一是走到B1，一是走到B2，一是走到B3。若選擇B2的決策，B2就是第一階段在我們決策之下的結果，它既是第一階段路線的終點，又是第二階段路線的始點。在第二階段，再從B2點出發(fā)，對于B2點就有一個可供選擇的終點集合(C1，C2，C3)；若選擇由B2走至C2為第二階段的決策，則C2就是第二階段的終點，同時又是第三階段的始點。同理遞推下去，可看到各個階段的決策不同，線路就不同。很明顯，當某階段的起點給定時，它直接影響著后面各階段的行進路線和整個路線的長短，而后面各階段的路線的發(fā)展不受這點以前各階段的影響。故此問題的要求是：在各個階段選取一個恰 當?shù)臎Q策，使由這些決策組成的一個決策序列所決定的一條路線，其總路程最短。如何解決這個問題呢？ 二、用枚舉法 把所有由A->E可能的每一條路線的距離算出來，然后互相比較，找出最短者，相應地得出了最短路線。 三、用動態(tài)規(guī)劃法求解 決策過程： （1）由目標狀態(tài)E向前推，可以分成四個階段，即四個子問題。如上圖所示。 （2）策略：每個階段到E的最省費用為本階段的決策路徑。 （3）D1，D2是第一次輸人的結點。他們到E都只有一種費用，在D1框上面標5，D2框上面標2。目前無法定下，那一個點將在全程最優(yōu)策略的路徑上。第二階段計算中，5，2都應分別參加計算。 （4）C1，C2，C3是第二次輸入結點，他們到D1，D2各有兩種費用。此時應計算C1，C2，C3分別到E的最少費用。 C1的決策路徑是 min{（C1D1），（C1D2）}。計算結果是C1+D1+E，在C1框上面標為8。 同理C2的決策路徑計算結果是C2+D2+E，在C2框上面標為7。 同理C3的決策路徑計算結果是C3+D2+E，在C3框上面標為12。 此時也無法定下第一，二階段的城市那二個將在整體的最優(yōu)決策路徑上。 （5）第三次輸入結點為B1，B2，B3，而決策輸出結點可能為C1，C2，C3。仿前計算可得Bl，B2，B3的決策路徑為如下情況。 Bl:B1C1費用 12+8=20， 路徑:B1+C1+D1+E B2:B2C1費用 6+8=14， 路徑:B2+C1+D1+E B3:B2C2費用 12+7=19， 路徑:B3+C2+D2+E 此時也無法定下第一，二，三階段的城市那三個將在整體的最優(yōu)決策路徑上。 （6）第四次輸入結點為A，決策輸出結點可能為B1，B2，B3。同理可得決策路徑為 A：AB2，費用5+14=19，路徑 A+B2+C1+D1+E。 此時才正式確定每個子問題的結點中，那一個結點將在最優(yōu)費用的路徑上。19將結果顯然這種計算方法，符合最優(yōu)原理。子問題的決策中，只對同一城市（結點）比較優(yōu)劣。而同一階段的城市（結點）的優(yōu)劣要由下一個階段去決定。 四、小結及比較 動態(tài)規(guī)劃的最優(yōu)化原理是“作為整個過程的最優(yōu)策略具有這樣的性質:無論過去的狀態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，余下的諸決策必須構成最優(yōu)策略?！? 與窮舉法相比，動態(tài)規(guī)劃的方法有兩個明顯的優(yōu)點: (1)大大減少了計算量 (2)豐富了計算結果 從上例的求解結果中，我們不僅得到由A點出發(fā)到終點E的最短路線及最短距離，而且還得到了從所有各中間點到終點的最短路線及最短距離，這對許多實際問題來講是很有用的。 動態(tài)規(guī)劃的最優(yōu)化概念是在一定條件下，我到一種途徑，在對各階段的效益經(jīng)過按問題具體性質所確定的運算以后，使得全過程的總效益達到最優(yōu)。 五、應用動態(tài)規(guī)劃要注意 1．階段的劃分是關鍵，必須依據(jù)題意分析，尋求合理的劃分階段(子問題)方法。而每個子問題是一個比原問題簡單得多的優(yōu)化問題。而且每個子問題的求解中，均利用它的一個后部子問題的最優(yōu)化結果，直到最后一個子問題所得最優(yōu)解，它就是原問題的最優(yōu)解。 2．變量太多，同樣會使問題無法求解。 3．最優(yōu)化原理應在子問題求解中體現(xiàn)。有些問題也允許順推。