lab4-動態(tài)規(guī)劃算法設(shè)計(jì)與應(yīng)用

1、實(shí)驗(yàn)四實(shí)驗(yàn)四動態(tài)規(guī)劃算法設(shè)計(jì)與應(yīng)用動態(tài)規(guī)劃算法設(shè)計(jì)與應(yīng)用一.實(shí)驗(yàn)?zāi)康暮鸵?.加深對動態(tài)規(guī)劃算法的基本原理的理解，掌握用動態(tài)規(guī)劃方法求解最優(yōu)化問題的方法步驟及應(yīng)用；2.用動態(tài)規(guī)劃設(shè)計(jì)整數(shù)序列的最長遞增子序列問題的算法，分析其復(fù)雜性，并實(shí)現(xiàn)；3.用動態(tài)規(guī)劃設(shè)計(jì)求凸多邊形的三角剖分問題的算法，分析其復(fù)雜性，并實(shí)現(xiàn)。4.選做題：用動態(tài)規(guī)劃設(shè)計(jì)求解01背包問題的算法，分析其復(fù)雜性，并實(shí)現(xiàn)。二基本原理動態(tài)規(guī)劃是一種非常重要的程序設(shè)計(jì)方法，常用于求

2、解最優(yōu)化問題。最優(yōu)化問題：給定若干個約束條件和一個目標(biāo)函數(shù)，在某指定集合中求滿足所有約束條件的且使得目標(biāo)函數(shù)值達(dá)最大或最小的元素和相應(yīng)的目標(biāo)函數(shù)值，即：問題的最優(yōu)值和最優(yōu)解。適用動態(tài)規(guī)劃求解的問題的基本要素：(1)滿足最優(yōu)性原理：即一個最優(yōu)化問題的最優(yōu)解包含了其子問題的最優(yōu)解。(2)無后向性：即某階段狀態(tài)一旦確定，就不受這個狀態(tài)以后決策的影響。也即，某狀態(tài)以后的過程不會影響以前的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)，這種特性也被稱為無后效性。(2)具

3、有重疊的子問題：即問題被分解成的子問題存在互相重疊。動態(tài)規(guī)劃方法對于這些重疊的子問題只求解一次，以提高算法的效率。三該類算法設(shè)計(jì)與實(shí)現(xiàn)的要點(diǎn)動態(tài)規(guī)劃算法求解最優(yōu)化問題的步驟：(1)找出問題的最優(yōu)子結(jié)構(gòu)。分析問題的最優(yōu)解（最優(yōu)值）的結(jié)構(gòu)特征。(2)遞歸地定義最優(yōu)值。根據(jù)最優(yōu)子結(jié)構(gòu)，確定最優(yōu)值所滿足的遞歸公式。(3)計(jì)算最優(yōu)值。根據(jù)最優(yōu)值的遞歸公式，采用自底向上的迭代或自頂向下的遞歸，計(jì)算最優(yōu)值。(4)構(gòu)造最優(yōu)解。在求解最優(yōu)值的過程中要記錄

4、下得到最優(yōu)值的相應(yīng)最優(yōu)解的信息，并根據(jù)該信息構(gòu)造最優(yōu)解。注意：在計(jì)算最優(yōu)值時應(yīng)保存相應(yīng)的信息：(a)已經(jīng)求出的子問題的最優(yōu)值（避免重復(fù)計(jì)算）。(b)最優(yōu)解的有關(guān)信息。動態(tài)規(guī)劃算法求解其它問題的步驟：(1)根據(jù)最優(yōu)化原理分析問題的解的結(jié)構(gòu)。(2)遞歸地定義問題的解。(3)計(jì)算問題的解。根據(jù)解的遞歸公式，自底向上或自頂向下地計(jì)算解，計(jì)算過程中注意保存已經(jīng)求出的子問題的解。其中，自底向上方法通過迭代來實(shí)現(xiàn)，適用于所有的子問題都需要解的情況，實(shí)

5、現(xiàn)時要注意根據(jù)遞歸公式正確確定子問題的求解順序。自頂向下方法通過遞歸來實(shí)現(xiàn)，適用于不必解所有的子問題的情況，實(shí)現(xiàn)時要注意標(biāo)記子問題是否計(jì)算過，同一個子問題只在第一次遞歸調(diào)用時計(jì)算并存儲結(jié)果。四實(shí)驗(yàn)內(nèi)容(一)最長遞增子序列問題voidLcss(intH[MAX][MAX]intnintA[MAX]intLintB[MAX])inti=nj=nk=LC[MAX]while(i0i=i1j=j1elseif(H[i][j]==1)i=i1el