2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 動(dòng)態(tài)規(guī)劃法專題.doc

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

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