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

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