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 阅读(990)
评论(0) 编辑 收藏 引用 所属分类:
Algorithm