1.
動態規劃
Dynamic programming, like the divideand-conquer method, solves problems by combinging the solutions to subproblems.
1) 動態規劃適用于優化問題：從很多個解中找到最優解。(Dynamic progrmming is typicall applied to optimization problems.)
2) 適合用動態規劃解決的問題有兩個特征：
a. optimal substructure(http://en.wikipedia.org/wiki/Optimal_substructure)
用一個公式化的式子把它的solution表示出來會更清晰。
b. overlapping subproblems
如果不是overlapping subproblems，用分治法就可以解決了。動態規劃正是利用了重復子問題這個特性，將子問題的解存起來以便重復利用。
3) 如何劃分子問題
以問題 "An activity-selection problem"為例，CLRS劃分的方法和我的就不同。
注意：如果劃分的子問題之間存在依賴，那么該問題就不適合用動態規劃解決。（見CLRS 15.3 subtlties小節）
4) reconsturcting an optimal solution
用動態規劃有個問題就是在最后得到最優解時不能知道選擇的過程，有如下兩種方法可以解決：
a. 可以根據我們存下來的信息推導出前一步的選擇是什么，如：
diff.java
b. 記下選擇。
如果選擇較少可以采用方法a，否則選擇方法2比較好。這是一個時空權衡問題。
5）運用動態規劃有幾個需要注意的地方：
a. We must ensure that when we search for the correct place to spilt the product, we have considered all possible places so that we are sure of
having examined the optimal one.
b. The subproblems are independent.
c. 不要形成困定思維: 一想到動態規劃，馬上聯想到LCS，然后覺得動態規劃的表結構就是一個二維數組
6)思考
子問題有最優解，那么該問題得到的一定是最優解嗎？ 如果不是，那么什么情況下是全局最優解，什么情況是局部最優解?
以＜編程之美＞上的一個例子舉例說明如下 :(有時間再補上)
2. 貪心算法
A greedy algorithm always makes the choice that looks best at the moment. That is , it makes a locally optimal choce in the hope that chis choce will lead to a globally optimal solution.
貪心法能解決的問題，動態規劃基本都能解決。（CLRS 16.2 Nevertheless, beneath every greedy algorithm, ther is almost always a more cumbersome dynamic-progrmming solution）。
但是：For many optimization problems, using dynamic programming to determine the best choices is overkill; Simpler, more effiiect algorithms will do. (eg: greedy algorithm)
1）適合用貪心法解決的問題
必須要有Greedy-choice property : a globally optiaml solution can be arrivedat by making a locally optimal (greedy) choice.
如：Huffman編碼，最小生成樹
2）貪心法的一般步驟
a. 將原問題劃分為子2個子問題（非overlap的），此時就能用動態規劃求解了
b. 找到一個劃分點，讓其中一個子問題變為空，則只剩下一個子問題了，這就是貪心算法
3）使用貪心法時必須保證：
We must prove that a greedy choice at each step yields a golbally optimal solution, and this is where cleverness may be required.
這點也是最難的。所以有個問題“什么情況下，局部最優最終會產生全局最優的結果？”
4）適用貪心算法的問題有 greedy-choice propertty，需要找到一個貪心策略。
5）對于找不到全局最優解的問題（如NP問題），可以考慮貪心算法。
3. 動態規劃與分治法的比較
分治法適合于那些能被分解為獨立子問題的問題；動態規劃更適用于子問題之間不是獨立的，而是會share subproblems。動態規劃的這個特點得益于它把子問題的結果都保存在一個表中了（動態規劃的英文名字是Dynamic Programming，這里的Programming可理解為a tabular method(表格方法)），這樣就能少去重復子問題的計算。 所以動態規劃可以算作是分治法在overlapping 子問題里的一個優化（這個優化在程序中是常見的優化方法Memoization（http://en.wikipedia.org/wiki/Memoization））
4. 動態規劃與貪心法的比較
1) 相同點
a. 問題要有optimal substructure
A problem exhibits optimalsubstructure if an optimal solution to the problem contains within it optimal solutions to subproblems.
這是能用貪心法與動態規劃解答的問題的關鍵因素。
b. 都需要劃分子問題，但是劃分子問題的方式有些區別，見下面的不同點。
2）不同點
a. 劃分子問題
如果你把劃分的子問題有交集(overloapping subproblem)，這就很顯然地將你引入了動態規劃的思維，以"An activity-selection problem"舉例說明：
對于問題 "An activity-selection problem"，很容易就能想到動態規劃的解法
int select_activity(int *a, int n, int i)
{
if(i >=n )
return 0;
for(j= i + 1; j < n; j ++){
if(a[j].start >= a[i].end)
break;
}
int sum1 = select_activity(a, n, j) + 1; //select the ith activity
int sum2 = select_activity(a, n, i + 1); //not select the ith activity
if(sum1 > sum2)
return sum1;
else
return sum2;
}
但是如何將它轉化為貪心算法呢？
答案是：由這種方法是不易轉化為貪心法的。上面這種劃分子問題的方式表明了它更適合于動態規劃，就像在CLRS 383頁里說到的0-1背包問題：The problem formulated in this way gives rise to many over-lapping subproblems － a hallmark of dynamic programming.
b. 貪心法： make whaterver choice seems best a the moment and then solve the subproblem arising after the choice is made.
動態規劃：make a choice at each step, but the choice usually depends on the solutions to subproblems.
c. 貪心法：top-down fashinon
動態規劃：bottom-up manner
posted on 2011-08-24 20:51
hex108 閱讀(1019)
評論(0) 編輯 收藏 引用 所屬分類:
Algorithm