版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、深入分析區(qū)間型動(dòng)態(tài)規(guī)劃鄭州市第九中學(xué)張旭祥區(qū)間型動(dòng)態(tài)規(guī)劃在信息學(xué)競(jìng)賽中應(yīng)用甚廣,它是動(dòng)態(tài)規(guī)劃中的經(jīng)典問題,最小代價(jià)字母樹是這類動(dòng)態(tài)規(guī)劃最經(jīng)典的體現(xiàn),對(duì)于初學(xué)者而言這類動(dòng)態(tài)規(guī)劃并不太好理解。于是,區(qū)間型動(dòng)態(tài)規(guī)劃又成了動(dòng)態(tài)規(guī)劃中的難點(diǎn)問題。下面,本文將為大家深入分析區(qū)間型動(dòng)態(tài)規(guī)劃的思想及其程序的實(shí)現(xiàn),希望能對(duì)大家有所幫助。?歷屆大賽中區(qū)間型動(dòng)態(tài)規(guī)劃題目的考查。區(qū)間型動(dòng)態(tài)規(guī)劃是各大信息競(jìng)賽出題的熱點(diǎn),具體體現(xiàn)在以下題目:1.合并石子NOI19
2、952.能量項(xiàng)鏈NOIP20063.加分二叉樹NOIP20034.最優(yōu)排序二叉樹CTSC96這些題目出現(xiàn)的頻次及其所在比賽的重要性足以說明區(qū)間型動(dòng)態(tài)規(guī)劃在各類動(dòng)態(tài)規(guī)劃中有著舉足輕重的地位。二、區(qū)間型動(dòng)態(tài)規(guī)劃的算法分析在這里就以經(jīng)典的最小代價(jià)字母樹作為例子,對(duì)區(qū)間型動(dòng)態(tài)規(guī)劃的算法進(jìn)行分析。問題描述:給定一個(gè)序列,如4、1、2、3我們將他們相加進(jìn)行合并,最終合并成一個(gè)數(shù),每次相加的代價(jià)是兩個(gè)加數(shù)的和,求怎樣的相加順序可以使總代價(jià)最小。很多初
3、學(xué)者認(rèn)為這類動(dòng)態(tài)規(guī)劃不易理解,其重要原因是這類動(dòng)態(tài)規(guī)劃與其他動(dòng)態(tài)規(guī)劃的思想不大相同,而初學(xué)者又是利用其他動(dòng)態(tài)規(guī)劃的思想來解決這類動(dòng)態(tài)規(guī)劃,從而進(jìn)入了思維誤區(qū)。這種錯(cuò)誤的思維模式一旦建立便很難重新建立正確的解題思想,從而陷入絕境。這類動(dòng)態(tài)規(guī)劃正確的解法是這樣的:首先,根據(jù)動(dòng)態(tài)規(guī)劃無后效性的性質(zhì)可以想到:對(duì)于一個(gè)序列:A1、A2……An,假如最后相加的兩個(gè)數(shù)是第一個(gè)數(shù)到第i個(gè)數(shù)的和S[1i]以及第i1個(gè)數(shù)到第n個(gè)數(shù)的和S[i1n],另外,對(duì)
4、于第一個(gè)數(shù)到第i個(gè)數(shù)相加的最小代價(jià)是F[1i]以及從第i1到第n個(gè)數(shù)相加的最小代價(jià)為F[i1n],則總代價(jià)即為F[i1n]F[1i](前面相加的最小代價(jià))S[1i]S[i1n](最后一次相加的最小代價(jià))。由此,我們可以清楚的看出要想求出總代價(jià)的最小值只要枚舉i的位置,使得F[i1n]F[1i]S[1i]S[i1n]的和最小即可。綜上所述我們可以總結(jié)出狀態(tài)轉(zhuǎn)移方程:輸入:44594輸出:4594859139224594414441822這
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 深入分析 linux 內(nèi)核鏈表
- 深入分析linux內(nèi)核鏈表
- 深入分析_linux_內(nèi)核鏈表
- 鏈家地產(chǎn)---深入分析報(bào)告
- 慢病管理商業(yè)模式深入分析
- 深入分析mfc文檔視圖結(jié)構(gòu)(項(xiàng)目實(shí)踐)
- [學(xué)習(xí)]對(duì)服務(wù)業(yè)組織的深入分析
- 深入分析led光衰的重要原因
- 鋼橋橋面鋪裝力學(xué)特性深入分析.pdf
- 動(dòng)態(tài)規(guī)劃的深入討論
- 動(dòng)態(tài)規(guī)劃的深入討論論文
- 赫拉與特提斯-深入分析巨蟹座神話
- 深入分析經(jīng)濟(jì)增長、貨幣供給與通貨膨脹的關(guān)系
- pstn交換網(wǎng)和傳輸網(wǎng)時(shí)鐘同步關(guān)系深入分析
- 深入分析當(dāng)前形勢(shì),推進(jìn)黃石市城鎮(zhèn)化向前發(fā)展
- 深入學(xué)習(xí)關(guān)于促進(jìn)社會(huì)辦醫(yī)持續(xù)健康規(guī)范發(fā)展的意見-醫(yī)改的癥結(jié)深入分析
- 深入分析公路工程施工當(dāng)中關(guān)鍵部位的施工技術(shù)
- 人口轉(zhuǎn)變對(duì)經(jīng)濟(jì)增長的影響機(jī)制研究——基于人口紅利理論框架的深入分析.pdf
- 15896.區(qū)間線性系統(tǒng)的farkas型定理及區(qū)間二次規(guī)劃的研究
- 基于WAMS的區(qū)間振蕩動(dòng)態(tài)特性分析方法研究.pdf
評(píng)論
0/150
提交評(píng)論