一、動(dòng)態(tài)規(guī)劃算法簡(jiǎn)介

　　動(dòng)態(tài)規(guī)劃算法是通過(guò)拆分問(wèn)題，定義問(wèn)題狀態(tài)和狀態(tài)之間的關(guān)系，使得問(wèn)題能夠以遞推（或者說(shuō)分治）的方式去解決。

　　1.基本思想與策略

　　動(dòng)態(tài)規(guī)劃算法的基本思想與分治法類似，也是將待求解的問(wèn)題分解為若干個(gè)子問(wèn)題（階段），按順序求解子階段，前一子問(wèn)題的解，為后一子問(wèn)題的求解提供了有用的信息。在求解任一子問(wèn)題時(shí)，列出各種可能的局部解，通過(guò)決策保留那些有可能達(dá)到最優(yōu)的局部解，丟棄其他局部解。依次解決各子問(wèn)題，最后一個(gè)子問(wèn)題就是初始問(wèn)題的解。由于動(dòng)態(tài)規(guī)劃解決的問(wèn)題多數(shù)有重疊子問(wèn)題這個(gè)特點(diǎn)，為減少重復(fù)計(jì)算，對(duì)每一個(gè)子問(wèn)題只解一次，將其不同階段的不同狀態(tài)保存在一個(gè)二維數(shù)組中。

　　2.適用情況

　　能采用動(dòng)態(tài)規(guī)劃求解的問(wèn)題的一般要具有3個(gè)性質(zhì)：

　　（1）最優(yōu)化原理：如果問(wèn)題的最優(yōu)解所包含的子問(wèn)題的解也是最優(yōu)的，就稱該問(wèn)題具有最優(yōu)子結(jié)構(gòu)，即滿足最優(yōu)化原理。

　?。?）無(wú)后效性：即某階段狀態(tài)一旦確定，就不受這個(gè)狀態(tài)以后決策的影響。也就是說(shuō)，某狀態(tài)以后的過(guò)程不會(huì)影響以前的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)。

　　（3）有重疊子問(wèn)題：即子問(wèn)題之間是不獨(dú)立的，一個(gè)子問(wèn)題在下一階段決策中可能被多次使用到。（該性質(zhì)并不是動(dòng)態(tài)規(guī)劃適用的必要條件，但是如果沒(méi)有這條性質(zhì)，動(dòng)態(tài)規(guī)劃算法同其他算法相比就不具備優(yōu)勢(shì)）

　　3.算法實(shí)現(xiàn)

　　動(dòng)態(tài)規(guī)劃的主要難點(diǎn)在于理論上的設(shè)計(jì)，也就是上面4個(gè)步驟的確定，一旦設(shè)計(jì)完成，實(shí)現(xiàn)部分就會(huì)非常簡(jiǎn)單。使用動(dòng)態(tài)規(guī)劃求解問(wèn)題，最重要的就是確定動(dòng)態(tài)規(guī)劃三要素：

　　（1）問(wèn)題的階段

　?。?）每個(gè)階段的狀態(tài)

　?。?）從前一個(gè)階段轉(zhuǎn)化到后一個(gè)階段之間的遞推關(guān)系。

　　遞推關(guān)系必須是從次小的問(wèn)題開(kāi)始到較大的問(wèn)題之間的轉(zhuǎn)化，從這個(gè)角度來(lái)說(shuō)，動(dòng)態(tài)規(guī)劃往往可以用遞歸程序來(lái)實(shí)現(xiàn)，不過(guò)因?yàn)檫f推可以充分利用前面保存的子問(wèn)題的解來(lái)減少重復(fù)計(jì)算，所以對(duì)于大規(guī)模問(wèn)題來(lái)說(shuō)，有遞歸不可比擬的優(yōu)勢(shì)，這也是動(dòng)態(tài)規(guī)劃算法的核心之處。

　　確定了動(dòng)態(tài)規(guī)劃的這三要素，整個(gè)求解過(guò)程就可以用一個(gè)最優(yōu)決策表來(lái)描述，最優(yōu)決策表是一個(gè)二維表，其中行表示決策的階段，列表示問(wèn)題狀態(tài)，表格需要填寫的數(shù)據(jù)一般對(duì)應(yīng)此問(wèn)題的在某個(gè)階段某個(gè)狀態(tài)下的最優(yōu)值（如最短路徑，最長(zhǎng)公共子序列，最大價(jià)值等），填表的過(guò)程就是根據(jù)遞推關(guān)系，從1行1列開(kāi)始，以行或者列優(yōu)先的順序，依次填寫表格，最后根據(jù)整個(gè)表格的數(shù)據(jù)通過(guò)簡(jiǎn)單的取舍或者運(yùn)算求得問(wèn)題的最優(yōu)解。

　　二、貪心算法簡(jiǎn)介

　　貪心算法（又稱貪婪算法）是指，在對(duì)問(wèn)題求解時(shí)，總是做出在當(dāng)前看來(lái)是最好的選擇。也就是說(shuō)，不從整體最優(yōu)上加以考慮，他所做出的是在某種意義上的局部最優(yōu)解。貪心算法不是對(duì)所有問(wèn)題都能得到整體最優(yōu)解，關(guān)鍵是貪心策略的選擇，選擇的貪心策略必須具備無(wú)后效性，即某個(gè)狀態(tài)以前的過(guò)程不會(huì)影響以后的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)。

　　1.基本要素

　　貪心選擇

　　貪心選擇是指所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)的選擇，即貪心選擇來(lái)達(dá)到。這是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。貪心選擇是采用從頂向下、以迭代的方法做出相繼選擇，每做一次貪心選擇就將所求問(wèn)題簡(jiǎn)化為一個(gè)規(guī)模更小的子問(wèn)題。對(duì)于一個(gè)具體問(wèn)題，要確定它是否具有貪心選擇的性質(zhì)，我們必須證明每一步所作的貪心選擇最終能得到問(wèn)題的最優(yōu)解。通?？梢允紫茸C明問(wèn)題的一個(gè)整體最優(yōu)解，是從貪心選擇開(kāi)始的，而且作了貪心選擇后，原問(wèn)題簡(jiǎn)化為一個(gè)規(guī)模更小的類似子問(wèn)題。然后，用數(shù)學(xué)歸納法證明，通過(guò)每一步貪心選擇，最終可得到問(wèn)題的一個(gè)整體最優(yōu)解。

　　最優(yōu)子結(jié)構(gòu)

　　當(dāng)一個(gè)問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解時(shí)，稱此問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。運(yùn)用貪心策略在每一次轉(zhuǎn)化時(shí)都取得了最優(yōu)解。問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用貪心算法或動(dòng)態(tài)規(guī)劃算法求解的關(guān)鍵特征。貪心算法的每一次操作都對(duì)結(jié)果產(chǎn)生直接影響，而動(dòng)態(tài)規(guī)劃則不是。貪心算法對(duì)每個(gè)子問(wèn)題的解決方案都做出選擇，不能回退；動(dòng)態(tài)規(guī)劃則會(huì)根據(jù)以前的選擇結(jié)果對(duì)當(dāng)前進(jìn)行選擇，有回退功能。動(dòng)態(tài)規(guī)劃主要運(yùn)用于二維或三維問(wèn)題，而貪心一般是一維問(wèn)題。

　　2.算法特性

　　貪婪算法可解決的問(wèn)題通常大部分都有如下的特性：

　　隨著算法的進(jìn)行，將積累起其它兩個(gè)集合：一個(gè)包含已經(jīng)被考慮過(guò)并被選出的候選對(duì)象，另一個(gè)包含已經(jīng)被考慮過(guò)但被丟棄的候選對(duì)象。

　　有一個(gè)函數(shù)來(lái)檢查一個(gè)候選對(duì)象的集合是否提供了問(wèn)題的解答。該函數(shù)不考慮此時(shí)的解決方法是否最優(yōu)。

　　還有一個(gè)函數(shù)檢查是否一個(gè)候選對(duì)象的集合是可行的，也即是否可能往該集合上添加更多的候選對(duì)象以獲得一個(gè)解。和上一個(gè)函數(shù)一樣，此時(shí)不考慮解決方法的最優(yōu)性。

　　選擇函數(shù)可以指出哪一個(gè)剩余的候選對(duì)象最有希望構(gòu)成問(wèn)題的解。

　　最后，目標(biāo)函數(shù)給出解的值。

　　為了解決問(wèn)題，需要尋找一個(gè)構(gòu)成解的候選對(duì)象集合，它可以優(yōu)化目標(biāo)函數(shù)，貪婪算法一步一步的進(jìn)行。起初，算法選出的候選對(duì)象的集合為空。接下來(lái)的每一步中，根據(jù)選擇函數(shù)，算法從剩余候選對(duì)象中選出最有希望構(gòu)成解的對(duì)象。如果集合中加上該對(duì)象后不可行，那么該對(duì)象就被丟棄并不再考慮；否則就加到集合里。每一次都擴(kuò)充集合，并檢查該集合是否構(gòu)成解。如果貪婪算法正確工作，那么找到的第一個(gè)解通常是最優(yōu)的。

　　三、動(dòng)態(tài)規(guī)劃算法和貪心算法的區(qū)別與聯(lián)系

　　背景介紹：這兩種算法都是選擇性算法，就是從一個(gè)候選集合中選擇適當(dāng)?shù)脑丶尤虢饧稀?/p>

　　貪心算法的選擇策略即貪心選擇策略，通過(guò)對(duì)候選解按照一定的規(guī)則進(jìn)行排序，然后就可以按照這個(gè)排好的順序進(jìn)行選擇了，選擇過(guò)程中僅需確定當(dāng)前元素是否要選取，與后面的元素是什么沒(méi)有關(guān)系。

　　動(dòng)態(tài)規(guī)劃的選擇策略是試探性的，每一步要試探所有的可行解并將結(jié)果保存起來(lái)，最后通過(guò)回溯的方法確定最優(yōu)解，其試探策略稱為決策過(guò)程。

　　主要不同：兩種算法的應(yīng)用背景很相近，針對(duì)具體問(wèn)題，有兩個(gè)性質(zhì)是與算法選擇直接相關(guān)的，最優(yōu)子結(jié)構(gòu)性質(zhì)和貪心選擇性質(zhì)。

　　最優(yōu)子結(jié)構(gòu)性質(zhì)是選擇類最優(yōu)解都具有的性質(zhì)，即全優(yōu)一定包含局優(yōu)，上一次選擇最短路線的例子已經(jīng)對(duì)此作了說(shuō)。

　　當(dāng)時(shí)我們也提到了貪心選擇性質(zhì)，滿足貪心選擇性質(zhì)的問(wèn)題可用貪心算法解決，不滿足貪心選擇性質(zhì)的問(wèn)題只能用動(dòng)態(tài)規(guī)劃解決?？梢?jiàn)能用貪心算法解決的問(wèn)題理論上都可以利用動(dòng)態(tài)規(guī)劃解決，而一旦證明貪心選擇性質(zhì)，用貪心算法解決問(wèn)題比動(dòng)態(tài)規(guī)劃具有更低的時(shí)間復(fù)雜度和空間復(fù)雜度。

　　貪心算法：

　　1.貪心算法中，作出的每步貪心決策都無(wú)法改變，因?yàn)樨澬牟呗允怯缮弦徊降淖顑?yōu)解推導(dǎo)下一步的最優(yōu)解，而上一部之前的最優(yōu)解則不作保留。

　　2.貪心法正確的條件是：每一步的最優(yōu)解一定包含上一步的最優(yōu)解。

　　動(dòng)態(tài)規(guī)劃算法：

　　1.全局最優(yōu)解中一定包含某個(gè)局部最優(yōu)解，但不一定包含前一個(gè)局部最優(yōu)解，因此需要記錄之前的所有最優(yōu)解

　　2.動(dòng)態(tài)規(guī)劃的關(guān)鍵是狀態(tài)轉(zhuǎn)移方程，即如何由以求出的局部最優(yōu)解來(lái)推導(dǎo)全局最優(yōu)解

　　3.邊界條件：即最簡(jiǎn)單的，可以直接得出的局部最優(yōu)解

　　所謂貪心選擇性質(zhì)是指所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)的選擇，即貪心選擇來(lái)達(dá)到。這是利用貪心算法求解最優(yōu)解的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。

　　在貪心算法中，作出的每步貪心決策都無(wú)法改變，因?yàn)樨澬牟呗允怯缮弦徊降淖顑?yōu)解推導(dǎo)下一步的最優(yōu)解，而上一部之前的最優(yōu)解則不作保留。并且，每一步的最優(yōu)解一定包含上一步的最優(yōu)解。

　　而在動(dòng)態(tài)規(guī)劃算法中，全局最優(yōu)解中一定包含某個(gè)局部最優(yōu)解，但不一定包含前一個(gè)局部最優(yōu)解，因此需要記錄之前的所有最優(yōu)解。動(dòng)態(tài)規(guī)劃的關(guān)鍵是狀態(tài)轉(zhuǎn)移方程，即如何由以求出的局部最優(yōu)解來(lái)推導(dǎo)全局最優(yōu)解。也就是說(shuō)，把一個(gè)復(fù)雜問(wèn)題分解成一塊一塊的小問(wèn)題，每一個(gè)問(wèn)題得到最優(yōu)解，再?gòu)倪@些最優(yōu)解中獲取更優(yōu)的答案。

?