2023年全國碩士研究生考試考研英語一試題真題(含答案詳解+作文范文)_第1頁
已閱讀1頁,還剩48頁未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1、動(dòng)態(tài)規(guī)劃(一)、動(dòng)態(tài)規(guī)劃的基本思想:動(dòng)態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問題。在這類問題中,可能會(huì)有許多可行解。每一個(gè)解都對應(yīng)于一個(gè)值,我們希望找到具有最優(yōu)值的解。動(dòng)態(tài)規(guī)劃算法與分治法類似,其基本思想也是將待求解問題分解成若干個(gè)子問題,先求解子問題,然后從這些子問題的解得到原問題的解。與分治法不同的是,適合于用動(dòng)態(tài)規(guī)劃求解的問題,經(jīng)分解得到子問題往往不是互相獨(dú)立的。若用分治法來解這類問題,則分解得到的子問題數(shù)目太多,有些子問題被重

2、復(fù)計(jì)算了很多次。如果我們能夠保存已解決的子問題的答案,而在需要時(shí)再找出已求得的答案,這樣就可以避免大量的重復(fù)計(jì)算,節(jié)省時(shí)間。我們可以用一個(gè)表來記錄所有已解的子問題的答案。不管該子問題以后是否被用到,只要它被計(jì)算過,就將其結(jié)果填入表中。這就是動(dòng)態(tài)規(guī)劃法的基本思路。具體的動(dòng)態(tài)規(guī)劃算法多種多樣,但它們具有相同的填表格式。二、設(shè)計(jì)動(dòng)態(tài)規(guī)劃法的步驟:1、找出最優(yōu)解的性質(zhì),并刻畫其結(jié)構(gòu)特征;2、遞歸地定義最優(yōu)值(寫出動(dòng)態(tài)規(guī)劃方程);3、以自底向上的

3、方式計(jì)算出最優(yōu)值;4、根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息,構(gòu)造一個(gè)最優(yōu)解。步驟13是動(dòng)態(tài)規(guī)劃算法的基本步驟。在只需要求出最優(yōu)值的情形,步驟4可以省略,步驟3中記錄的信息也較少;若需要求出問題的一個(gè)最優(yōu)解,則必須執(zhí)行步驟4,步驟3中記錄的信息必須足夠多以便構(gòu)造最優(yōu)解。三、動(dòng)態(tài)規(guī)劃問題的特征:動(dòng)態(tài)規(guī)劃算法的有效性依賴于問題本身所具有的兩個(gè)重要性質(zhì):最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題重疊性質(zhì)。1、最優(yōu)子結(jié)構(gòu):當(dāng)問題的最優(yōu)解包含了其子問題的最優(yōu)解時(shí),稱該問題具有最

4、優(yōu)子結(jié)構(gòu)性質(zhì)。2、重疊子問題:在用遞歸算法自頂向下解問題時(shí),每次產(chǎn)生的子問題并不總是新問題,有些子問題被反復(fù)計(jì)算多次。動(dòng)態(tài)規(guī)劃算法正是利用了這種子問題的重疊性質(zhì),對每一個(gè)子問題只解一次,而后將其解保存在一個(gè)表格中,在以后盡可能多地利用這些子問題的解。(二)、動(dòng)態(tài)規(guī)劃算法的基本步驟優(yōu)指標(biāo)12.輸出t但是,實(shí)際應(yīng)用當(dāng)中經(jīng)常不顯式地按照上面步驟設(shè)計(jì)動(dòng)態(tài)規(guī)劃,而是按以下幾個(gè)步驟進(jìn)行:2.分析最優(yōu)解的性質(zhì),并刻劃其結(jié)構(gòu)特征。3.遞歸地定義最優(yōu)值。

5、4.以自底向上的方式或自頂向下的記憶化方法(備忘錄法)計(jì)算出最優(yōu)值。5.根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息,構(gòu)造一個(gè)最優(yōu)解。步驟(1)(3)是動(dòng)態(tài)規(guī)劃算法的基本步驟。在只需要求出最優(yōu)值的情形,步驟(4)可以省略,若需要求出問題的一個(gè)最優(yōu)解,則必須執(zhí)行步驟(4)。此時(shí),在步驟(3)中計(jì)算最優(yōu)值時(shí),通常需記錄更多的信息,以便在步驟(4)中,根據(jù)所記錄的信息,快速地構(gòu)造出一個(gè)最優(yōu)解。(三)、動(dòng)態(tài)規(guī)劃概述1.基本思想:將問題分解為若干小問題,解子問題,

6、然后從子問題得到原問題的解。2.特點(diǎn):將問題分解為子問題,這些子問題往往不相互獨(dú)立。(如果可以用分治法求解,分解的子問題太多,因此,用分治法時(shí)間代價(jià)太高,消耗指數(shù)時(shí)間)3.且某些子問題可能被重復(fù)多次計(jì)算,因此將計(jì)算過的子問題的結(jié)果保存。一般,放入表中。4.應(yīng)用:往往求解具有某種最優(yōu)性質(zhì)的問題,此類問題往往具有多個(gè)解,我們要找到具有最優(yōu)值的那個(gè)解。5.步驟:找出最優(yōu)解的性質(zhì),刻畫其特征;遞歸地定義最優(yōu)值;以自底向上的方式計(jì)算出最優(yōu)值;根據(jù)

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫僅提供信息存儲(chǔ)空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論