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

1、動態(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)過的權(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動態(tài)規(guī)劃解決的問題n能夠用動態(tài)規(guī)劃解決的問題，往往是最優(yōu)化問題而且問題的最優(yōu)解的局部往往是局部問題在相應(yīng)條件下的最優(yōu)解。而且問題的最優(yōu)解與其子問題的最優(yōu)解要有一定的關(guān)聯(lián)，要能建立遞推關(guān)系，此外，為了體現(xiàn)動態(tài)規(guī)劃的高時(shí)效，子問題應(yīng)當(dāng)是互相重疊的，即很多不同的問題共享相同的子問題。6動態(tài)規(guī)劃的解題思路n通過劃分子問題來縮小問題規(guī)模n記錄子問題的最優(yōu)解從而

3、避免重復(fù)計(jì)算7設(shè)計(jì)動態(tài)規(guī)劃算法的一般步驟n確定子問題的表示方法（確定狀態(tài)）n遞歸地定義最優(yōu)解的值（狀態(tài)轉(zhuǎn)移方程）n按自底而上的方式構(gòu)造最優(yōu)解的值8動態(tài)規(guī)劃實(shí)現(xiàn)的兩種方法n自頂而下的記憶化搜索n通過遞歸的方式，將對問題最優(yōu)解的求解，歸結(jié)為求其子問題的最優(yōu)解，并將計(jì)算過的結(jié)果記錄下來，以后使用時(shí)不必重新計(jì)算。n自底而上的遞推方法9動態(tài)規(guī)劃的分類n編號動態(tài)規(guī)劃n區(qū)間動態(tài)規(guī)劃n劃分動態(tài)規(guī)劃n數(shù)軸動態(tài)規(guī)劃n樹形動態(tài)規(guī)劃10編號動態(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編號動態(tài)規(guī)劃

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

5、最優(yōu)解：ndpi = max dpj | 0 j i; aj ai + 113編號動態(tài)規(guī)劃-最長不下降子序列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編號動態(tài)規(guī)劃-最長不下降子序列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可以通過二分查找求出）15編號動態(tài)

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