一篇小白也能看懂的动态规划算法文章

vlambda
2020-02-06

一篇小白也能看懂的动态规划算法文章

前言

动态规划( dynamic programming )是属于运筹学的一门分支，它是求解决策过程最优化的一种数学方法。在上世纪50年代初期美国的几位数学家在研究多阶段决策过程( multistep decision process ) 的最优化问题时，提出了最优化原理，把多阶段的复杂问题转换为一系列的单阶段问题，利用各个阶段之间的关系，逐个求解，从而创立了解决这类过程优化问题的新方法——动态规划( dynamic programming )。

基本概念

动态规划过程是：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。

基本思想

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。“我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。” 这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。

适用条件

任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。

最优化原理(最优子结构性质)：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。
无后效性：将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。
子问题的重叠性动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。

动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。

基本结构

多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化问题的方法为动态规划方法。可以得到动态规划的基本模型如下：

(1)确定问题的决策对象。

(2)对决策过程划分阶段。

(3)对各阶段确定状态变量。

(4)根据状态变量确定费用函数和目标函数。

(5)建立各阶段状态变量的转移过程，确定状态转移方程。状态转移方程的一般形式：

U：状态；X：策略　

顺推：

f[Uk]=opt{f[Uk-1]+L[Uk-1,Xk-1]}

其中， L[Uk-1,Xk-1]：状态Uk-1通过策略Xk-1到达状态Uk 的费用

初始f[U1]；

结果：f[Un]。

倒推：

　　f[Uk]=opt{f[Uk+1]+L[Uk,Xk]}

　　L[Uk,Xk]：状态Uk通过策略Xk到达状态Uk+1 的费用

　　初始f[Un]；

结果：f(U1)

基本框架

// 第一个阶段
 xn[j] = 初始值;
 for(i=n-1; i>=1; i=i-1)
 // 其他n-1个阶段
   for(j=1; j>=f(i); j=j+1)
    //f(i)与i有关的表达式
     xi[j]=j=max（或min）{g(xi-1[j1:j2]), ......, g(xi-1[jk:jk+1])};
     t = g(x1[j1:j2]); 
    // 由子问题的最优解求解整个问题的最优解的方案

   print(x1[j1]);
 for(i=2; i<=n-1; i=i+1）
 {  
     t = t-xi-1[ji];
     for(j=1; j>=f(i); j=j+1)
        if(t=xi[ji])
             break;
 }

求解01背包问题

有一个背包，背包容量是M=180。有7个物品，物品可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。

物品	A	B	C	D	E	F	G
重量（ｗ）	35	30	60	50	40	10	25
价值（ｐ）	10	40	30	50	35	40	30

问题分析：

这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。可以将背包问题的求解看作是进行一系列的决策过程，即决定哪些物品应该放入背包，哪些不放入背包。

如果一个问题的最优解包含了物品n，即Xn = 1，那么其余X1, X2, .....,Xn-1 一定构成子问题1,2,.....,n-1在容量M - cn时的最优解。如果这个最优解不包含物品n,即Xn = 0;那么其余 X1, X2.....Xn-1一定构成了子问题 1,2,....n-1在容量M时的最优解。

根据以上分析最优解的结构递归定义问题的最优解：

f[i][v] = max{ f[i-1][v] , f[i-1][v - M[i]] + v[i]}

代码实现：

#include <iostream>
#include <algorithm>
using namespace std;
struct bag
{
    int weight;//总重量
    int value;//总价值
    float bi;//单位重量的价值
    float rate;//使用率：1代表完整放入，小于1代表被分割后放入
} bags[50];
bool compare(const bag &bag1,const bag &bag2)
{
    return  bag1.bi>bag2.bi;
}
int main()
{
    int sum=0,n;
    float M;
    int j=0;
    cout<<"输入背包容量和物品数量："<<endl;
    cin>>M>>n;
    for(int i=0; i<n; i++)
    {
        cin>>bags[i].weight>>bags[i].value;//录入物品重量和价值。
        bags[i].bi=(float)bags[i].value/bags[i].weight;//计算单位重量价值。
        bags[i].rate=0;//初始化每件物品使用率。
    }
    sort(bags,bags+n,compare);//将物品按照单位重量价值由大到小排序
    for(j=0; j<n; j++)
    {
        if(bags[j].weight<=M)
        {
            bags[j].rate=1;
            sum+=bags[j].weight;
            M-=bags[j].weight;
            cout<<"重："<<bags[j].weight<<"价值："<<bags[j].value<<"的物品被放入了背包"<<endl<<"放入比例:"<<bags[j].rate<<endl;
        }
        else break;
    }
    if(j<n)
    {
        bags[j].rate=M/bags[j].weight;
        sum+=bags[j].rate*bags[j].weight;
        cout<<"重："<<bags[j].weight<<"价值："<<bags[j].value<<"被放入了背包"<<endl<<"放入比例:"<<bags[j].rate<<endl;
    }

    return 0;
}

总结

动态规划在我们的生活中应用非常广泛，生产管理，工程调度，最优控制等领域均有应用。虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。

END

vlambda博客
学习文章列表