動(dòng)態(tài)規(guī)劃ppt課件

1、動(dòng)態(tài)規(guī)劃天津大學(xué)1;.2例題：數(shù)字方陣n給出一個(gè)數(shù)字方陣，形式如下：n1 2 3 4n8 7 6 5n9 10 11 12n16 15 14 13n找出從第一層到最后一層的一條路，使得所經(jīng)過(guò)的權(quán)值之和最小。要求每一步只能向下，左下和右下這三個(gè)方向走。3例題：數(shù)字方陣n設(shè)f(i, j)是走到第i行第j列時(shí)能夠得到的最小權(quán)值，根據(jù)規(guī)則最多只有三個(gè)格子能走到這個(gè)格子：（i-1, j-1），（i-1, j），（i-1, j+1）。要求出到走到位置（i, j）時(shí)的能夠得到的最小權(quán)值，要先求出走到上面那三個(gè)位置時(shí)的最小權(quán)值（為什么？）于是可以列出遞歸式：nf(i, j) = min f(i-1, j-1)

2、, f(i-1, j), f(i-1, j+1) + wijn然而如果這樣直接寫成遞歸程序，效率并不高。4例題：數(shù)字方陣n使用二維數(shù)組dp，每當(dāng)算完一個(gè)f(i,j)，就把結(jié)果保存在dpij中，下次再用到這個(gè)結(jié)果，可以直接使用，從而避免了重復(fù)計(jì)算。5動(dòng)態(tài)規(guī)劃解決的問(wèn)題n能夠用動(dòng)態(tài)規(guī)劃解決的問(wèn)題，往往是最優(yōu)化問(wèn)題而且問(wèn)題的最優(yōu)解的局部往往是局部問(wèn)題在相應(yīng)條件下的最優(yōu)解。而且問(wèn)題的最優(yōu)解與其子問(wèn)題的最優(yōu)解要有一定的關(guān)聯(lián)，要能建立遞推關(guān)系，此外，為了體現(xiàn)動(dòng)態(tài)規(guī)劃的高時(shí)效，子問(wèn)題應(yīng)當(dāng)是互相重疊的，即很多不同的問(wèn)題共享相同的子問(wèn)題。6動(dòng)態(tài)規(guī)劃的解題思路n通過(guò)劃分子問(wèn)題來(lái)縮小問(wèn)題規(guī)模n記錄子問(wèn)題的最優(yōu)解從而

3、避免重復(fù)計(jì)算7設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的一般步驟n確定子問(wèn)題的表示方法（確定狀態(tài)）n遞歸地定義最優(yōu)解的值（狀態(tài)轉(zhuǎn)移方程）n按自底而上的方式構(gòu)造最優(yōu)解的值8動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)的兩種方法n自頂而下的記憶化搜索n通過(guò)遞歸的方式，將對(duì)問(wèn)題最優(yōu)解的求解，歸結(jié)為求其子問(wèn)題的最優(yōu)解，并將計(jì)算過(guò)的結(jié)果記錄下來(lái)，以后使用時(shí)不必重新計(jì)算。n自底而上的遞推方法9動(dòng)態(tài)規(guī)劃的分類n編號(hào)動(dòng)態(tài)規(guī)劃n區(qū)間動(dòng)態(tài)規(guī)劃n劃分動(dòng)態(tài)規(guī)劃n數(shù)軸動(dòng)態(tài)規(guī)劃n樹形動(dòng)態(tài)規(guī)劃10編號(hào)動(dòng)態(tài)規(guī)劃一般有兩種表示狀態(tài)的方法：1) 狀態(tài)i表示前i個(gè)元素構(gòu)成的最優(yōu)解，可能不包含第i個(gè)元素。2) 狀態(tài)i表示在必須包含第i個(gè)元素的情況下前i個(gè)元素構(gòu)成的最優(yōu)解。11編號(hào)動(dòng)態(tài)規(guī)劃

4、-最長(zhǎng)不下降子序列n給定一個(gè)序列：a1, a2, , an，從這個(gè)序列中選出m個(gè)元素：ai1, ai2, , aim，如果i1, i2, , im滿足i1 i2 im，那么就把這m個(gè)選出的元素組成的序列成為原來(lái)序列的子序列。如果子序列滿足ai1 ai2 aim，那么就稱這個(gè)子序列為不下降子序列，這個(gè)問(wèn)題是要求出指定序列的最長(zhǎng)不下降子序列。12編號(hào)動(dòng)態(tài)規(guī)劃-最長(zhǎng)不下降子序列n分析：假設(shè)最長(zhǎng)不下降子序列中包含元素ak，那么一定存在一組最優(yōu)解，它包含了a1, a2, , ak這個(gè)序列的最長(zhǎng)不下降子序列。n子問(wèn)題的表示：令dpi表示以第i個(gè)元素結(jié)尾的前i個(gè)元素構(gòu)成的最長(zhǎng)不下降子序列的長(zhǎng)度。n遞歸地定義

5、最優(yōu)解：ndpi = max dpj | 0 j i; aj ai + 113編號(hào)動(dòng)態(tài)規(guī)劃-最長(zhǎng)不下降子序列n偽代碼：nFOR i FROM 1 TO nn dpi 0;n FOR j FROM 1 TO i 1n IF aj dpin THEN dpi dpj;n dpi dpi + 1;14編號(hào)動(dòng)態(tài)規(guī)劃-最長(zhǎng)不下降子序列n上面的算法的時(shí)間復(fù)雜度為O(n2)，是否可以優(yōu)化呢？n分析：設(shè)Ai = min aj | dpj = i，那么如果i j，一定可以推出Ai Aj。n狀態(tài)轉(zhuǎn)移：ndpi = max j | Aj ai + 1; n（maxj | Aj ai可以通過(guò)二分查找求出）15編號(hào)動(dòng)態(tài)

6、規(guī)劃-最大局部和n給定一個(gè)數(shù)列：a1, a2, , an，它的局部和定義為S(i, j) = ai + ai+1 + + aj。求這個(gè)數(shù)列的最大局部和。16編號(hào)動(dòng)態(tài)規(guī)劃-最大局部和n分析：如果元素ai是最大局部和的一部分，那么只有兩種情況：ai是這個(gè)局部和的開(kāi)始元素；或ai接在ai-1之后。n子問(wèn)題的表示：n令dpi表示以ai結(jié)束的最大局部和。n遞歸地定義最優(yōu)解：ndpi = maxdpi 1 + ai, ain化簡(jiǎn)得：dpi = max dpi 1, 0 + ai17編號(hào)動(dòng)態(tài)規(guī)劃-最大局部和n偽代碼：ndp0 0;nFOR i FROM 1 TO nn IF dpi 1 0）n最終結(jié)果為：maxsumi39樹形動(dòng)態(tài)規(guī)劃-賄賂nA國(guó)要申辦某項(xiàng)國(guó)際會(huì)議，它必須爭(zhēng)取到m個(gè)以上國(guó)家的同意才能申辦成功。然而，如果不采用賄賂的手段，沒(méi)有國(guó)家會(huì)支持A國(guó)。在國(guó)與國(guó)之間存在附庸關(guān)系，如果B國(guó)是C國(guó)的附庸國(guó)，那么賄賂了C國(guó)就不用再賄賂B國(guó)也會(huì)獲得B國(guó)的支持?，F(xiàn)在已知n個(gè)國(guó)家之間的附庸關(guān)系，以及賄賂每個(gè)國(guó)家需要花費(fèi)的資金，問(wèn)最少需要花費(fèi)多少，A國(guó)才能申辦成功。40樹形動(dòng)態(tài)規(guī)劃-賄賂n國(guó)家的關(guān)系形成一個(gè)森林，用dpij表示在國(guó)家i及其子樹中，爭(zhēng)取到j(luò)張選票所需的最