《算法导论》第15章 动态规划 (1)装配线调度

动态规划通常用于有很多种可行解，而找出最优解的问题。

具体可分为4个步骤：

1）描述最优解的结构。

2）递归定义最优解的值。

3）自底向上计算最优解的值。

4）由最优解的值构造出最优解。

下面通过一个具体问题来看究竟如何用动态规划算法来解决问题。

Colonel汽车公司在有两条装配线的工厂里生成汽车。每一条装配线上有n个装配站，

两条生产线上相同位置的装配站功能相同，但所需时间不同，并且汽车底盘在两条

装配线间转移要花费一定的时间。如下图所示两条生产线。

这里首先尝试下下一章的贪心算法，在每一步都取最省时间的装配站。首先进入装配线1时间为2 + 7

小于装配线2的4 + 8，因此进入装配线1。之后装配站2的时间9大于转移到装配线2的时间2 + 5，因此

转移到装配线2上。以此类推可以得到下图中标红的路线：

可以清楚地看出，在这个问题上采用贪心的策略是不对的，那么哪里出了问题呢？问题的关键就

在于两条装配线间转移是需要不同时间的。以装配站Station-1,3为例，虽然选择进入Station-1,4保证

了眼前的最优（Station-1,4的时间4大于转移到装配线2的时间1 + 4），但是接下来在Station-1,4至少

要耗费时间为8，一共需要时间为4 + 8 = 12。但若在Station-1,3时转移到了装配线2的Station-2-4，

花费时间1 + 4 = 5，接下来直接进入Station-2,5，那么一共需要时间5 + 5 = 10。

这就是问题的关键！在Station-1,3处只能看到眼前的两种选择哪个更节省时间，却没法知道后来的情况。

这也就是“步步最优不等于全局最优”的道理。然而所有路线的可能性为2 ^ n，其中n为每条装配线上

装配站的个数。因此当有很多装配站时，使用Brute force生成比较各条路线的值几乎是不可能的。

那么现在就要请出动态规划来帮忙了。

e1和e2表示进入装配线1和2所需时间，x1和x2表示出装配线时间。

a1和a2表示各个装配站花费时间，t1和t2则表示装配线间转移花费的时间。

装配线1和2的最优路线保存到数组L1和L2中用于构造一个最优解。

下面来看具体实现代码。

#include <stdio.h>
#include <stdlib.h>
#define SIZE 6

int e1 = 2, e2 = 4;
int a1[] = { 7, 9, 3, 4, 8, 4 };
int a2[] = { 8, 5, 6, 4, 5, 7 };
int t1[] = { 2, 3, 1, 3, 4 };
int t2[] = { 2, 1, 2, 2, 1 };
int x1 = 3, x2 = 2;

void fastest_way(void)
{
     int f1[SIZE], f2[SIZE];
     int l1[SIZE], l2[SIZE];

     f1[0] = e1 + a1[0];
     f2[0] = e2 + a2[0];

     int j;
     for (j = 1; j < SIZE; j++) {
          if (f1[j - 1] < f2[j - 1] + t2[j - 1]) {
               f1[j] = f1[j - 1] + a1[j];
               l1[j] = 0;
          } else {
               f1[j] = f2[j - 1] + t2[j - 1] + a1[j];
               l1[j] = 1;
          }
          if (f2[j - 1] < f1[j - 1] + t1[j - 1]) {
               f2[j] = f2[j - 1] + a2[j];
               l2[j] = 1;
          } else {
               f2[j] = f1[j - 1] + t1[j - 1] + a2[j];
               l2[j] = 0;
          }
     }
     
     int f, l;
     if (f1[j - 1] + x1 < f2[j - 1] + x2) {
          f = f1[j - 1] + x1;
          l = 0;
     } else {
          f = f2[j - 1] + x2;
          l = 1;
     }

     // 构造最优解
     printf("%d\n", f);
     print_path(&l1, &l2, l, SIZE - 1);          
}

void print_path(int *l1, int *l2, int l, int j)
{
     if (j > 0) {
          if (l == 0)
               print_path(l1, l2, l1[j], j - 1);
          else
               print_path(l1, l2, l2[j], j - 1);
     }
     printf("%d line, %d station\n", l, j);
}

int main(void)
{
     fastest_way();
     return 1;
}

原来动态规划也是从装配站1开始到N逐步计算，但与贪心法不同的是，它用数组f1[j]和f2[j]记录了通过

装配站a1[j]和a2[j]的最优解。以a1[j]为例，计算通过a1[j]的最优解时，不是像贪心法那样只通过前一个

装配站a1[j-1]和a2[j-1]+t2[j-1]谁更省时间，而是比较了f1[j-1]和f2[j-1]+t2[j-1]来决定到底是从a1[j-1]直接

运送到a1[j]，还是由a2[j-1]转移到装配线1。这样可以明显看出动态规划与贪心算法的区别，贪心算法只顾

眼前（前一个装配站的情况），而动态规划则是根据前面所有装配站的情况（f1和f2保存了前面所有装配站

的最优解）。重点是理解f1和f2的意义，从而明白这个问题的最优子结构是如何定义。

下图中标红的路线才是最优路线。

在使用L1和L2构造最优解时要注意，要从后向前处理，因为我们只知道最优路线是从装配线1中出来。

所以在这里可以采用递归地方式，来正序打印最佳路线。这也是习题15.1-1的答案。