动态规划策略(dynamic programming strategy)是一种用于解决许多组合优化问题(combinatorial optimization problem)的有效方法。

 
 

动态规划

问题的解是一系列决策的结果,是一种算法设计方法。

Dynamic Programming is an algorithm design method that can be used when

the solution to a problem may be viewed as the result of a sequence of decisions

 
 

、优化原理 (Principle of optimality)

假设我们在解决一个问题,我们得作出一个序列的决策D1,D2,D3…,Dn,

如果这个序列是最优的,那么最后 k(1<k< n) 个决策也是最优的。

 
 

Suppose that in solving a problem, we have to make a sequence of

decisions D 1 , D 2 , …, D n . If this sequence is optimal, then the last k decisions, 1 < k < n must be optimal.

 
 

e.g. 最短路径问题

如果 i, i1 , i2 , …, j 是一个从i到j的最短路径

那么 i1 , i2 , …, j 一定是从i1到j的最短路径

 
 

 
 

 
 

二、如何使用动态规划

如果一个问题,可以被描述成一个多阶段图(multistage graph),那么这个问题就用动态规划方法解决。

In summary, if a problem can be described by a multistage graph, then it can be solved by dynamic programming.

解决步骤:

1、找到递推关系

2、通过一个多阶段图表示这个问题

动态规划可能会消除一部分解空间的子集(消除一部分求解)

 
 

 
 

范例1:Fibonacci 数列

 
 

递归算法:

Fibo(n):

if n = 0 then return(0)

else if n = 1 then return(1)

else return(Fibo(n-1)+Fibo(n-2))

 
 

时间复杂度如下:

 
 


 
 

F(6)要调用F(5)、F(4),然后又分别再继续调用。

太多的重复导致指数级的复杂度。

 
 

更有效的方法,不进行重复计算:


 
 

有两种方法:

  记忆求解,根据需求进行计算,不重复计算。

1、保存每一个递归调用结果

2、每次调用之前,检查一下是否计算结果已经保存了

  动态规划,不进行记忆<not memorized> (保存很少的信息)

预计算,不重复计算

1、递归变为递推Recursion become iteration,改为从下到上进行计算(top-down ->bottom up)

2、预计算所需要的值

 
 

DP(动态规划) 通常更简洁、快速、简单的数据结构

 
 

 
 

Fibonacci – Memoized Version

 
 


 
 

 
 

Fibonacci – Dynamic Programming Version

 
 


 
 

 
 

 
 

三、动态规划在什么情况下最有用呢?

  Same recursive sub-problems occur repeatedly 子问题解空间重叠

(Overlapping subproblems)

  Parameters of these recursive calls anticipated 预先计算

   The solution to whole problem can be solved 优化结构

without knowing the internal details of how the

sub-problems are solved ( principle of optimality, optimal structure)

 
 

 
 

四、最短路径问题     


使用贪心算法,从s到t的最短路径是1+2+5 = 8,这种情况是可解的。

 
 

多状态的图,求最短路径:                 


这种图,就无法使用贪心算法:(S A D T)=>1+4+18 = 23

实际的最短路径是:(S C F T)=>5+2+2 = 9

 
 

动态规划,分两种方法解决多状态图的问题【后向推理】【前向推理】

Dynamic programming approach [后向推理] [backward reasoning]

对A->T B->T分别讨论         


 
 


    

为什么动态规划是高效的?

SBDT is one path, the length of it

d(S,B)+d(B,D)+d(D,T) is never calculated.


BET < BDT

    
 

    
 

    

Dynamic programming approach [前向推理][forward reasoning]

    


 
 


 
 

 
 

 
 

向前推理 向后推理

Note that if the recurrence relations are formulated using the forward approach

then the relations are solved by backward reasoning .

i.e., beginning with the last decision

 
 

On the other hand if the relations are formulated using the backward approach,

they are solved by forward reasoning.

    
 

 
 

 
 

五、资源分配问题(The resource allocation problem)

m 个资源, 分给 n 个项目

profit :p(i, j) : j 个资源分配给了项目 i,获取的收益

目标:最大化整体收益

 

假设有 3 个资源,4 个项目,利润表如下:


 

表示为多阶段图,节点(3, 2)表示将3个资源分配给之前的项目1和当前的项目2


 
 

问题变为找一个最长路径(利润最大)

用前向推理或者后向推理得到结果:

(S, C, H, L, T), 8+5+0+0=13

2 resources allocated to project 1.

1 resource allocated to project 2.

0 resource allocated to projects 3, 4.

 
 

 
 

 
 

六、旅行商问题(The traveling salesperson [TSP] problem)

e.g.直连图


 
 

费用矩阵:        


 
 

多状态图的解决方法:             


 
 

一个结点的表示方法(The representation of a node)

假设在一个图中,我们有6个结点,

可以把不同的两个序列 {1, 2, 3, 4} ,{1, 3, 2, 4} 变成一个结点的表示方式



(3),(4,5,6) means that the last vertex visited is 3 and the remaining vertices to be visited are (4, 5, 6).

 
 

The dynamic programming approach

Let g(i, S) be the length of a shortest path starting at vertex i,

going through all vertices in S and terminating at vertex 1

让 g (i,S) 表示最短路径,最短路径由i开始,遍历 S 中所有的节点,最后在节点 1 结束。

 
 


 
 

 
 

 
 

 
 

 
 

六、最长公共子序问题(The longest common subsequence (LCS) problem

 
 

考虑一个字符串,A = b a c a d

A的一个子序列是通过从A中删去0个或更多个(不必是连续的)字符得到的。

e.g.    ad, ac, bac, acad, bacad, bcd……

 
 

A和B间的公共子序列定义为两个字符串的共同子序列。

A = bacad ; B = accbadcb :

A,B公共子序列: ad, ac, bac, acad.

The longest common subsequence (LCS) of

A and B:    acad.

 
 

The LCS algorithm





 
 


 
 



 
 


 
 

用表格方式体现,

如果比较的两个字符相等,左上斜角线那一格的值+1,再赋值给当前位置。

如果比较的两个字符不相等,就比较左一格,上一格,哪个大,当前位置就是哪个值。

 
 

 
 

 
 

 
 

七、最优二叉树(Optimal binary search trees


e.g. binary search trees for 3, 7, 9, 12;


 
 


 
 


 
 


 
 

 
 


 


 
 



 
 

 
 

八、矩阵链乘积(Matrix-chain multiplication)

矩阵链乘积是可用动态规划解决的最佳化问题。给定一序列矩阵,期望求出相乘这些矩阵的最有效方法。此问题并不是真的去执行其乘法,而只是决定执行乘法的顺序而已。

 
 

因为矩阵乘法具有结合律,所有其运算顺序有很多种选择。换句话说,不论如何括号其乘积,最后结果都会是一样的。例如,若有四个矩阵A、B、C和D,将可以有:

 
 

(ABC)D = (AB)(CD) = A(BCD) = A(BC)D = …

但括号其乘积的顺序是会影响到需计算乘积所需简单算术运算的数目,即其效率。例如,设A为 10×30矩阵,B为30×5矩阵与C为5×60矩阵,则

 
 

(AB)C 有 (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 个运算

A(BC) 有 (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 个运算

明显地,第一种方式要有效多了。

既然已确认过此问题了,那要如何决定n个矩阵相乘的最佳顺序呢?可以比较每一顺序的运算量(使用蛮力),但这将需要时间O(2^n),是一种非常慢且对大n不实在的方法。那解决方法,如我们将看到的,是将问题分成一套相关的子问题。以解答子问题一次而再使用其解答数次,即可以彻底地得出其所需时间。此一方法称为动态规划。


 
 

 
 

 
 

 
 

 
 



分类: 算法

发表评论

电子邮件地址不会被公开。 必填项已用*标注