【算法设计与分析】动态规划—流水线问题

Alex_Shen
2021-07-16 / 0 评论 / 0 点赞 / 116 阅读 / 3,445 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-04-06,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

github:项目地址

一、实验目的:

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

二、内容:

汽车厂有两条流水线,每条流水线有n个处理环节(station): S1,1,…,S1,n 和 S2,1,…,S2,n,其中下标的第一个字母表示流水线编号(流水线1和流水线2)。其中S1, j 和 S2, j 完成相同的功能,但是花费的时间不同,分别是a1, j , a2, j 。两条流水线的输入时间分别为e1 和 e2, 输出时间是x1 和 x2。

每个安装步骤完成后,有两个选择:
1)停在同一条安装线上,没有转移代价;
2)转到另一条安装线上,转移代价: Si,j 的代价是ti,j , j = 1,…,n - 1

在这里插入图片描述
问题: 如何选择安装线1和安装线2的节点组合,从而最小化安装一台车的总时间?

三、实验要求

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

四、实验过程及结果

一:实验结果正确性展示

随机生成了多组20个结点,通过蛮力法与动态规划法分别求解,验证程序正确性,结果如下。
在这里插入图片描述

二:蛮力法求解

  1. 算法原理
    (1) 通过遍历所有可能的路径和并计算总时间的最小值。
    (2) 取任意一种可能的情况(如左图所示),可以将路径表示位00110(0表示上流水线,1表示下流水线)
    在这里插入图片描述

    (3) 显然对于n个结点的流水线,所有可能的路线有种可能性,可以用0 ~ 的二进制表示所有情况。

  2. 伪代码

for 0 to 2^n-1:	// 遍历每一条路径
	sum += e + 结点1
	for 二进制串的每一个位置:
		if 需要转移:
			sum += 转移代价 + 结点i
		else if 不需要转移
			sum += 结点i
	if sum < MIN:
		MIN = sum
  1. 复杂度分析
    (1) 时间复杂度:O(2n)O(2^n)
    (2) 空间复杂度:O(n)O(n)

  2. 数据分析
    在这里插入图片描述
    在这里插入图片描述

三:动态规划法求解

①总时间计算

  1. 算法原理
    (1) 动态规划方程:
    在这里插入图片描述
    其中参数含义:
    e:输入时间
    t :转移代价
    a:花费时间
    x:输出时间
    dp[i]:当前结点最短总时间
    res:最终总时间

  2. 伪代码

dp1 =e1 + a[1][1], dp2 =e2 + a[2][1]
for i = 2 to n:
	dp1 = min(dp1 + a[1][i], dp2 + t[2][i - 1] + a[1][i])
	dp2 = min(dp2 + a[2][i], dp1 + t[1][i - 1] + a[2][i])
res = min(dp1 + x1, dp2 + x2)  
  1. 复杂度分析
    (1) 时间复杂度:O(n)O(n)
    (2) 空间复杂度:O(1)O(1)
    根据题意,不需要保存每一个结点的最优值,所以每次动态规划可以及时更新dp值。

  2. 数据分析
    在这里插入图片描述
    在这里插入图片描述

②路径计算

1. 路径存储原理(一)

(1) 算法原理
在这里插入图片描述
具体详细保存两条路径(具体生成过程见PPT / 汇报)
如图所示,路径1:ABBAA / 路径2:ABBBB

(2) 伪代码

dp1 =e1 + a[1][1], dp2 =e2 + a[2][1]
路线1[1] = A, 路线2[1] = B
for i = 2 to n:
     if dp1 + a[1][i] < dp2 + t[2][i - 1] + a[1][i]:
          dp1 = dp1 + a[1][i]
          路线1 更新新节点A
     else: 
          dp1 = dp2 + t[2][i - 1] + a[1][i]
          路线1 = 路线2
          路线1 更新新节点A
     (对dp2 做相同类似操作)
if dp1 + x1 < dp2 + x2:
     路线1 为最优路径
else:
     路线2 为最优路径

(3) 复杂度分析
① 时间复杂度:O(n2)O(n^2)
具体生成路径过程见PPT / 汇报,可以发现当需要转移流水线时,需要将路径进行切换(复制另一条路径),这会导致两条路径频繁的相互复制。
复制过程复杂度为O(n)O(n),所以会导致算法总体复杂度O(n2)O(n^2)
② 空间复杂度:O(2n)O(2n)
对于两条路径,直到最后加上输出代价才知道哪一条路径为更优解。所以需要保存两条路径,空间复杂度为O(2n)O(2n)

2. 路径存储原理(二)

(1) 算法原理
①每一结点都保存其来自于第一/第二流水线。
②解码过程通过回溯法即可获取路径。具体解码过程见PPT / 汇报。
在这里插入图片描述
(2) 伪代码

路径存储:
dp1 =e1 + a[1][1], dp2 =e2 + a[2][1]
routeA[1] = A, routeB[1] = B
for i = 2 to n:
     if dp1 + a[1][i] < dp2 + t[2][i - 1] + a[1][i]:
          dp1 = dp1 + a[1][i]
          routeA 更新新节点A
     else:
          dp1 = dp2 + t[2][i - 1] + a[1][i]
          routeA 更新新节点B
     (对dp2 做相同类似操作)
解码过程:
if dp1 + x1 < dp2 + x2:
     起始点为S[1][n], t = 1
else:
     起始点为S[2][n], t = 2
for i = n to 2
     output route[t][i]
     t = route[t][i]

(3)复杂度分析
① 时间复杂度:O(n)O(n)
② 空间复杂度:O(2n)O(2n)

(4) 数据分析
利用 char 数组存储路径。(用bit存储路径,可以更加节省空间)
Windows下,最多开到8-9亿,存储1亿的时间大约12s。
Linux下,存储1亿的时间大约17s,极限510亿2.5小时。
符合O(n)O(n)的时间复杂度

由上一部分可知,路径存储即对于二进制串的存储。以下部分为对于二进制串存储的压缩算法分析。
非杨煊老师的算法课以下部分可以忽视,纯属被迫卷起来了

3. 压缩算法(一)

(1) 算法原理

① n位连续数字可以保存为n。
② 解码过程中,AB交替出现。所以当知道末尾结点来自A或B,可以自尾向前解码。
③ 例子:
路径:A BB AAAAAA BBBB A B AA BBB AA
压缩编码:1 2 6 4 1 1 2 3 2
路径:AAAAAAAAAAA BBBBBBBBBB
压缩编码:11 11

(2) 数据离散度测试
显然,数据的离散程度对于压缩效率有着较大的影响。
测试数据:随机生成一条长度为10亿的路径。
在这里插入图片描述
由表中数据可以得知,当转移代价越大时,二进制连续性越大。
具体影响程序见后续数据分析。

(3) 伪代码

end_s = A or B
BEGIN
     s = next input
     if s == route[end]:
          code[end] += 1
     else:
          code.push_back(1)
          end_s = s
END

(4) 数据分析
① 测试结果:1亿数据存储时间约为21秒,最大测试结果为1550亿9小时(理论上可以更大,堆内存大小即可)
② 压缩效率理论测试:

  1. 二进制串长度:N
  2. 最大连续位数:max
  3. 平均连续位数:avg
  4. 压缩效率:
    在这里插入图片描述
    在这里插入图片描述
    由表中数据可以得知,当转移代价越大时,压缩效率越高。当代价比例大于7时,压缩算法才有效。
    但显然不符合实际逻辑。所以并不是一个好的压缩算法。

4. 压缩算法(二)

(1) 算法原理
① 利用哈希表存储一个字典,在生成动态二进制串时,利用LZW算法,对串进行压缩。
② 具体生成过程见PPT / 汇报。
③ 举例:
路径:ABABBABABABBA
压缩编码:1 2 3 4 6 5 1
字典如下所示
在这里插入图片描述
(2) 伪代码
在这里插入图片描述
(3) 数据分析
① 压缩效率理论测试:

  1. 二进制串长度:N
    字典长度:T
    压缩后位数:M
  2. 压缩效率:NMlog2T\frac{N}{M*\lceil{\log_2T}\rceil}

② 当转移代价:花费代价 = 1 :1,测试数据如下。
在这里插入图片描述
③当转移代价:花费代价 = 1 :1,测试数据如下。
在这里插入图片描述
在这里插入图片描述
由表中数据可以得知,当转移代价越大时,压缩效率越高。当代价比例大于1时,压缩算法有效。
在小规模时,压缩效率提升巨大,大规模时,压缩效率有提升,但是较慢。
但是字典压缩编码还需要存储一个相对较大的字典,由第一个表格可知,字典实际上时比较庞大的,所以仍然需要耗费相当一部分空间。将压缩编码与字典空间相加后,不一定相较于bit存储会有提升。(或许对压缩编码再次进行多次字典压缩,会有一定提升)
相较于连续位压缩,是一个相对较好的压缩算法,但是也不是完美的压缩方案。

五、经验总结

经过本次实验,感受到了动态规划法对于整体效率有着极大的影响。本次实验的动态规划方程相对简单,更多的工作在于对于路径的压缩工作。但是尝试多种压缩算法后,发现结果并不是十分显著,可能还是直接通过bit存储会比较节约空间。
还有就是最大规模的测试,有时算法的不足可以利用硬件去弥补,例如增加内存大小,可以使程序存储更大量的数据集。

0

评论区