算法設(shè)計(jì)與分析第七八講

《算法設(shè)計(jì)與分析第七八講》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、智能信息處理研究中心（RCIIP）第第33章章動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃潘海為1智能信息處理研究中心（RCIIP）學(xué)習(xí)要點(diǎn)?理解動(dòng)態(tài)規(guī)劃算法的概念。P?掌握動(dòng)態(tài)規(guī)劃算法的基本要素（1）最優(yōu)子結(jié)構(gòu)性質(zhì)（2）重疊子問題性質(zhì)a?掌握設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的步驟。（1）找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。（2）遞歸地定義最優(yōu)值。n（3）以自底向上的方式計(jì)算出最優(yōu)值。（4）根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。2智能信息處理研究中心（RCIIP）學(xué)習(xí)要點(diǎn)?通過應(yīng)用范例學(xué)習(xí)動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)策略。P（1）矩陣連乘問題；（2）最長(zhǎng)公共子序列；a（3）凸

2、多邊形最優(yōu)三角剖分；（4）0/1背包問題；（5）最優(yōu)二叉搜索樹。n3智能信息處理研究中心（RCIIP）背景?在50年代,RichardBellman等人提出了解決多階段決策P問題的“最優(yōu)性原理”，并創(chuàng)建了最優(yōu)化問題的一種新的求解方法--動(dòng)態(tài)規(guī)劃（Dynamicprogramming）。1957年，出版“動(dòng)態(tài)規(guī)劃”。?優(yōu)點(diǎn)：a對(duì)許多問題，比線性規(guī)劃或非線性規(guī)劃更有效。?弱點(diǎn)：（1）得出函數(shù)方程后，尚無統(tǒng)一處理方法；n（2）維數(shù)屏蔽:變量個(gè)數(shù)（維數(shù)）太大時(shí)無法解決。4智能信息處理研究中心（RCIIP）動(dòng)態(tài)規(guī)劃算法的基本要素PW

3、hyWhy？？What?What?aHow?How?n5智能信息處理研究中心（RCIIP）動(dòng)態(tài)規(guī)劃算法的基本要素WhyWhy？？1.Divide-and-conquer技術(shù)的問題P?子問題是相互獨(dú)立的?如果子問題不是相互獨(dú)立的，分治方法將重復(fù)計(jì)算公共子問題，效率很低a2.優(yōu)化問題?給定一組約束條件和一個(gè)代價(jià)函數(shù)，在解空間中搜索具有最小或最大代價(jià)的優(yōu)化解n?很多優(yōu)化問題可分為多個(gè)子問題，子問題相互關(guān)聯(lián)，子問題的解被重復(fù)使用6智能信息處理研究中心（RCIIP）動(dòng)態(tài)規(guī)劃算法的基本要素What?What?1.DynamicProg

4、ramming特點(diǎn)P?把原始問題劃分成一系列子問題?求解每個(gè)子問題僅一次，并將其結(jié)果保存在一個(gè)表中，以后用到時(shí)直接存取，a?不重復(fù)計(jì)算，節(jié)省計(jì)算時(shí)間?自底向上地計(jì)算2.適用范圍n?一類優(yōu)化問題：可分為多個(gè)相關(guān)子問題，子問題的解被重復(fù)使用7智能信息處理研究中心（RCIIP）動(dòng)態(tài)規(guī)劃算法的基本要素How?How??使用DynamicProgramming的條件P1.優(yōu)化子結(jié)構(gòu)?當(dāng)一個(gè)問題的優(yōu)化解包含了子問題的優(yōu)化解時(shí)，我們說這個(gè)問題具有優(yōu)化子結(jié)構(gòu)。a?縮小子問題集合，只需那些優(yōu)化問題中包含的子問題，減低實(shí)現(xiàn)復(fù)雜性?優(yōu)化子結(jié)構(gòu)使

5、得我們能自下而上地完成求解過程2.重疊子問題n?在問題的求解過程中，很多子問題的解將被多次使用8智能信息處理研究中心（RCIIP）動(dòng)態(tài)規(guī)劃算法的基本要素How?How?一、最優(yōu)子結(jié)構(gòu)一、最優(yōu)子結(jié)構(gòu)P?矩陣連乘計(jì)算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)。?在分析問題的最優(yōu)子結(jié)構(gòu)性質(zhì)時(shí)，所用的方法具有普遍性：同一個(gè)問題可以有多種方式刻劃首先假設(shè)由問題的最優(yōu)解導(dǎo)出的子問題的解不是最優(yōu)的，然后它的最優(yōu)子結(jié)構(gòu)，有些表示方a法的求解速度更快（空間占用小，問題的維度低）再設(shè)法說明在這個(gè)假設(shè)下可構(gòu)造出比原問題最

6、優(yōu)解更好的解，從而導(dǎo)致矛盾。?利用問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，以自底向上的方式遞歸地從子n問題的最優(yōu)解逐步構(gòu)造出整個(gè)問題的最優(yōu)解。最優(yōu)子結(jié)構(gòu)是問題能用動(dòng)態(tài)規(guī)劃算法求解的前提。9智能信息處理研究中心（RCIIP）動(dòng)態(tài)規(guī)劃算法的基本要素How?How?二、重疊子問題二、重疊子問題P?遞歸算法求解問題時(shí)，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計(jì)算多次。這種性質(zhì)稱為子問題的重疊性質(zhì)。?動(dòng)態(tài)規(guī)劃算法，對(duì)每一個(gè)子問題只解一次，而后將其解保存在a一個(gè)表格中，當(dāng)再次需要解此子問題時(shí)，只是簡(jiǎn)單地用常數(shù)時(shí)間查看一下結(jié)果。n?通常,不同的子

7、問題個(gè)數(shù)隨問題的大小呈多項(xiàng)式增長(zhǎng)。因此用動(dòng)態(tài)規(guī)劃算法只需要多項(xiàng)式時(shí)間，從而獲得較高的解題效率。10智能信息處理研究中心（RCIIP）動(dòng)態(tài)規(guī)劃算法的基本要素How?How?三、備忘錄方法三、備忘錄方法P?備忘錄方法的控制結(jié)構(gòu)與直接遞歸方法的控制結(jié)構(gòu)相同，也是自頂向下的方法，區(qū)別在于備忘錄方法為每a個(gè)解過的子問題建立了備忘錄以備需要時(shí)查看，避免了相同子問題的重復(fù)求解。n11智能信息處理研究中心（RCIIP）動(dòng)態(tài)規(guī)劃算法的基本要素How?How??動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分P解成若干個(gè)子問題T(n)=

8、naT(n/k)T(n/k)T(n/k)nT(n/k)12智能信息處理研究中心（RCIIP）動(dòng)態(tài)規(guī)劃算法的基本要素How?How??但是經(jīng)分解得到的子問題往往不是互相獨(dú)立的。不同子問題的P數(shù)目常常只有多項(xiàng)式量級(jí)。在用分治法求解時(shí)，有些子問題被重復(fù)計(jì)算了許多次。T(n)=nan/kn/kn/kn/knT(