歡迎來到裝配圖網(wǎng)! | 幫助中心 裝配圖網(wǎng)zhuangpeitu.com!
裝配圖網(wǎng)
ImageVerifierCode 換一換
首頁 裝配圖網(wǎng) > 資源分類 > DOC文檔下載  

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

  • 資源ID:105095359       資源大小:47.52KB        全文頁數(shù):4頁
  • 資源格式: DOC        下載積分:9.9積分
快捷下載 游客一鍵下載
會員登錄下載
微信登錄下載
三方登錄下載: 微信開放平臺登錄 支付寶登錄   QQ登錄   微博登錄  
二維碼
微信掃一掃登錄
下載資源需要9.9積分
郵箱/手機(jī):
溫馨提示:
用戶名和密碼都是您填寫的郵箱或者手機(jī)號,方便查詢和重復(fù)下載(系統(tǒng)自動生成)
支付方式: 支付寶    微信支付   
驗(yàn)證碼:   換一換

 
賬號:
密碼:
驗(yàn)證碼:   換一換
  忘記密碼?
    
友情提示
2、PDF文件下載后,可能會被瀏覽器默認(rèn)打開,此種情況可以點(diǎn)擊瀏覽器菜單,保存網(wǎng)頁到桌面,就可以正常下載了。
3、本站不支持迅雷下載,請使用電腦自帶的IE瀏覽器,或者360瀏覽器、谷歌瀏覽器下載即可。
4、本站資源下載后的文檔和圖紙-無水印,預(yù)覽文檔經(jīng)過壓縮,下載后原文更清晰。
5、試題試卷類文檔,如果標(biāo)題沒有明確說明有答案則都視為沒有答案,請知曉。

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)。有些問題也允許順推。

注意事項(xiàng)

本文(2022年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 動態(tài)規(guī)劃法專題)為本站會員(xt****7)主動上傳,裝配圖網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對上載內(nèi)容本身不做任何修改或編輯。 若此文所含內(nèi)容侵犯了您的版權(quán)或隱私,請立即通知裝配圖網(wǎng)(點(diǎn)擊聯(lián)系客服),我們立即給予刪除!

溫馨提示:如果因?yàn)榫W(wǎng)速或其他原因下載失敗請重新下載,重復(fù)下載不扣分。




關(guān)于我們 - 網(wǎng)站聲明 - 網(wǎng)站地圖 - 資源地圖 - 友情鏈接 - 網(wǎng)站客服 - 聯(lián)系我們

copyright@ 2023-2025  zhuangpeitu.com 裝配圖網(wǎng)版權(quán)所有   聯(lián)系電話:18123376007

備案號:ICP2024067431-1 川公網(wǎng)安備51140202000466號


本站為文檔C2C交易模式,即用戶上傳的文檔直接被用戶下載,本站只是中間服務(wù)平臺,本站所有文檔下載所得的收益歸上傳人(含作者)所有。裝配圖網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對上載內(nèi)容本身不做任何修改或編輯。若文檔所含內(nèi)容侵犯了您的版權(quán)或隱私,請立即通知裝配圖網(wǎng),我們立即給予刪除!