动态规划求解流水线问题

• 一、实验目的与要求
• • 1. 实验目的：
  • 2. 实验亮点：
• 二、实验内容与方法
• • 1. 实验内容：
  • 2. 实验要求：
• 三、实验步骤与过程
• • （一）暴力穷举法
  • • 1、算法描述：
    • 2、时间复杂度分析：
    • 3、编程实现：
    • 4、运行并测试：
  • （二）动态规划法
  • • 1、算法描述：
    • • （1）分析规划过程：
      • （2）分析动态规划方程：
    • 2、时间复杂度分析：
    • 3、编程实现：
    • 4、运行并测试：
  • （三）效率对比分析
• 四、实验结论或体会
• 五、思考（时间与空间优化）
• • 1、算法描述：
  • 2、进行优化：
  • 3、进行测试：
  • 4、只用内存进行运算：

一、实验目的与要求

1. 实验目的：

（1） 掌握动态规划算法设计思想。
（2） 掌握流水线问题的动态规划解法。

2. 实验亮点：

（1）使用动态规划算法进行了优化，大大降低了程序的运行时间。并给出了详细的规划方程。
（2）选用了更合理的数据结构进行优化，将程序可处理的数据量上限提高到 1 0 1 3 10^13 1013并将程序运行的时间降低至 1 / 100 1/100 1/100。
（3）每个算法均有详细的伪代码描述。并对不同数据量级下做对比并做出数据折线图。
（4）对算法的正确性进行了逻辑上与数据上的验证。

二、实验内容与方法

1. 实验内容：

汽车厂有两条流水线，每条流水线有n个处理环节（station）: S 1 , 1 S_{1,1} S1,1​，…， S 1 , n S_{1,n} S1,n​ 和 S 2 , 1 S_{2,1} S2,1​，…， S 2 , n S_{2,n} S2,n​，其中下标的第一个字母表示流水线编号（流水线1和流水线2）。其中 S 1 , j S_{1,j} S1,j​ 和 S 2 , j S_{2,j} S2,j​完成相同的功能，但是花费的时间不同，分别是 a 1 , j a_{1,j} a1,j​ , a 2 , j a_{2,j} a2,j​ 。两条流水线的输入时间分别为 e 1 e_1 e1​ 和 e 2 e_2 e2​, 输出时间是 x 1 x_1 x1​ 和 x 2 x_2 x2​。

每个安装步骤完成后，有两个选择：
1）停在同一条安装线上，没有转移代价；
2）转到另一条安装线上，转移代价： S i , j S_{i,j} Si,j​ 的代价是 t i , j t_{i,j} ti,j​, j = 1，…，n - 1

问题: 如何选择安装线1和安装线2的节点组合，从而最小化安装一台车的总时间？

2. 实验要求：

1. 给出解决问题的动态规划方程；
2. 随机产生 S 1 , j S_{1, j} S1,j​, S 2 , j S_{2, j} S2,j​ , t i , j t_{i, j} ti,j​的值，对小数据模型利用蛮力法测试算法的正确性；
3. 随机产生 S 1 , j S_{1, j} S1,j​, S 2 , j S_{2, j} S2,j​ , t i , j t_{i, j} ti,j​的值，对不同数据规模（ n n n的值）测试算法效率，并与理论效率进行比对，请提供能处理的数据最大规模，注意要在有限时间内处理完；
4. 该算法是否有效率提高的空间？包括空间效率和时间效率。

三、实验步骤与过程

（一）暴力穷举法

1、算法描述：

对于暴力穷举解决流水线问题，只需对所有组合可能进行完备穷举，并选择较小的时间消耗作为最终结果。由于暴力法是对每一种解的完备搜索，因此暴力法的正确性有很高的保证。

2、时间复杂度分析：

对于一条流水线上的每个单元，存在两种选择，即选择在流水线1上或在流水线2上。因此，对于 n n n个单元，存在 2 n 2^n 2n种不同的选择。因此暴力穷举法时间复杂度为 O ( 2 n ) O(2^n ) O(2n)

3、编程实现：

伪代码如下

//find each combination by binary
bitset<LEN> flagBit;

//least cost
int res = 1e9

//cost of chassis enters
int e[2]

//cost of each station
int a[2][LEN]

//cost of transform
int t[2][LEN]

//Use binary to brute force each combination
while (flagBit!=0):
    //Use binary to identify the combination
    //'0' for line 0, '1' for line 1

    currentCost = 0

    //chassis enters
    if (flagBit[0] == 0): 
        currentCost += (e[0] + a[0][0])
    else:
        currentCost += (e[1] + a[1][0])
        
    //each station
    for i from 1 to LEN:
        //cost of a station
        currentCost += a[flagBit[i]][i]

        //if transform
        if flagBit[i] != flagBit[i - 1] 
            currentCost += t[flagBit[i - 1]][i - 1]

    res = min(res, currentCost)
    flagBit--
    
print(res)

①通过二进制表示每个流水线的选择情况，如果为0则选择第一个流水线，如果为1则选择第二个流水线
②在循环中进行判断，如果当前环节流水线与上一环节的流水线不相同，则需额外加上转移流水线消耗的时间。
③进入流水线与退出流水线的消耗时间直接加到当前运行时间即可
④完成一次可能的计算后，将当前时间消耗值与当前最小时间消耗值进行比较，如果小于当前最小时间消耗值，则进行更新。
⑤完成所有可能的穷举后即可获得最小时间消耗值。

4、运行并测试：

使用随机数生成器生成了不同大小的多组测试数据。为了避免运行时的偶然情况，对于每个数量级下的多组数据进行20次测试并取平均值作为该数据量级下的结果，并统计如下：

选取数据量为25时的运行时间为理论值，将各个数据取对数并作图如下：

通过分析可知，对于全体数据，时间复杂度大致满足 O ( 2 n ) O(2^n ) O(2n)，证明时间复杂度分析是正确的。通过观察图像，我们也可以发现，当数据量较小时，实际运行时间要比理论运行时间短这是因为算法运行过程中每运行一次都要开辟动态空间，每次开辟空间均会对后面算法的执行造成影响。当数据量较小时，已经开辟的动态空间较少，对算法影响小，因此会比较快；但当数据量较大时，已经开辟了很多空间，对算法影响较大，因此会比较慢。

（二）动态规划法

1、算法描述：

（1）分析规划过程：

通过分析，我们可以知道，当流水线运行到第j个配件站是最优的，则到达该配件站前可能为 S ( 1 , j − 1 ) S(1,j-1) S(1,j−1)或 S ( 2 , j − 1 ) S(2,j-1) S(2,j−1)，且到达 S ( 1 , j − 1 ) S(1,j-1) S(1,j−1)或 S ( 2 , j − 1 ) S(2,j-1) S(2,j−1)的路径同样也为最短的。即到达S(1,j)的最优解包含了到达 S ( 1 , j − 1 ) S(1,j-1) S(1,j−1)或 S ( 2 , j − 1 ) S(2,j-1) S(2,j−1)的最优解。对于通过的最优路线，必然通过了流水线1或流水线2的 j − 1 j-1 j−1配件站。因此，通过 S ( 1 , j ) S(1,j) S(1,j)的最优路线只能是如下两种选择：
①通过配件站 S ( 1 , j − 1 ) S(1,j-1) S(1,j−1)，然后直接到达 S ( 1 , j ) S(1,j) S(1,j)
②通过配件站 S ( 2 , j − 1 ) S(2,j-1) S(2,j−1)，然后从流水线2到流水线1最后到达 S ( 1 , j ) S(1,j) S(1,j)

由于流水线1与流水线2是完全对称的，因此需要找到到达某一配件站的最短时间，只需解决两个子问题的最短时间，并通过对子问题的求解最后构造出整个问题的最优解即可。

（2）分析动态规划方程：

首先我们将到达最后出口的最短时间记作 f ∗ f^* f∗，流水线长度都为 n n n，则有：
f ∗ = m i n ⁡ ( f 1 [ n ] + x 1 , f 2 [ n ] + x 2 ) f^*=min⁡(f_1 [n]+x_1,f_2 [n]+x_2 ) f∗=min⁡(f1​[n]+x1​,f2​[n]+x2​)

当进入流水线第一个环节时，则可得：
f 1 [ 1 ] = e 1 + a 1 , 1 f_1 [1]=e_1+a_{1,1} f1​[1]=e1​+a1,1​
f 2 [ 1 ] = e 2 + a 2 , 1 f_2 [1]=e_2+a_{2,1} f2​[1]=e2​+a2,1​
通过对上面的分析，有：
f 1 [ j ] = { e 1 + a 1 , 1 j=1 m i n ⁡ ( f 1 [ j − 1 ] + a 1 , j , f 2 [ j − 1 ] + t 2 , j − 1 + a 1 , j j≥2 f_1 [j]= \begin{cases} e_1+a_{1,1}& \text{j=1}\\ min⁡(f_1 [j-1]+a_{1,j} ,f_2 [j-1]+t_{2,j-1}+a_{1,j}& \text{j≥2} \end{cases} f1​[j]={e1​+a1,1​min⁡(f1​[j−1]+a1,j​,f2​[j−1]+t2,j−1​+a1,j​​j=1j≥2​

f 2 [ j ] = { e 2 + a 2 , 1 j=1 m i n ⁡ ( f 2 [ j − 1 ] + a 2 , j , f 1 [ j − 1 ] + t 1 , j − 1 + a 2 , j j≥2 f_2 [j]= \begin{cases} e_2+a_{2,1}& \text{j=1}\\ min⁡(f_2 [j-1]+a_{2,j} ,f_1 [j-1]+t_{1,j-1}+a_{2,j}& \text{j≥2} \end{cases} f2​[j]={e2​+a2,1​min⁡(f2​[j−1]+a2,j​,f1​[j−1]+t1,j−1​+a2,j​​j=1j≥2​

2、时间复杂度分析：

通过分析算法描述中的运行过程可知，在运行过程中，仅需按照流水线顺序进行从头至尾一次扫描即可，因此时间复杂度为 O ( n ) O(n) O(n)

3、编程实现：

编写伪代码如下：

f1[1]<- e1+a1,1 //处理第一个环节
f2[1]<- e2+a2,1 //处理第一个环节
for j<-2 to n   //对第2到第n个环节进行处理
    do if f1[j-1]+a1,j <=f2[j-1]+t2,j-1+a1,j  //对第一条流水线的最优解进行判断
        then    
            f1[j]<-f1[j-1]+a1,j
            l1[j]<-1
        else
            f1[j]<-f2[j-1]+t2,j-1+a1,j
            l1[j]<-2

        if f2[j-1]+a2,j <=f1[j-1]+t1,j-1+a2,j  //对第二条流水线的最优解进行判断

        then    
            f1[j]<-f2[j-1]+a2,j
            l2[j]<-1
        else
            f1[j]<-f1[j-1]+t1,j-1+a2,j
            l1[j]<-2
if f1[n]+x1<=f2[n]+x2   //最终最优解判断
    then
        f* <-f1[n]+x1
        l* <-1
    else    
        f* <-f2[n]+x2
        l* <-2

4、运行并测试：

①正确性检验：
为了验证动态规划算法的正确性，生成大量随机数据并使用暴力穷举法和动态规划法进行同步运行，并比较运行结果是否一致。生成了 1 0 5 10^5 105组不同的测试数据，在两种方法线下均可以得到相同的结果，结合逻辑分析，可以证明动态规划算法是正确的。

②效率分析：
使用随机数生成器生成了不同大小的多组测试数据。为了避免运行时的偶然情况，对于每个数量级下的多组数据进行20次测试并取平均值作为该数据量级下的结果，并统计如下：

选取数据量为 1 0 6 10^6 106时的运行时间为理论值，取对数并作图如下：

通过分析可知，对于全体数据，时间复杂度大致满足 O ( n ) O(n) O(n)，证明时间复杂度分析是正确的。整体图像大致成线性，拟合效果比较好。

（三）效率对比分析

对于暴力穷举以及动态规划两种算法，根据现有数据以及时间复杂度分析，大致做出如下表：

从上表以及对两算法的运行时间图冲大致可以看出，暴力穷举算法的时间复杂度是十分恐怖的，对于一些稍微大一些的数据，需要若干年才能得出结果，而动态规划只需若干毫秒，时间对比十分明显。因此在进行流水线调度问题时，我们要选择动态规划法进行计算。

四、实验结论或体会

1. 常规穷举法的效率常常是非常低的。对于一些问题，可以将大问题转为若干个子问题，并利用动态规划思想进行运算可以很大程度上降低运行时间。
2. 在进行算法优化过程中，除了降低算法的时间复杂度，降低算法运行的常数级时间也是很重要的，也可以极大的降低程序的时间消耗。
3. 算法的空间消耗也很重要，可以通过采用更优的数据结构降低空间消耗。
4. 选取合适的数据结构可以又降低运行时间又减少运行空间。

五、思考（时间与空间优化）

1、算法描述：

在运行动态规划算法的代码时，经常发现，算法能运行的数据大小是有限的，无法运行一些特别大的数据，比如超过 1 0 8 10^8 108的数据。

当数据量大到一定程度后，会造成由于数组太大造成内存不足，而抛出std::bad_alloc异常（俗称爆内存）。这限制了程序对更大数据量的处理。通过分析程序，我们可以发现，在对动态规划的路径保存过程中，使用了32位整型int对路径进行存储。但对于本题来讲，路径值只可能为0或1。因此造成了大量的空间冗余浪费。不妨采取一种新的数据结构对路径进行优化存储。

并且运行中采用了一个另外的数组来记录当前的最小时间消耗值，但通过逻辑分析，可以发现，该数组被创建后，仅仅最后一个元素被二次访问过，中间的元素只被创建，并没有多次访问，因此创建数组是无意义的，可以直接采用unsigned long long型变量对当前最小值进行存储

2、进行优化：

①引入bitset数据结构：
为了更好的存储0或1，而尽少占用空间，可以引入bitset这一数据结构，在bitset中，仅对0或1的值进行存储，因而每位bitset只占1比特，而int型占32比特，采用该数据结构成功将内存占用降低为之前的1/32。并且，由于bitset是基于底层位逻辑，因此采用bitset数据结构后，程序的运行时间也会降低很多。

②减少无用数组：
在编程过程中对当前最优时间的存储采用了数组进行存储，由于数组只创建，并在运算过程中进行了单次调用。因此可以使用last_1_cost，last_2_cost，current_1_cost，current_1_cost四个unsigned long long型变量存储上一次流水线1,2的最优时间和当前流水线1,2的最优时间。这不仅减少了程序运行消耗的空间，也避免了反复对数组进行大量操作，从而降低程序运行时间。

③避免一次加载所有数据：
由于记录流水线的每个环节消耗时间与流水线切换时间的数组是采用int型，并且是不可缺省的。若直接一次性加载到内存中将占用很多内存，因此，不妨分多次将数据加载到内存中。一次加载 1 0 7 10^7 107的数据到内存中，并进行运算，当运算完加载的数据后，再将大小为 1 0 7 10^7 107的数据加载到内存中，依次循环。

3、进行测试：

可以看到，优化之后的算法与优化前相比，不仅能处理更大的数据，并且运行时间得到了很大提升，大约缩短至原 1 / 100 1/100 1/100。因此算法优化是有效的，并且是高效的。

4、只用内存进行运算：

此外，如果不采用内存进行保存结果，只采用内存进行运算，即一边进行动态规划，一边进行读入数据，可以在理论上做到处理无穷大的数据。