貪心法與動態(tài)規(guī)劃

第8章貪心法與動態(tài)規(guī)劃(2)石志國大綱◎貪心法的基本概念，以及使用貪心法解決問題：哈夫曼編碼、單源最短路徑、最小生成樹、背包問題◎動態(tài)規(guī)劃的基本概念，以及使用動態(tài)規(guī)劃解決問題：多源最短路徑、背包問題、圖像壓縮和最長公共子序列問題。問題提出

動態(tài)規(guī)劃是解決多階段決策最優(yōu)化問題的一種方法。如圖所示的一個線路網(wǎng)絡(luò)，兩點(diǎn)之間的連線上的數(shù)字表示兩個點(diǎn)之間的距離，要求求出一條從A到E的路徑，使得總距離最小。問題提出從圖可以看出，從A到E可以劃分為5個階段，除起點(diǎn)A和終點(diǎn)E外，其它各點(diǎn)既是上一階段的終點(diǎn)又是下一階段的起點(diǎn)。例如從A到B的第一階段中，A為起點(diǎn)，B1和B2為終點(diǎn)，這里就存在兩種情況供選擇。同理，在第2和第3階段都存在多種情況供選擇?，F(xiàn)在的問題是：如何在每個階段都作出一個恰當(dāng)?shù)臎Q策，使由這些決策組成的一個決策序列所構(gòu)成的一條線路的總距離最短。問題提出一個容易想到的方法是愚公移山的想法(exhaustivesearch)，即窮舉法。將從A到E的所有可能路線的距離都計(jì)算出來，然后兩兩互相比較，找出最短路線。其缺點(diǎn)是計(jì)算比較復(fù)雜。問題提出實(shí)際上，求從A到E的最短距離問題，可以轉(zhuǎn)化為兩個性質(zhì)完全相同，但規(guī)模較小的子問題即分別從B1、B2到E的最短路徑問題，這時，從A到E的最短距離(記為SD(A))問題可以表示為：

動態(tài)規(guī)劃法同樣，計(jì)算SD(B1)又可以歸結(jié)為性質(zhì)完全相同，但規(guī)模更小的問題，即分別求C1，C2，C3到E的最短路徑問題SD(Ci)(i=1,2,3)，而求SD(Ci)又可以歸結(jié)為求SD(D1)和SD(D2)兩個子問題。由于SD(D1)和SD(D2)是已知的，因此，可以從這兩個值開始，逆向遞歸計(jì)算出SD(A)的值。最終，可以得到從A到E的最短路徑。上述求解的方法稱為動態(tài)規(guī)劃法(DynamicProgramming)。2動態(tài)規(guī)劃法概述動態(tài)規(guī)劃是美國數(shù)學(xué)家R．Bellman等人于1951年在研究多階段決策過程的優(yōu)化問題時所創(chuàng)立的一種用于解決此類過程優(yōu)化問題的新方法。（1）基本思想在現(xiàn)實(shí)生活中，有一類問題可以將其活動過程分解成若干個相互聯(lián)系的階段，在它的每一階段都需要作出決策，從而使整個過程達(dá)到最好的活動效果。在每個階段所作的決策選擇依賴于當(dāng)前狀態(tài)，又影響它以后的發(fā)展。當(dāng)各個階段決策確定后，就組成一個決策序列，從而就確定了整個過程的一條活動路線。這種將一個問題看作是一個前后相互關(guān)聯(lián)且具有鏈狀結(jié)構(gòu)的多階段過程稱為多階段決策過程。如圖所示。其中，“狀態(tài)”是指各決策階段開始時的客觀條件。（1）基本思想在多階段決策過程中，某一階段會存在多個決策序列，如果在進(jìn)行決策時遵循如下原則：求解過程為自底向上（即從終點(diǎn)到起點(diǎn)），每一步的選擇總是依賴于上一步的選擇，且此步僅僅把不可能的決策序列排除在外。則這種解決多階段決策的最優(yōu)化的過程稱為動態(tài)規(guī)劃法。動態(tài)規(guī)劃法適用方法動態(tài)規(guī)劃法主要適用于最優(yōu)化問題的求解。這類問題會有多種可能的解，每個解都有一個值，而動態(tài)規(guī)劃找出其中最優(yōu)(最大或最小)值的解。若存在若干個最優(yōu)值的解的話，它只取其中的一個。與分治法和貪心法聯(lián)系與區(qū)別動態(tài)規(guī)劃法與分治法和貪心法類似，它也是將原問題分解為若干個更小的、相似的子問題，并通過求解子問題產(chǎn)生一個全局最優(yōu)解。與分治法和貪心法不同之處在于：①使用貪心法時，當(dāng)前的選擇可能要依賴于已經(jīng)作出的所有選擇，但不依賴于有待于做出的選擇和子問題。因此貪心法是自頂向下(即從起點(diǎn)到終點(diǎn))，一步一步地作出貪心選擇。當(dāng)然，如果當(dāng)前的選擇可能要依賴于子問題的解時，則難以通過局部的貪心策略達(dá)到全局最優(yōu)解。②使用分治法時，由原問題分解出的各子問題通常是相互獨(dú)立的，即不包含公共的子問題，因此一旦遞歸地求出各子問題的解后，便可自下而上地將各子問題的解合并成問題的解。如果各子問題不是相互獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地求解公共的子問題。③動態(tài)規(guī)劃允許由原問題分解出的子問題之間相互依賴。每一個子問題只求解一次，并將結(jié)果保存起來，避免每次碰到此子問題時都要重復(fù)計(jì)算。（2）適用條件適用動態(tài)規(guī)劃的問題通常應(yīng)滿足如下3點(diǎn)：①最優(yōu)化原理（最優(yōu)子結(jié)構(gòu)性質(zhì)）如果問題的最優(yōu)解所包含的子問題的解也是最優(yōu)的，就稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，即滿足最優(yōu)化原理。所謂最優(yōu)原理是指無論前面的策略如何，此后的決策必須是基于當(dāng)前狀態(tài)（由上一次決策產(chǎn)生）的最優(yōu)決策。②無后效性應(yīng)用動態(tài)規(guī)劃法的一個重要條件就是將各階段按照一定的次序排列好，階段i的狀態(tài)只能由階段i+1的狀態(tài)來確定，與其它狀態(tài)沒有關(guān)系，尤其是與未發(fā)生的狀態(tài)沒有關(guān)系。換言之，每個狀態(tài)都是“過去歷史的一個完整總結(jié)”。這就是無后效性。③子問題的重疊性子問題重疊性是指在利用遞歸算法自頂向下對問題進(jìn)行求解時，每次產(chǎn)生的子問題并不總是新問題，有些子問題可能會被重復(fù)計(jì)算多次。動態(tài)規(guī)劃法正是利用子問題的這種重疊性質(zhì)，對每一個子問題只計(jì)算一次，然后將其計(jì)算結(jié)果保存在起來，當(dāng)再次需要計(jì)算已經(jīng)計(jì)算過的子問題時，只是簡單地查看一下以往的計(jì)算結(jié)果，從而獲得較高的解題效率。子問題的重疊性并不是動態(tài)規(guī)劃適用的必要條件，但是如果該性質(zhì)無法滿足，動態(tài)規(guī)劃算法同其它算法相比就無優(yōu)勢可言了。（3）解決問題的步驟利用動態(tài)規(guī)劃法求解問題的算法通常包含如下幾個步驟：①分析對原始的問題進(jìn)行分析，找出問題的最優(yōu)解的結(jié)構(gòu)特征。②分解將所給問題按時間或空間特征分解成若干相互關(guān)聯(lián)的階段，并確定出計(jì)算局部最優(yōu)解的遞推關(guān)系，這是利用動態(tài)規(guī)劃法解決問題的關(guān)鍵和難點(diǎn)所在。需要注意的是，分解后的各個階段一定是有序的或者是可排序的，即無后向性。否則問題就無法用動態(tài)規(guī)劃求解。階段之間相互聯(lián)系方式是通過狀態(tài)和狀態(tài)轉(zhuǎn)移體現(xiàn)的。每個階段通常包含若干個狀態(tài)，用以描述問題發(fā)展到這個階段時所處在的一種客觀情況。每個階段的狀態(tài)都是由以前階段的狀態(tài)以某種方式“變化”而來的，這種“變化”稱為狀態(tài)轉(zhuǎn)移。狀態(tài)轉(zhuǎn)移是導(dǎo)出狀態(tài)的途徑，也是聯(lián)系各階段的方式。③解決對于每個階段通過自底向上的方法求得局部問題的最優(yōu)解。由于這一步驟通常是通過遞推實(shí)現(xiàn)的，因此，需要一個遞推的終止條件或邊界條件。④合并將各個階段求出的的解合并為原問題的解，即構(gòu)造一個最優(yōu)解。步驟①～③是動態(tài)規(guī)劃法的基本步驟。在只需要求出最優(yōu)值的情形下，步驟④可以省略。若需要求出問題的一個最優(yōu)解，則必須執(zhí)行步驟④。此時，在步驟③中計(jì)算最優(yōu)值時，通常需記錄更多的信息，以便在步驟④中，根據(jù)所記錄的信息，快速地構(gòu)造出一個最優(yōu)解。動態(tài)規(guī)劃的主要難點(diǎn)動態(tài)規(guī)劃的主要難點(diǎn)在于理論上的設(shè)計(jì)，特別是遞推關(guān)系的建立，一旦設(shè)計(jì)完成，實(shí)現(xiàn)部分就會非常簡單。整個求解過程就可以使用一個最優(yōu)決策表的二維數(shù)組來描述，其中，行表示決策的階段，列表示問題狀態(tài)，表格需要填寫的數(shù)據(jù)一般對應(yīng)此問題的在某個階段某個狀態(tài)下的最優(yōu)值，如最短路徑，最長公共子序列，最大價值等。填表的過程就是根據(jù)遞推關(guān)系從1行1列開始，以行或者列優(yōu)先的順序，依次填寫表格。最后根據(jù)整個表格的數(shù)據(jù)通過簡單的取舍或者運(yùn)算求得問題的最優(yōu)解。總之，動態(tài)規(guī)劃算法的關(guān)鍵在于解決冗余，是一個以空間換時間的技術(shù)，所以它的空間復(fù)雜度要大于其它的算法。應(yīng)用舉例-多源最短路徑

1）問題描述所謂多源最短路徑問題就是指對于一個給定的非負(fù)有向網(wǎng)圖，求出任意兩個結(jié)點(diǎn)之間的最短路徑。目前，對于多源最短路徑問題更直接的做法是使用Warshall-Floyd算法。其中，Warshall算法是一個用于求圖的傳遞閉包的算法。而求任意兩個頂點(diǎn)之間的最短路徑的Floyd(弗洛伊德)算法與Warshall算法非常相似，所以通常稱Floyd算法為Warshall-Floyd算法。應(yīng)用舉例-多源最短路徑對于一個n×n的矩陣，F(xiàn)loyd算法使用的迭代矩陣序列如下：D0，D1，…，Dn-1迭代的初始值D0是圖的鄰接矩陣，然后逐步嘗試在原來的路徑中加入其它的結(jié)點(diǎn)作為中間點(diǎn)，如果加入新結(jié)點(diǎn)后求得的路徑比原來的路徑短，則以此新路徑替代原來的路徑。然后再加入一個頂點(diǎn)，繼續(xù)進(jìn)行迭代。依次類推，直到經(jīng)過n次比較后，就可以求得兩個頂點(diǎn)之間的最短路徑。例如，假設(shè)Dk-1中第i行第j列的值為dijk-1，增加頂點(diǎn)vk后，需要進(jìn)行dijk-1與dikk-1+dkjk-1的大小比較，取它們中的小者為dijk，即有如下迭代公式：dijk=min{dijk-1,dikk-1+dkjk-1}0≤k≤n-1（6-1）程序?qū)嵗斎腠旤c(diǎn)個數(shù):(最大輸入數(shù)為:5)5依次輸入頂點(diǎn)名:ABCDE輸入邊數(shù):7按"headtailweight"的方式輸入邊信息：AB10AD30AE100BC50CE10DC20DE60圖中所有邊如下:(A,B,10)(A,D,30)(A,E,100)(B,C,50)(C,E,10)(D,C,20)(D,E,60)最小路徑值:60路徑:0324圖像壓縮

1）問題描述在計(jì)算機(jī)中，圖像常用像素點(diǎn)的灰度值來表示，假如一幅圖像用一個mXm的像素陣列表示，每個像素都用一個字節(jié)來存儲，則總的存儲空間為8m2位。為了減少所需的存儲空間，通常采用變長模式存儲，即不同像素用不同位數(shù)來存儲。圖像壓縮問題就是要尋找一個方案，通過對給定的圖像像素點(diǎn)進(jìn)行合理的分割，針對不同的子段采用不同存儲位技術(shù)即變長模式，使得整個圖像所占用的存儲空間最小。圖像壓縮2）算法實(shí)現(xiàn)比如：表示一幅圖像的像素點(diǎn)灰度值序列為{p1，p2，…，pn}，其中pi表示第i個像素點(diǎn)的灰度值?；叶戎档姆秶鸀?-255。假設(shè)將像素點(diǎn)序列{p1，p2，…，pn}分割為m個連續(xù)子段S1，S2，…，Sm。其中，像素段Si中包含有L[i]個像素，且該段中每個像素都用b[i]位來表示。如果b[i]和L[i]取值范圍分別限制為：1≤b[i]≤8，1≤L[i]≤255，則需要3位表示b[i]，8位表示L[i]。此時像素段Si所需存儲空間為：L[i]*b[i]+11位。其中11為每個像素段的頭信息，用于存儲段的長度以及該段中每個像素所占用的位數(shù)。另外還可以通過將某些相鄰段合并的方式來減少空間消耗。如當(dāng)像素段

i

和i-1合并后，像素段長應(yīng)為L[i]+L[i-1]。合并后像素段中的每個像素的存儲位數(shù)應(yīng)設(shè)為max{b[i]，b[i-1]}

位。圖像壓縮令s[k]為前k個像素段的最優(yōu)合并所需要的空間。定義s[0]=0。則第i(i＞0)個像素段與其前面第i-