如下图所示为一个街景图，左边是一些居民的居住地，右边是一些停车场，图中连线是代表街道，而圆圈代表不同街道之间的交界处。网络之所以设计成这种钻石形状，是为了使得每次都必须穿越五条街才能达到停车场。圆圈中的数字表示等待时间，要解决的问题是希望规划出一条从家到停车场行走路线以至于所需的等待时间最短。
这个问题最朴素的做法就是循环遍历所有的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;
}
上述代码运行的结果就是：
跟最后一幅图的推理结果一样。
来源： 张泽旺 深度学习每日摘要
智造家