现在的位置: 首页 > 综合 > 正文

动态规划(1)总述

2018年02月20日 ⁄ 综合 ⁄ 共 7889字 ⁄ 字号 评论关闭

1 Dynamic Programming

The most widely example we use Dynamic Programming in our life is find the shortest/quickest path between two places.So what is the Dynamic Programming?


Dynamic programming refers to simplifying a complicated problem by breaking it down into simpler subproblems in a recursive manner. If subproblems can be nested recursively inside larger
problems, so that dynamic programming methods are applicable,then there is a relation between the value of the larger problem and the values of the subproblems. In computer science, a problem that can be broken down recursively is said to have optimal substructure. 动态规划适用于最优化问题,即要做出一组选择以达到一个最优解。在做选择的同时,经常出现同样形式的子问题,关键技术是存储这些字问题每一个的解,以备重复出现。

There are two key attributes that a problem must have in order for dynamic programming to be applicable:optimal substructure(最优子结构)
and overlapping subproblems(重叠子问题)
. If a problem can be solved by combining optimal solutions to non-overlapping subproblems, the strategy is called "divide and conquer". This is why mergesort and quicksort are not
classified as dynamic programming problems.

(Note:why mergesort and quicksort are not classified as dynamic programming problems?

The key words here are "overlapping subproblems" and "optimal substructure". When you execute quicksort or mergesort, you are recursively breaking down your array into smaller pieces
that do not overlap. You never operate over the same elements of the original array twice during any given level of the recursion.This means there is no opportunity to re-use previous calculations. On the other hand,many problems using dynamic
programming involve performing the same calculations overlapping subsets, and have the useful characteristic that an optimal solution to a subproblem can be re-used when computing the optimal solution to a larger problem.
)

Optimal Substructure

Optimal substructure means that the solution to a given optimization problem can be obtained by the combination of
optimal solutions to its subproblems(
如果问题的一个最优解中包含了子问题的最优解,则该问题具有最优子结构).Consequently, the first step towards devising a dynamic programming solution is to check whether the problem
exhibits such optimal substructure. Such optimal substructures are usually described by means of recursion
. For example, given a graph G=(V,E),
the shortest path 
p from a vertex u to a vertex vexhibits
optimal substructure: take any intermediate vertex 
w on this shortest path p. If is
truly the shortest path, then the path 
p1 from u to w and p2 from w to v are
indeed the shortest paths between the corresponding vertices (by the simple cut-and-paste argument described in Introduction to Algorithms
). Hence, one can easily formulate the solution
for finding shortest paths in a recursive manner.

Overlapping subproblems

Overlapping subproblems means that the space of subproblems must be small, that is,
any recursive algorithm solving the problem should solve the same subproblems over and over, rather than generating new subproblems. For example, consider the recursive formulation for generating the Fibonacci series: 
Fi = Fi−1 + Fi−2,
with base case 
F1 = F2 = 1. Then F43F42 + F41,
and 
F42 = F41 + F40.
Now 
F41 is being solved in the recursive subtrees of bothF43 as
well as 
F42. Even though the total number of subproblems is actually small (only 43 of them), we end up solving the same problems over and over if
we adopt a naive recursive solution such as this. Dynamic programming takes account of this fact and solves each subproblem only once.

Steps of Solving Problems with Dynamic Progarmming

1 描述最优子结构

2 递归定义最优解的值

3 按自底向上方式计算最优解的值

4 由计算出的结果构造一个最优解

详细步骤

1 描述最优子结构

在寻找最优子结构时,可以遵循一种共同的模式:

1)问题的一个解可以使做一个选择。

2)假设对一个给定的问题,已知是一个可以导致最优解的选择。不必关心如何确定这个选择,尽管假设是已知的。

3)在已知这个选择后,要确定哪些子问题会随之发生,以及如何最好地描述所得到的子问题空间。

4)利用一种“剪贴”技术,来证明在问题的一个最优解中,使用的子问题的解本身也必须是最优的。通过假设每一个子问题的解都不是最优解,然后导出矛盾。

如何描述子问题空间?可以遵循这样一条有效的经验准则,就是尽量保持这个空间简单,然后在需要时再扩充它。


2 递归定义最优解的值

注意定义递归的边界条件

如《算法导论》中的装配线调度问题的递归解公式为:

最终目标是确定底盘通过工厂的所有路线的最快时间,设为f*,令fi[j]表示一个底盘从起点到装配站Si,j的最快时间,则f* = min(f1[n]+x1,f2[n]+x2)。
1)f1[j]
当j=1时: f1[1] = e1+a1。
当j>1时:f1[j] = min(f1[j-1]+a1,j,f2[j-1]+t2,j-1+a1,j),
2)f2[j]
当j=1时: f2[1] = e2+a2。
当j>1时:f2[j] = min(f2[j-1]+a2,j,f1[j-1]+t1,j-1+a2,j)。		

3 按自底向上方式计算最优解的值

1)在实际实现动态规划算法时,我们又正过来解决问题,也就是采用自底向上方式计算。

如装配线调度上面的公式的伪代码如下:

DynamitcPrograming(a,t,e,x,n){
  //边界条件(初始值)
  f1[1]=e1+a1;
  f2[1]=e2+a2;
  
  //自底向上循环求解,最优解记录在f1[n]和f2[n]中
  for(j=2;j<=n;j++){
      //求f1[j]
      if(f1[j-1]+a1[j]<=f2[j-1]+t2[j-1]+a1[j]){
	     f1[j]=f1[j-1]+a1[j];
		 l1[j]=1;   //同时在l1[j]中记录下子问题的选择,以便后期构造最优解
	  }//end if
	  else{
	     f1[j]=f2[j-1]+t2[j-1]+a1[j];
		 l1[j]=2;
	  }//end else
	  
	  //求f2[j]
	  if(f2[j-1]+a2[j]<=f1[j-1]+t1[j-1]+a2[j]){
	     f2[j]=f2[j-1]+a2[j];
		 l2[j]=1;   //同时在l1[j]中记录下子问题的选择,以便后期构造最优解
	  }//end if
	  else{
	     f2[j]=f1[j-1]+t1[j-1]+a2[j];
		 l2[j]=2;
	  }//end else
  }//end for
  
  //求最优解
  if(f1[n]<f2[n]){
     f*=f1[n]+x1;
	 l*=1;
  }//end if
  else{
     f*=f2[n]+x2;
	 l*=2;
  }//end else
} //end DynamitcPrograming(a,t,e,x,n)	

2)Memo 备忘录

动态规划有一种变形,它既有通常的动态规划方法的效率,又采用了一种自顶向下的策略,其思想是备忘(memoize)原问题的中间求解结果,这种方法可以优化低效的递归算法。By the way, dynamic
programming doesn't mean to convert a recursive code into an iterative code. You can also save the subresults into a variable if you want a recursive code. In this case the technique is called memoization.

      在实际应用中,如果所有的子问题都至少要被计算一次,则一个自底向上的动态规划算法通常要比一个自顶向下的做备忘录算法好处一个常数因子,因为前者无需递归的代价,而且维护表格的开销也小一些。如果子问题空间中的某些子问题根本没有必要求解,做备忘录方法有着只解哪些肯定要求解的子问题的优点。

4 由计算出的结果构造一个最优解

当只要求计算最优解的值时可以略去该步骤。当需要同时确定如何构造出最优解时,需要在步骤3中记录一些附加详细,来辅助构造最优解。

在实际应用中,我们通常把每一个子问题中所作的选择保存在一个表格中,这样在需要时,就不必根据已经存储下来的代价信息来重构这方面的信息了。

Bottom-up approach:

Once we formulate the solution to a problem recursively as in terms of its subproblems, we can try reformulating the problem in a bottom-up fashion: try
solving the subproblems first and use their solutions to build-on and arrive at solutions to bigger subproblems. This is also usually done in a tabular form by iteratively generating solutions to bigger and bigger subproblems by using the solutions to small
subproblems. For example, if we already know the values of 
F41 and F40,
we can directly calculate the value of 
F42.

动态规划算法时间复杂度

非正式地,一个动态规划算法的运行时间依赖于两个因素的乘积:子问题的总个数和每一个子问题中有多少种选择

2 Dynamic Programming Example

最优二叉查找树

3 Dynamic Programming vs. Divide and conquer(分治算法)

Both solve problems by dividing problems into sub-problems.

(1)   Dependent vs. independent

Divideand conquer works best when all subproblems are independent.

Dynamic programming is needed when subproblems are dependent.

Forexample, let S1= {ALPHABET}, and S2 = {HABITAT}.

Considerthe subproblem with S1’ = {ALPH}, S2’ = {HABI}. Then,


(2)   Solve the sub problem

Divide and conquer is best suited for the case when no “overlapping subproblems” are encountered.

Dynamic programming solves the sub problems only once and then stores it in table, whereas divide and conquer does more work on the overlapping subproblems and hence has more time consumption.

You may think of Dynamic Programming = recursion +re-use

(3) relationship

The relationship to the Divide and Conquer is that both algorithms rely on recursion. And some versions of them has this "multiple function call with the same parameter issue." Search
for "matrix chainmultiplication" and "longest common subsequence" for such examples where dynamic programming is needed to improve the T(n) of Divide and Conquer algorithm.

(4) good example to distinguish

A classic example to understand the difference would be to see both these approaches towards obtaining the nth fibonacci number(斐波纳契数列).








Appedix A golden section(or golden ratio)黄金分割



or it can be represented like this a/(a+b)=b/a=0.618

4、动态规划与贪心算法(Dynamic Programming & Greedy Algorithm)

4.1贪心算法介绍

贪心算法也是应用于最优化问题,该算法的思想是使所做的选择看起来都是当前最佳的,期望通过所做的局部最优选择来产生一个全局最优解。对许多问题来说,采用贪心算法可以比用动态规划算法更快地给出一个最优解。但是,不容易判断贪心法是否一定有效。

贪心算法具有贪心选择和最优化子结构两个关键特点。

贪心选择性质:一个全局最优解可以通过局部最优(贪心)选择来达到。即当考虑如何做选择时,我们只考虑对当前问题最的选择而不考虑子问题的结果。

4.2 贪心算法步骤

1)决定问题的最优子结构。将优化问题转换成这样的一个问题,即先做出选择,再解决剩下的一个子问题。

2)证明原问题总是有一个最优解是做贪心选择得到的(即当前最优),从而说明贪心选择的安全。

3)说明在做出贪心选择后,剩余的子问题具有这样的一个性质。即如果将子问题的最优解和我们所做的贪心选择联合起来,可以得出原问题的一个最优解。

4.3贪心算法应用

资源占用(《算法导论》上的活动选择问题),部分背包问题,Dijkstra最短路径,最小生成树,哈弗曼编码

4.4 动态规划与贪心算法

因为贪心算法与动态规划都利用了最与子结构,故人们往往会在贪心解足以解决问题的场合下,给出一个动态规划解,或者在需要动态规划的场合下使用贪心方法。具体见01背包问题(动态规划算法)和部分背包问题(贪心算法)-《算法导论》P229。

5 动态规划应用

动态规划(1)总述

动态规划(2)01背包问题

动态规划(3)饮料供货

动态规划(4)最大连续子串问题

动态规划(5)字符串相似度算法

动态规划(6)最长公共子串

Appedix B fibonacci number

斐波纳契数列(fibonacci number),又称黄金分割数列,指的是这样一个数列:1、1、2、3、5、8、13、21、……在数学上,斐波纳契数列以如下被以递归的方法定义:F0=0,F1=1,Fn=F(n-1)+F(n-2)(n>=2,n∈N*)在现代物理、准晶体结构、化学等领域,斐波纳契数列都有直接的应用。随着数列项数的增加,前一项与后一项之比越来越逼近黄金分割的数值0.6180339887..…


References

Introduction to Algorithms(算法导论)

http://en.wikipedia.org/wiki/Dynamic_programming#Examples%3a_Computer_algorithms

http://stackoverflow.com/questions/15596363/why-mergesort-is-not-dynamic-programming/15596650#15596650

Data Structure and Algorithm in Java 


抱歉!评论已关闭.