动态规划 入门学习
動(dòng)態(tài)規(guī)劃
- 引言
- 問(wèn)題引入?
對(duì)于一個(gè)2×2的表格，從左上角走到右下角，過(guò)程只可以向右或向下移動(dòng)，共有6種方式（如圖），那么，對(duì)于一個(gè)10×10的表格呢？? - 遞歸解法
- n設(shè)坐標(biāo)以左上角為（0，0），向右記為R，為x軸的增方向；向下記為D，為y軸的增方向。當(dāng)前坐標(biāo)為C，表格的寬=高=S。
- 從（0，0）開(kāi)始，我們有兩種選擇，R和D。
- 如果第一步選擇R時(shí)，C=（1，0），此時(shí)又有兩種選擇，R和D，也就是說(shuō)，與第一步是一樣的。
- 同理，如果第一步選擇的是D，也與第一步一致。
- 顯然，這是一個(gè)遞歸的過(guò)程。邊界條件就是當(dāng)C的坐標(biāo)到達(dá)（S-1，S-1)。
- 因此：?
static const int gridSize = 10;int Recursivity_GetRoutes(int x, int y) {int count = 0;if (x < gridSize)count += Recursivity_GetRoutes(x + 1, y);if (y < gridSize)count += Recursivity_GetRoutes(x, y + 1);if (x == gridSize && y == gridSize)return 1;return count; }
- 更高效的解法?
上述的程序是針對(duì)10×10的表格，它運(yùn)行的不算慢，所以我們?cè)賹⒈砀竦拇笮》?#xff0c;測(cè)試下它的運(yùn)行時(shí)間。通過(guò)在一臺(tái)普通的計(jì)算機(jī)上測(cè)試，表格為20×20時(shí)，程序運(yùn)行超過(guò)了30分鐘（具體時(shí)間有興趣的可以測(cè)試），為什么會(huì)這么慢呢？?
我們知道，遞歸的過(guò)程會(huì)消耗一定的時(shí)間，但是也不足以將程序拖到運(yùn)行30分鐘之久。因此我們?nèi)”砀裰械囊粋€(gè)點(diǎn)來(lái)分析，拿P點(diǎn)來(lái)說(shuō)，到達(dá)這個(gè)點(diǎn)有下圖中的路徑：?
我們看到，到達(dá)P點(diǎn)之后，這個(gè)點(diǎn)到終點(diǎn)的路徑數(shù)是固定的（如圖粉線(xiàn)所示），然而，遞歸調(diào)用中為用紅線(xiàn)到達(dá)P和藍(lán)線(xiàn)到達(dá)P分別計(jì)算了一次。?
因此我們需要一個(gè)備忘錄，或者說(shuō)一個(gè)哈希表，來(lái)保存以前計(jì)算過(guò)的值，而且，嘗試用迭代代替遞歸又能進(jìn)一步增加效率和運(yùn)行時(shí)的安全性。?
注意觀察會(huì)發(fā)現(xiàn)一個(gè)重要的性質(zhì)：?
因此，我們決定采用一個(gè)自底向上的，帶有備忘錄的迭代的解法：?
long long Dp_GetRoutes(){long long arr[21][21] = {0};for(int i = 0; i < 21; ++i)arr[i][20] = 1, arr[20][i] = 1;for(int i = 19; i >= 0; --i)for(int j = 19; j >= 0; --j){arr[i][j] = arr[i + 1][j] + arr[i][j + 1];}return arr[0][0];} 當(dāng)然，對(duì)于這個(gè)問(wèn)題，有一個(gè)手算的方法，為了走到終點(diǎn)，必然會(huì)向右走20步，向下走20步。它們的全排列共有40!種。?
又因?yàn)?#xff0c;20個(gè)相同的R及D進(jìn)行全排列是沒(méi)意義的，所以需要除以(20!×20!）。?
結(jié)果為40! / (20!×20!）。
- 問(wèn)題引入?
- 動(dòng)態(tài)規(guī)劃
- 定義?
動(dòng)態(tài)規(guī)劃(dynamic programming)是運(yùn)籌學(xué)的一個(gè)分支，是求解決策過(guò)程最優(yōu)化的數(shù)學(xué)方法。20世紀(jì)50年代初美國(guó)數(shù)學(xué)家R.E.Bellman等人在研究多階段決策過(guò)程的優(yōu)化問(wèn)題時(shí)，提出了著名的最優(yōu)化原理，把多階段過(guò)程轉(zhuǎn)化為一系列單階段問(wèn)題，利用各階段之間的關(guān)系，逐個(gè)求解，創(chuàng)立了解決這類(lèi)過(guò)程優(yōu)化問(wèn)題的新方法——?jiǎng)討B(tài)規(guī)劃。 - 特征
- 最優(yōu)子結(jié)構(gòu)
- 如果問(wèn)題的一個(gè)(最優(yōu))解中，包含了子問(wèn)題的(最優(yōu))解，則該問(wèn)題具有最優(yōu)子結(jié)構(gòu)。
- 結(jié)合引言中的例子，從底層開(kāi)始迭代，比如取一個(gè)點(diǎn)，坐標(biāo)為（x,y），那么，從這個(gè)點(diǎn)到終點(diǎn)的所有路徑的總和就等于（x+1,y）到終點(diǎn)的所有路徑和加上(x,y+1)到終點(diǎn)的所有路徑和。
- 證明最優(yōu)子結(jié)構(gòu)可以使用“剪切粘貼”的方法。在后面討論誤用動(dòng)態(tài)規(guī)劃時(shí)的最短路時(shí)應(yīng)用此方法。
- 重疊子問(wèn)題
- 用來(lái)解決原問(wèn)題的算法會(huì)反復(fù)地解同樣的子問(wèn)題，而不是總產(chǎn)生新的問(wèn)題。
- 就引言中的例子而言，隨著迭代的進(jìn)行，總會(huì)遇到相同的子問(wèn)題，因?yàn)槲覀冏隽藗渫?#xff0c;因此這些問(wèn)題只被計(jì)算一次。
- 最優(yōu)子結(jié)構(gòu)
- 提防誤用
- 動(dòng)態(tài)規(guī)劃中的子問(wèn)題一定是相互獨(dú)立的，一個(gè)子問(wèn)題中的解不會(huì)影響其它子問(wèn)題的解。比如將點(diǎn)(x,y)到終點(diǎn)的路徑分割為從(x+1,y)到終點(diǎn)的所有路徑加上從(x,y+1)到終點(diǎn)的所有路徑。
- 考慮下圖中的最短路和最長(zhǎng)路徑：?
如果需要計(jì)算q到t的最短路徑，可以將問(wèn)題從r或者s處劃分開(kāi)，具體在哪里劃分取決于r到t的路徑和s到t的路徑誰(shuí)短。這樣問(wèn)題的兩個(gè)部分是獨(dú)立的。?
如果需要計(jì)算q到t的最長(zhǎng)路徑，考慮從r處分開(kāi)子問(wèn)題，那么q到r的最長(zhǎng)路徑為q->s->t->r，r到t的最長(zhǎng)路徑顯然是r->q->s->t，合并二者，得到q->s->t->r->q->s->t，顯然是錯(cuò)誤的。 - 兩種路徑產(chǎn)生很大差別，原因是，最長(zhǎng)路徑的子問(wèn)題不獨(dú)立，選定了一個(gè)子問(wèn)題的解之后，它所使用的點(diǎn)不應(yīng)被另一個(gè)子問(wèn)題再使用。
- 實(shí)際上，最長(zhǎng)路徑問(wèn)題是NP完全的，也就是說(shuō)，無(wú)法在多項(xiàng)式時(shí)間（一個(gè)問(wèn)題的計(jì)算時(shí)間m(n)不大于問(wèn)題大小n的多項(xiàng)式倍數(shù)）得到解決。
- 定義?
- 典型動(dòng)態(tài)規(guī)劃問(wèn)題舉例
- 最大取值?
問(wèn)題：?
從下面的三角的頂端，每次只能移動(dòng)到下一行的且與之臨近的點(diǎn)上，其最大值是（紅色表示路徑）：3 + 7 + 4 + 9 = 23。?
那么，對(duì)于以下的三角呢？?
分析：同樣，我們從三角的倒數(shù)第二層開(kāi)始分析，假如，此時(shí)我們?cè)谧钭筮叺?3上，按題意，此時(shí)只有兩種選擇，04和62，顯然，為了得到最大值，我們會(huì)選擇62，第二行的其余點(diǎn)也如此選擇。?
接著，我們上升一層，在91上，為了得到最大值，我們會(huì)選擇63和66。?
顯然這是個(gè)動(dòng)態(tài)規(guī)劃的問(wèn)題，在倒數(shù)第N層到底層內(nèi)這個(gè)問(wèn)題(最優(yōu)子結(jié)構(gòu))是最優(yōu)的。?
當(dāng)三角只有一層時(shí)，最大取值=底層點(diǎn)的值。?
static inline int Max(int x, int y){return (x > y) ? x : y; }static int arr[][15] = {/*layer1*/ { 75 },/*layer2*/ { 95, 64 },/*layer3*/ { 17, 47, 82 },/*layer4*/ { 18, 35, 87, 10 },/*layer5*/ { 20, 4, 82, 47, 65 },/*layer6*/ { 19, 1, 23, 75, 3, 34 },/*layer7*/ { 88, 2, 77, 73, 7, 63, 67 },/*layer8*/ { 99, 65, 4, 28, 6, 16, 70, 92 },/*layer9*/ { 41, 41, 26, 56, 83, 40, 80, 70, 33 },/*layer10*/ { 41, 48, 72, 33, 47, 32, 37, 16, 94, 29 },/*layer11*/ { 53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14 },/*layer12*/ { 70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57 },/*layer13*/ { 91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48 },/*layer14*/ { 63, 66, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31 },/*layer15*/ { 4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23 }};int Dp_GetMaxValueThroughTriangle(){const int limit = 15 - 1;for(int layer = limit; layer != 0; --layer){const int& layerNumberCount = layer;for(int numberIndex = 0; numberIndex < layerNumberCount; ++numberIndex)arr[layer - 1][numberIndex] += Max(arr[layer][numberIndex], arr[layer][numberIndex + 1]);}return arr[0][0];} - 錢(qián)幣組合方式?
假設(shè)我們有無(wú)限多的1元，2元，5元，10元，20元，50元，100元，200元的錢(qián)幣，那么為了組合成一個(gè)200元的錢(qián)幣，共有多少種組合方式？?
比如說(shuō)：?
200 = 1×100+1×50+2×20+1×5+1×2+3×1。?
因?yàn)橛辛?元的錢(qián)幣，這就使我們組成的任何不足200的數(shù)字可以整合為200。?
為了說(shuō)明問(wèn)題，我們來(lái)觀察這樣的一個(gè)類(lèi)似的小問(wèn)題，用1元，2元，5元來(lái)組成5元。?
如果只允許用1元，那么顯然只有一種方案：1×5。?
如果允許用1元和2元，那么，5元的組合方式有，1×5，2+1×3，2×2+1。增加了兩種方案。?
如果允許用1，2，5元，那么有：?
1×5，2+1×3，2×2+1，5×1。?
我們假設(shè)組成0元的方式有一種，那么，可選的最大幣值為x，那么：?
當(dāng)x=1時(shí)：?
當(dāng)x=2時(shí)：?
當(dāng)x=5時(shí)：?
從這個(gè)問(wèn)題總結(jié)出：當(dāng)目標(biāo)幣值為Y，現(xiàn)在可用的最大幣值為1，2，5……X(X ≤Y)，Z是小于X的最大幣值，組成Y的方式為f(Y)那么?
f(Y) = f(Y-X) + f(X-Z)?
比如說(shuō)，對(duì)于Y=3，X=2，可知Z=1，所以，?
f(3) = f(3-2) + f(2 - 1) = f(1) + f(1) = 1 + 1 = 2。特別地，f(0) = 1。?
static int faceValue[] = {1, 2, 5, 10, 20, 50, 100, 200}; static const size_t factValueCount = 8;int Dp_GetCountOfWaysCan200BeMadeUp(){// Dynamic Programming.const int destination = 200;int waysCount[destination + 1] = { 0 };waysCount[0] = 1;for(int indexCoin2Give = 0; indexCoin2Give < factValueCount; ++indexCoin2Give)for(int indexValueNeed2Pay = faceValue[indexCoin2Give]; indexValueNeed2Pay <= destination; ++indexValueNeed2Pay)waysCount[indexValueNeed2Pay] += waysCount[indexValueNeed2Pay - faceValue[indexCoin2Give]];return waysCount[200];} 由于數(shù)據(jù)量不大，也可以用遞歸解決或者枚舉法解決。?
int Recursivity_GetCountOfWaysCan200BeMadeUp(int money, int maxCoin){int coins[8] = {200, 100, 50, 20, 10, 5, 2, 1};int result = 0;if(maxCoin == 7) // Only coins[1] = 1 is available.return 1;for(int i = maxCoin; i < 8; i++){if (money - coins[i] == 0)//Done.result += 1;if (money - coins[i] > 0) result += Recursivity_GetCountOfWaysCan200BeMadeUp(money - coins[i], i);// else, money < coins[i], continue. }return result;}///int BruteFource_GetCountOfWays(){int ways = 0;const int dest = 200;for(int a = dest; a >= 0; a -= 200) //a個(gè)200。for(int b = a; b >= 0; b -= 100) //b個(gè)100。for(int c = b; c >= 0; c -= 50) //c個(gè)50。for(int d = c; d >= 0; d -= 20) //d個(gè)20。for(int e = d; e >= 0; e -= 10) //e個(gè)10。for(int f = e; f >= 0; f -= 5) //f個(gè)5。for(int g = f; g >= 0; g -= 2) //g個(gè)2。++ways;return ways;}
- 最大取值?
- 活動(dòng)安排?
假設(shè)有11個(gè)活動(dòng)，需要占用同一個(gè)資源(比如說(shuō)一個(gè)會(huì)議室)，他們的活動(dòng)時(shí)間按照結(jié)束時(shí)間遞增的順序，如下表所示：?
如果兩個(gè)活動(dòng)不會(huì)同時(shí)占用一樣資源，那么稱(chēng)他們是相容的。那么，共有最多可以有多少個(gè)活動(dòng)相容？?
n假設(shè)S(i,j)表示一個(gè)集合，活動(dòng)記為a， S(i,j)之中的元素代表活動(dòng)，并且所有的活動(dòng)都在a_i結(jié)束之后開(kāi)始，在a_j開(kāi)始之前結(jié)束。假設(shè)活動(dòng)的編號(hào)從1開(kāi)始，到n-1結(jié)束，定義哨兵事件，a_0為最開(kāi)始的事件，a_n為最結(jié)束的事件。記c[i,j]為|S(i,j)|。?
簡(jiǎn)言之，如果一個(gè)活動(dòng)a_k是S(i,j)中的一個(gè)合法的活動(dòng)，那么c[i,j]為k取(i,j)中的各個(gè)值，并通過(guò)c[i,k]+1+c[k,j]得到的最大結(jié)果。?
#include <vector> #include <map> #include <iostream>const int FirstActivityInitializer = 0; const int LastActivityInitializer = 2147483647; //INT_MAX;struct Activity{Activity(int b = -1, int e = -1) : tBeg(b), tEnd(e) {}operator int(){ return tEnd; }int tBeg;int tEnd;};typedef std::vector<Activity> ActivityTable; typedef std::map<int, int> HashTable; typedef std::map<int, size_t> ResultCollector;const Activity firstActivity(FirstActivityInitializer, FirstActivityInitializer); const Activity lastActivity(LastActivityInitializer, LastActivityInitializer);static inline int MakeKey(int l, int h){return ((h << 16) | l);}static inline void output(ResultCollector& result, int from, int to){int divider = result[MakeKey(from, to)];if(divider == 0){ //New pair (MakeKey(from, to), 0) has been inserted into ResultCollector, remove it.result.erase(MakeKey(from, to));return;}std::cout << divider << " ";output(result, from, divider);output(result, divider, to);}static inline void OutputResult(const ResultCollector& result, int from, int to){std::cout << "Optional: ";output(const_cast<ResultCollector&>(result), from, to);std::cout << std::endl;}static int ActivitySelector(const ActivityTable& act){ActivityTable activities(1, firstActivity);activities.insert(activities.end(), act.begin(), act.end());activities.push_back(lastActivity);HashTable hashTable;ResultCollector collector;size_t actCount = activities.size() - 1;for(size_t subLen = 1; subLen < actCount; ++subLen)for(size_t first = 0; first < actCount - subLen; ++first){size_t last = first + subLen + 1;for(size_t cur = first + 1; cur < last; ++cur)if(activities[cur].tBeg >= activities[first].tEnd && activities[cur].tEnd <= activities[last].tBeg&& hashTable[MakeKey(first, cur)] + 1 + hashTable[MakeKey(cur, last)] > hashTable[MakeKey(first, last)]){collector[MakeKey(first, last)] = cur;hashTable[MakeKey(first, last)] = hashTable[MakeKey(first, cur)] + 1 + hashTable[MakeKey(cur, last)];}}OutputResult(collector, 0, actCount);return hashTable[MakeKey(0, activities.size() - 1)];}int Dp_ActivitySelector(){ActivityTable al;al.push_back(Activity(1, 4));al.push_back(Activity(3, 5));al.push_back(Activity(0, 6));al.push_back(Activity(5, 7));al.push_back(Activity(3, 8));al.push_back(Activity(5, 9));al.push_back(Activity(6, 10));al.push_back(Activity(8, 11));al.push_back(Activity(8, 12));al.push_back(Activity(2, 13));al.push_back(Activity(12, 14));return ActivitySelector(al);} - 題外話(huà)
- 前面我們假設(shè)活動(dòng)按照結(jié)束時(shí)間遞增的順序排列，其實(shí)我們也可以不要這個(gè)限制，而在活動(dòng)選擇之前主動(dòng)進(jìn)行排序。觀察活動(dòng)結(jié)束時(shí)間的選擇區(qū)間，顯然是0～24的，那么，用計(jì)數(shù)排序是很合適的。下面的計(jì)數(shù)排序是兼容STL的：?
#include <algorithm> #include <cassert>template <class RanIt> static void count_sort(RanIt first, RanIt last, int upper){typedef std::iterator_traits<RanIt>::value_type value_t;typedef std::iterator_traits<RanIt>::difference_type distance_t;distance_t dis = std::distance(first, last);std::vector<value_t> tmp(first, last);RanIt dest = tmp.begin();int *host = new int[upper];//fill temporary range with default value.std::fill(host, host + upper, 0);//host[i]: count of values which are equal to i. eg: host[2] == 1, //means there are two '2'.for(int i = 0; i < dis; ++i)++host[*(first + i)];//host[i]: count of values which are not greater than i. eg: host[2] = 3,//means there are 3 numbers less or equal to 2.for(int i = 1; i < upper; ++i)host[i] += host[i - 1];//place the number backwardly to keep this algorithm stable.for(int i = (--dis); i >= 0; --i){value_t temp = *(first + i);dest[host[temp] - 1] = temp, --host[temp];}//copy result back into the input range. std::copy(tmp.begin(), tmp.end(), first);//clean up. delete host;}template <class RanIt> inline void CountSort(RanIt first, RanIt last, int upper){ //this algorithm use both the index and the value of an array to represent data.if(*(std::min_element(first, last)) >= 0 && *(std::max_element(first, last)) <= upper)count_sort(first, last, ++upper);elseassert(false);} - 當(dāng)然，用動(dòng)態(tài)規(guī)劃解決活動(dòng)選擇問(wèn)題是可以的，但是它還有另一個(gè)重要的性質(zhì)，如果已經(jīng)選定了活動(dòng)x，那么，下一個(gè)被選擇的活動(dòng)一定是與x相容且結(jié)束時(shí)間最早的活動(dòng)y。證明：?
假設(shè)下一個(gè)選擇的活動(dòng)為z且z≠y，那么，將z換為y，因?yàn)閥是最早結(jié)束的活動(dòng)，并且y與x相容，所以y的結(jié)束時(shí)間必然≤z的結(jié)束時(shí)間，這就保證了它不與已選擇的其他活動(dòng)沖突。所以y在這個(gè)活動(dòng)集中是合理的。?
有了上述的性質(zhì)，我們假設(shè)第一個(gè)活動(dòng)是a_0,它的結(jié)束時(shí)間為0，選擇下一個(gè)時(shí)，選擇開(kāi)始時(shí)間大于0且結(jié)束時(shí)間最早的，因?yàn)榛顒?dòng)的結(jié)束時(shí)間已經(jīng)按照遞增排序，因此選擇的是a_1，按照這個(gè)規(guī)則，同理，下一個(gè)選擇的是a_4，然后是a_8，最后是a_11。?
上述方法稱(chēng)為貪心算法，每次選取當(dāng)前看來(lái)最優(yōu)的解，從而獲得全局的最優(yōu)解。?
貪心算法是一個(gè)與動(dòng)態(tài)規(guī)劃類(lèi)似但是較動(dòng)態(tài)規(guī)劃更為簡(jiǎn)潔但卻更容易誤用的算法。
- 前面我們假設(shè)活動(dòng)按照結(jié)束時(shí)間遞增的順序排列，其實(shí)我們也可以不要這個(gè)限制，而在活動(dòng)選擇之前主動(dòng)進(jìn)行排序。觀察活動(dòng)結(jié)束時(shí)間的選擇區(qū)間，顯然是0～24的，那么，用計(jì)數(shù)排序是很合適的。下面的計(jì)數(shù)排序是兼容STL的：?
轉(zhuǎn)載于:https://www.cnblogs.com/tham/p/6827473.html
總結(jié)
- 上一篇： 一天一道算法题--5.30---递归
- 下一篇： tableView练习 -- QQ好友列