《算法导论》学习总结 — 17.第15章 动态规划(2) 案例之装配线调度

原来打算把算法导论在7月份前搞定,现在已经过去一个多月了,才只看到第15章,后面也只零散看了一些,不知道假期前能否看完。。。够呛啊,马上要期末考试了,上学期GPA不到2,被学位警告了,虽说以后不学这个专业了,但起码成绩单上也不能有挂科是吧。。。要是平时一点不看,考前靠春哥,曾哥,关公哥都不行啊。。。这进度,郁闷!

尽力吧!

顺便还是说两句话:

1.有些书上分析的相当好了,我不想做画蛇添足的人,所以有的地方我会适当省略,当然也不是说我总结的地方就是书上讲的不好的地方,只是没人有一套自己的理解方式,我用自己的话去总结了,当时也就是最适合我的知识!所以,建议大家多写一些算法总结,你会体会到好处的!

2.而且我这个的性质是总结,不是对一个算法的具体讲解,所以不先看书,大家应该读不懂的,就比如下面,题目我就没有贴出来,大家不看数,肯定就读不懂,我的目的是大家看完书后,谢谢总结,或者看看别人写的总结,说不定可以发现自己哪些地方理解错了,哪些地方不理解,或是哪些地方值得探讨。

建议先看看前言:http://www.wutianqi.com/?p=2298

这一次主要是分析15.1节的例子—装配线调度问题。

题目有点长,首先得把题目读懂。

这个例子书上花了6面纸的篇幅来详细分析,由此可见其重要性。

谈到DP,不得不说的就是暴力法,大家都知道,如果用暴力解决类似问题,一般时间复杂度都是非常非常的高,这个时候救世主DP就出来了,DP以避免了许多重复的计算,而大大降低了时间复杂度。

按照书上的四个步骤,我在这里提取一些重点,建议还是把P194~196这四步完整步骤看书上的分析。只有慢慢品味,你才会发现《算法导论》的美。

步骤一

分析问题,比如一个底盘要到达S[1][j],则有两种情况,第一种是从S[1][j-1]到S[1][j],第二种是从S[2][j-1]到S[1][j]。找出这两者所花时间的最小,则就是S[1][j]所需时间的最小。

这就是有局部最优解求全局最优解。也就是说,一个问题的最优解包含了子问题的一个最优解。我们称这个性质为最优子结构。这是是否可以应用DP的标志之一。

步骤二

找出这个递归关系,由步骤一可以得到这个递归关系:

15_2

步骤三

因为递归的关系,一般总是可以转换为非递归的算法。

由已知量f1[1], f2[1]逐步推出未知量,推啊推,推啊推,最后就推到结果了~~~~

步骤四

再由已知结果返回求路径。

这一节最给力的就是这个例子以及相应的

15_3

拿起笔,用书上给出的例子,分析这个图!

以下是代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
/*
Author: Tanky Woo
Blog:   www.WuTianQi.com
About:  《算法导论》15.1 装配线调度
*/
#include <iostream>
using namespace std;
 
int n;                 // 一个装配线上有n个装配站
int e1, e2;            // 进入装配线1,2需要的时间
int x1, x2;            // 离开装配线1,2需要的时间
int t[3][100];         // t[1][j]表示底盘从S[1][j]移动到S[2][j+1]所需时间,同理t[2][j]
int a[3][100];         // a[1][j]表示在装配站S[1][j]所需时间
int f1[100], f2[100];  // f1[j], f2[j]分别表示在第一/第二条装配线上第j个装配站的最优解
int ln1[100], ln2[100];// ln1[j]记录第一条装配线上,最优解时第j个装配站的前一个装配站是第一条线还是第二条线上
int f, ln;             // 最优解是,f代表最小花费时间,ln表示最后出来时是从装配线1还是装配线2
 
void DP()
{
	f1[1] = e1 + a[1][1];
	f2[1] = e2 + a[2][1];
	for(int j=2; j<=n; ++j)
	{
		// 处理第一条装配线的最优子结构
		if(f1[j-1] + a[1][j] <= f2[j-1] + t[2][j-1] + a[1][j])
		{
			f1[j] = f1[j-1] + a[1][j];
			ln1[j] = 1;
		}
		else
		{
			f1[j] = f2[j-1] + t[2][j-1] + a[1][j];
			ln1[j] = 2;
		}
		// 处理第二条装配线的最优子结构
		if(f2[j-1] + a[2][j] <= f1[j-1] + t[1][j-1] + a[2][j])
		{
			f2[j] = f2[j-1] + a[2][j];
			ln2[j] = 2;
		}
		else
		{
			f2[j] = f1[j-1] + t[1][j-1] + a[2][j];
			ln2[j] = 1;
		}
	}
	if(f1[n] + x1 <= f2[n] + x2)
	{
		f = f1[n] + x1;
		ln = 1;
	}
	else
	{
		f = f2[n] + x2;
		ln = 2;
	}
}
 
void PrintStation()
{
	int i= ln;
	cout << "line " << i << ", station " << n << endl;
	for(int j=n; j>=2; --j)
	{
		if(i == 1)
			i = ln1[j];
		else
			i = ln2[j];
		cout << "line " << i << ", station " << j-1 << endl;
	}
}
 
int main()
{
	//freopen("input.txt", "r", stdin);
	cout << "输入装配站的个数: ";
	cin >> n;
	cout << "输入进入装配线1,2所需的时间e1, e2 :";
	cin >> e1 >> e2;
	cout << "输入离开装配线1, 2所需的时间x1, x2: ";
	cin >> x1 >> x2;
	cout << "输入装配线1上各站加工所需时间a[1][j]: ";
	for(int i=1; i<=n; ++i)
		cin >> a[1][i];
	cout << "输入装配线2上各站加工所需时间a[2][j]: ";
	for(int i=1; i<=n; ++i)
		cin >> a[2][i];
	cout << "输入装配线1上的站到装配线2上的站所需时间t[1][j]: ";
	//注意这里是i<n,不是i<=n
	for(int i=1; i<n; ++i)
		cin >> t[1][i];
	cout << "输入装配线2上的站到装配线1上的站所需时间t[2][j]: ";
	for(int i=1; i<n; ++i)
		cin >> t[2][i];
	DP();
	cout << "最快需要时间: " << f << endl;
	cout << "路线是: " << endl;
	PrintStation();
	cout << endl;
}

最后还是要感叹一下,《算法导论》讲的真是棒极了,希望大家能静下心把这一章节好好看看。

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《《算法导论》学习总结 — 17.第15章 动态规划(2) 案例之装配线调度》有2个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注