前面提到了动态规划的原理以及一个计算最短延迟时间的例子，联想到之前说过的隐马尔科夫模型（HMM）中的forward-backward算法、时序分类模型CTC中的动态规划算法，这些无非是在降低问题的计算时间复杂度。如果不使用DP算法来解决的话，原问题当然也是可以解决的，只不过计算量会非常大。
 
 
那么到底什么是DP算法呢？细想一下，DP算法的精髓无非就是把一个复杂的问题拆分成一些子问题，然后“递归”计算每个子问题的解，并且“记住”了每一个计算结果，这个技巧一般称为“Memoization”。在一般的递归计算中，会有许多子问题被重复计算，而DP算法则避免了重复计算的消耗。换句话说，DP算法对历史作了记录表，后来的子问题只用查询记录表即可获取值。
 
 
不妨看看下面两个程序之间的差异，它们都是为了解决同一个问题：
 

算法一：

int binom(int a, int b)
   {
     if (b==0 || b==a) return 1;
     else return binom(a-1,b-1)+binom(a-1,b);
   }
 
 

算法二：

int binomDP(int a, int b) 
{
     int binom[a+1][a+1];
     for (int i=0; i<=a; i++)
     {
          for (int j=0; j<=i; j++)
            {
               if (j==0 || j==i) binom[j] = 1;
               else binom[j] = binom[i-1][j-1] + binom[i-1][j];
          }
     }
     return binom[a];
}
 
 
那么，很显然算法二使用了DP算法来解决，而算法一仅仅是常规的递归计算，这中间当然会有同一个值被计算了多次，而算法二中每次计算都会保存在数组中，不会有重复的计算。
 
 
下面再看一个简单的DP问题，题目是这样的：现在假如有一个梯子一共有20格，你可以每次跨一步，也可以每次跨两步，还可以每次跨三步，为了从梯子底部到达梯子顶部，请问一共有多少种不同的走法？
 
 
如果按照传统的迭代方法的话，这个问题的计算复杂度应该是指数级的，但是我们可以使用DP算法将问题的复杂度降级为O(n)，下面我用C++语言来解决上面所说的梯子问题。
 
 
#include <iostream>
using namespace std;
int main()
{
    int i;
    int ladders=20;
    long num[ladders];
    for(i=0;i<ladders;i++) 
   {
        num=0;
    }
    num[0]=1;
    for(i=0;i<ladders;i++) 
    {
        if(i+1<ladders)
            num[i+1]+=num;
        if(i+2<ladders)
            num[i+2]+=num;
        if(i+3<ladders)
            num[i+3]+=num;
    }
    cout << num[ladders-1] << endl;
    return 0;
}
 
 
计算结果是:一共可以有66012种方法。
 
 
 
 
 

来源：张泽旺 深度学习每日摘要
智造家 查看全部

如下图所示为一个街景图，左边是一些居民的居住地，右边是一些停车场，图中连线是代表街道，而圆圈代表不同街道之间的交界处。网络之所以设计成这种钻石形状，是为了使得每次都必须穿越五条街才能达到停车场。圆圈中的数字表示等待时间，要解决的问题是希望规划出一条从家到停车场行走路线以至于所需的等待时间最短。






 
这个问题最朴素的做法就是循环遍历所有的150条路径，最终看哪个路径时间延迟会最短。然而这种做法所需计算资源比较大，DP算法可以使得计算量减小。
 

为了应用DP算法，我们可以把每个节点当做每个stage。我们可以运用反向归纳法，即从stage1开始计算，例如我们现在处在如下的节点处，那么我们要想到达右边的停车场，显然是选择3+2＝5的延迟路径而不是3+8=11，因此，这个节点的路径延迟就是５。







按照这个思路，我们可以进一步把stage1的所有节点的延迟路径规划出来，如下图所示：
stage1:






以此类推，我们可以计算stage2、stage3等等，最终所有节点处的最佳延迟时间就计算出来了，如下图所示：
stage2:






 
stage3:






 
stage4:






 
stage5:






 
这样，我们就得到了最终的所有最优路径图如上所示。可以看到，从左边倒数第二个位置处出发可以获得最短延迟时间为18的路径。除了可以使用反向归纳以外，这里也可以使用正向归纳来计算，可以计算，正向归纳与反向归纳所得到的最短路径均为18，但是其他的路径会不一样。
 

下面，我使用一段C++代码来实现上述的逆向归纳算法。
 
#include<iostream>
using namespace std;
 
int main()
{
    int delay_time[6][6]={{2,8,6,3,3,8},
 {5,6,5,9,5,2},
 {7,7,2,6,7,6},
 {4,3,6,3,9,5},
 {5,9,3,3,1,5},
 {6,4,9,2,3,3}};
    int flag[6][6]={0};//记录方向,1代表向上,0代表向下
    int accum_time[6][6];
 
    for(int i=0;i<=5;i++)
        accum_time[5]=delay_time[5];
 
    int up,down,up_t,down_t;
    for(int col=4;col>=0;col--)
    {
        if(col%2==0)
            up=0,down=1;
        else
   up=-1,down=0;
        for(int row=0;row<=5;row++)
{
   if(col%2!=0&&row==0)
   {
flag[row][col]=0;
accum_time[row][col]=delay_time[row][col]+accum_time[row][col+1];
   }
   else if(col%2==0&&row==5)
            {
flag[row][col]=1;
accum_time[row][col]=delay_time[row][col]+accum_time[row][col+1];
   }
   else
   {
       up_t=delay_time[row][col]+accum_time[row+up][col+1];
       down_t=delay_time[row][col]+accum_time[row+down][col+1];
       if(up_t<down_t) 
{
   flag[row][col]=1;
   accum_time[row][col]=up_t;
}
       else
{
   flag[row][col]=0;
   accum_time[row][col]=down_t;
}
   }
}
    }
    for(int i=0;i<=5;i++)
    {
        for(int j=0;j<=5;j++)
        {
   if(flag[j]==0)
    [size=12]        cout<<accum_time[j]<<",down ";[/size]
   else
    [size=12]        cout<<accum_time[j]<<",up ";[/size]
}
        cout<<endl;
    }
    return 0;
}
 
上述代码运行的结果就是：






跟最后一幅图的推理结果一样。
 
 
 
 
来源： 张泽旺 深度学习每日摘要
智造家 查看全部

 前言：这是我八月份的第一篇笔记，之所以写动态规划算法的原因有两点。一方面是因为在前面几期推文中讲到的隐马尔科夫模型、时序分类算法CTC均有运用到动态规划算法；另一方面是后期要写的强化学习中也会用到动态规划。因此，动态规划算法在深度学习中是一个非常常用的基础算法，本期介绍基础理论，下一期通过具体的示例来说明一下如何使用动态规划算法解决实际问题。


动态规划算法是一种基于决策的问题优化算法，运用动态规划算法来解决优化控制问题，通常它具有以下三个基本元素：
阶段。运用动态规划来解决优化问题最基本的一步是要把问题划分成多个阶段，并且按顺序每次解决一个阶段。尽管每单个阶段是一个普通的优化问题，它的解却能够帮助确定下一个阶段的特征。通常，阶段可能是指不同的时间段，例如运用动态规划问题优化一年中每一个月商品的库存量问题；但有时候阶段也可能不是对应着时间段，例如在堵车情况下规划最优路径的时候，这里的阶段就是确定每个子路径了。
 
状态。与每一个阶段的优化问题相对应的是过程的状态。状态是反映当前决策对未来行动所造成的后果，例如在堵车问题中状态就是每个子路径的等待时间。要明确一个系统的状态通常是动态规划模型中最难发现的部分，而对于这个并没有成套的规则可循。不过，对于状态的选择，通常有两个特征：第一，状态应该包含足够的信息来对未来一步做出决策，而不关心系统是如何达到此状态的；第二，状态的数目应该比较小，因为在动态规划问题中，状态变量的数目通常不能超过３个，原因是如果超过的话将会导致计算量非常庞大。因此，在实践中，第二点通常会限制动态规划算法的使用。
 
 
递归优化。递归优化的过程就是对于求解一个N阶段的问题，会按顺序去求解每一个单独阶段的优化问题，直到整体的优化解被找到。这个递归优化过程通常可以基于两种归纳法，逆向归纳法(backward induction)和正向归纳法(forward induction)。逆向归纳法的做法是首先分析问题的最后一个阶段，然后依次向前分析每个阶段，直到问题的所有阶段都有被包含；正向归纳法的做法是首先分析问题的初始阶段，然后依次向后分析每个阶段，直到问题的所有阶段都有被包含。在有些情况下，解决动态规划问题只能用两种归纳法中的其中一种，并且在大部分包含不确定性问题中，只能运用逆向归纳法去解决。



下面，我们来结合以上三个特征具体阐述一下动态规划的理论。假设现有一个对于特定阶段的回报函数为：

fn(dn,sn)

其中dn是一个决策，它可能是从所有决策集Dn中挑选的；sn是一个状态，对于系统而言，n的意思是接下来还需要进行n个阶段。通常情况下，给定阶段的决策集是依赖于那个阶段的状态的，换句话说，Dn可以写为Dn(sn)，为了简化表达，我们直接写成Dn。假如系统一共有N个阶段，我们用n代表归纳过程中剩余的阶段，并且，我们认为系统要经过余下n个阶段的话，只需要知道当前的状态sn即可，对于之前的所有状态我们并不关心，也就是说下一个阶段的状态只取决于此阶段的状态以及此阶段要做的决策。于是，我们定义一个状态转移函数，对于系统从剩余n个阶段转移到剩余n-1个阶段的函数为：

sn-1=tn(dn,sn)

这里的dn是指基于当前阶段和状态所做的决策。注意一点的是，这里一旦状态和决策确定，下一个阶段的状态也就唯一被确定了。


下面我们可以使用一张图来描述多阶段决策过程。







为了更好地将这些抽象的理论阐述清楚，我们来看一个具体的库存分配问题。在这个问题中，系统的状态sn是剩余n个月的库存量In，而决策dn是这个月要增加的库存量On，另外还要考虑每个阶段的库存消耗量Rn，因此，剩余n-1个月的库存含量的函数表达式（或者称之为状态转移表达式）为：

I(n-1)=tn(In,On)=In+On-Rn


而要优化的变量是库存配送的费用，即使得每个阶段的Cn(In,On)总和达到最小。


对于一般的问题，优化的目标都是使得总收益函数值达到最大或使得总损失函数值达到最小。因此，我们可以定义一个最优价值函数（optimal value function）：

vn(sn)=Max[fn(dn,sn)+...+f1(d1,s1)+f0(d0,s0)]


其中，状态转移函数为：

sm-1=tm(dm,sm)，其中dm∈Dm


而既然fn(dn,sn)是只依赖于dn的，而不依赖于之前的决策d(n-1),...,d0等，因此我们先算出最优价值函数的后面部分：

vn(sn)=Max{fn(dn,sn)+Max[fn-1(dn-1,sn-1)+...+f0(d0,s0)]}


于是，我们可以将最优价值函数写成如下的递归形式：


vn(sn)=Max[fn(dn,sn)+vn-1(sn-1)]


而sn-1=tn(dn,sn)，因此可以改写成：

vn(sn)=Max{fn(dn,sn)+vn-1[tn(dn,sn)]}

这样，就突出了决策dn对最优价值函数的影响。



上面的最优价值函数遵循的最优化原则，也就是说对于一个多阶段的问题，不管当前的决策dn和当前的状态sn如何，所有之后的状态必须是最优的，假设当前的决策就导致下一个状态sn-1。
 
 
 
 
 
来源：张泽旺 深度学习每日摘要
智造家 查看全部