很多参考书在讲解动态规划算法的时候都会使用到一个例子----流水线的装配调度问题。如图所示：
从in进入到流水线1需要e1的时间，这里的每个表格代表一个装配站，在同一条流水线中，从一个装配站到另一个装配站是不需要时间的，而跨流水线则需要时间，我们定义一个数组t来保存流水线的切换时间，（例如：从流水线1【2】到流水线2【3】)，那么这个时间为t[1][2]，在每个装配站上装配也需要时间，我们定义一个数组a来保存装配时间,例如：在流水线1上的装配站2所需的装配时间为a[1][2]。现在所要求的是从in到out的最短时间。
分析路线构造（描述最优解的结构）：
先对这个问题进行分析，假设我们现在已经装配到了n，可以是流水线1的n也可以是流水线2的n，那么从1到n-1都是最短时间完成的（也就是说从1到n-1的过程具有最短时间），这里有四种情况（上下两条是对称的），这里对流水线1进行分析：
1）、通过流水线1的装配站n-1，然后直接通过流水线1的n；
2）、通过流水线2的装配站n-1，然后从流水线2切换到1，之后通过流水线1的n；
对于流水线2的情况和流水线1一样。
构造递归解：
我们假设f*为最短时间，则f* = min(f[1][n]+x1 , f[2][n]+x2)，那么根据题意我们知道：f[1][1] = e1+a[1][1]; f[2][1] = e2+a[2][1]. 现在我们再来考虑如何计算f[i][j]，（这里i=1或2；j=2,3,4,...,n）。
根据刚才对流水线路线的分析 1）、2）两条我们得出：
f[1][j] = min(f[1][j-1]+a[1][j] , f[2][j-1]+a[1][j]+t[2][j-1]);
f[2][j] = min(f[2][j-1]+a[2][j] , f[1][j-1]+a[2][j]+t[1][j-1]);
求最短时间：
根据上面的递归式，我们可以计算出f这个数组里的值，又因为我们定义的这个f数组里面所存放的就是从装配站1到j的最短时间，所以以此我们就可以计算出从in到out的最短时间。
下面我们所要做的就是将上面的递归式以程序算法的形式写出：
f[1][1] = e1+a[1][1];
f[2][1] = e2+a[2][1];
for j = 2 to n
do if f[1][j-1]+a[1][j] < f[2][j-1]+a[1][j]+t[2][j-1]
then
f[1][j] = f[1][j-1]+a[1][j]
//line[1][j] = 1
else
f[1][j] = f[2][j-1]+a[1][j]+t[2][j-1]
//line[1][j] = 2
if f[2][j-1]+a[2][j] < f[1][j-1]+a[2][j] + t[1][j-1]
then
f[2][j] = f[2][j-1]+a[2][j]
//line[2][j] = 2
else
f[2][j] = f[1][j-1]+a[2][j]+t[1][j-1]
//line[2][j] = 1
if f[1][n]+x1 <= f[2][n]+x2
then f* = f[1][n]+x1
else f* = f[2][n]+x2
这个算法的过程还是比较好理解的，分为三部分，初始化、计算数组值、比较得出一个最小时间值。
当然这个算法只是仅仅的计算出了最短时间值，要是我们想要知道装配的每个站点，则还要用一个数组保存我们通过的流水线过程。假设使用一个数组line[i][j]来保存（i=1或2,j=2,3,...,n），那么我们就可以在每次计算出f[i][j]的地方对line这个数组进行赋值，也就是上面算法中加//的部分。
动态规划算法的设计可以大致分为以下四个步骤：
1）、描述最优解的结构；
2）、递归定义最优解的值；
3）、按自底向上的方式计算最优解的值；
4）、由计算结果构造一个最优解。
这里的第四步就相当于我们保存line这个数组的过程。
阅读(9632) | 评论(0) | 转发(0) |
