Nameless Site

But one day, you will stand before its decrepit gate,without really knowing why.

0%

动态规划习题

Posted on Edited on In ,
Symbols count in article: 3.7k Reading time ≈ 3 mins.

动态规划

矩阵链乘法

笔记

本节给出了一个关于矩阵链相乘问题的动态规划算法。给定一个n个矩阵的矩阵链，要计算它们的乘积A1*A2*A3……An。矩阵乘法满足结合律，所以通过加括号，一个矩阵链的乘法可以按照不同的顺序进行。例如，4个矩阵的矩阵链，共有5种加括号的方式：

加括号的方式对矩阵链乘法的时间代价产生巨大的影响。我们先来分析两个矩阵相乘的时间代价。下面的代码给出了两个矩阵相乘的标准算法。

两个矩阵A和B只有相容，即A的列数等于B的行数时，才能相乘。如果A是 p×q 矩阵，B是 q×r 矩阵，那么乘积C是 p×r 矩阵。分析上面的代码，矩阵乘法的时间代价主要由最内层循环的标量乘法的次数决定，一共需要做 pqr 次标量乘法。

现在考虑计算矩阵链乘法的时间代价。以3个矩阵为例， 它们的维数分别为10×100、100×5和5×50，有以下两种加括号的方式：

  • 按((A1·A2)·A3)的顺序计算
    先(A1·A2)计算，需要做10×100×5 = 5000次标量乘法，得到的结果矩阵的维度为10×5；再与A3相乘，需要做10×5×50 = 2500次标量乘法。总共需要做5000+2500 = 7500次标量乘法。
  • 按(A1·(A2·A3))的顺序计算
    先计算(A2·A3)，需要做100×5×50 = 25000次标量乘法，得到的结果矩阵的维度为100×50;A1再与(A2·A3的结果相乘，需要做10×100×50 = 50000次标量乘法。总共需要做25000+50000 = 75000次标量乘法。

可以看到，第(2)种计算顺序的时间代价是第(1)种顺序的10倍。

矩阵链乘法问题:给定一个n个矩阵的矩阵链，矩阵Ai的维度为 (1 ≤ i ≤ n)，求一个最优的加括号方案，使得计算矩阵A1*A2*A3……An乘积所需要的标量乘法次数最少。
矩阵A1的维度为p0*p1，A2的维度为p1*p2，… …。以此类推，矩阵An的维度为pn-1*pn。矩阵的维度可以构成一个n+1元的数组{p0,p1……,pn}。以这个数组作为算法输入。
令P(n)表示n个矩阵的矩阵链的所有加括号的方案的数量。当n =1时，由于只有一个矩阵，所以P(1) = 1。当n ≥ 2时，可以先将矩阵链划分为两个子链和，其中k = 1,2,…, n-1，对两个子链加括号又是规模更小的子问题，因此矩阵链乘法问题满足最优子结构。由此，我们可以得到

易知道,P(n) = O(2^n)。显然，遍历所有加括号的方案，并不是一个明智的选择，这样的算法至少有一个指数增长的时间复杂度。现在我们用动态规划方法来求解这个问题。

用m[i, j]表示计算矩阵链所需标量乘法次数的最小值。如果i = j，矩阵链中只有一个矩阵，显然m[i, j] = 0。对于i < j 的情况，上文提到，可以先将矩阵链划分为两个子链和。左子链的乘积是一个矩阵，右子链的乘积是一个矩阵。假设两个子链的最优解已知，它们分别为m[i, k]和m[k+1, j ]，并且可以知道两个子链的结果相乘需要次pi-1·pk·pj 标量乘法。于是，可以得到m[i,j] = m[i,k] + m[k + 1,j] + pi-1·pk·pj。
矩阵链的划分点k可以取值i, i+1,…, j-1，我们需要检查k的所有可能的取值情况，并从中找到最优解。于是有

我们已经确立了问题的最优子结构，现在要合理安排子问题的求解顺序。子问题的规模是用相应的子链中矩阵的个数来度量的。我们要计算m[i, j]，只依赖于更短的子链的求解结果。因此，我们可以按照长度递增的顺序求解矩阵链乘法问题。另外，还需要在求解过程中记录下每个子问题的最优解的分割点位置k。以下是代码。

练习

T15.2-1 对矩阵链<5,10,3,12,5,50,6>，求矩阵链最有括号化方案

代码如下：

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
public class Main {

	static String [] A = {"A0","A1","A2","A3","A4","A5","A6"};//六个矩阵A1～A6 但是伪码是从下标1开始计算，因此在首位填充0
	static int [] p = {5,10,3,12,5,50,6};  //矩阵维数为p[i-1]*p[i]

	static int[][] matrix_chain_order(int [] p,int [][] matrix,int [][] brakcet,int n){
		for(int i = 1; i <= n; i++)
			matrix[i][i] = 0;
		for(int len = 2; len <= n; len++){
			for(int i = 1;i <= n- len + 1;i++){
				int j = i + len - 1;
				matrix[i][j] = Integer.MAX_VALUE; //设置为无穷大
				for(int k = i; k <= j - 1; k++){
					int mulTimes = matrix[i][k] + matrix[k + 1][j] + p[i - 1]*p[k]*p[j];
					if(mulTimes < matrix[i][j]){
						matrix[i][j] = mulTimes;
						brakcet[i][j] = k;
					}
				}
			}
		}
		for(int i = 1; i <= n ; i++){
			for(int j = 1; j <= n;j++)
				System.out.print(matrix[i][j] + " ");
			System.out.println(" ");
		}
		for(int i = 1; i <= n; i++){
			for(int j = 1; j<= n;j++)
				System.out.print(brakcet[i][j] + " ");
			System.out.println(" ");
		}
		return brakcet;
	}

	static void print_optimal_parens(int [][] brakcet,int i ,int j){
		if(i == j)
			System.out.print(A[i]);
		else{
			System.out.print("(");
			print_optimal_parens(brakcet,i,brakcet[i][j]);
			print_optimal_parens(brakcet,brakcet[i][j] + 1,j);
			System.out.print(")");
		}
	}
	public static void main(String[] args) {
		int [][] matrix = new int[7][7];
		int [][] brakcet = new int[7][7];
		for(int i = 0 ; i <= 6 ; i++)
			for(int j = 0 ; j<= 6 ;j++)
				matrix[i][j] = Integer.MAX_VALUE;

		brakcet = matrix_chain_order(p,matrix,brakcet,6);
		print_optimal_parens(brakcet,1,6);

	}

}

运行结果如下：

0 150 330 405 1655 2010
2147483647 0 360 330 2430 1950
2147483647 2147483647 0 180 930 1770
2147483647 2147483647 2147483647 0 3000 1860
2147483647 2147483647 2147483647 2147483647 0 1500
2147483647 2147483647 2147483647 2147483647 2147483647 0

0 1 2 2 4 2
0 0 2 2 2 2
0 0 0 3 4 4
0 0 0 0 4 4
0 0 0 0 0 5
0 0 0 0 0 0

((A1A2)((A3A4)(A5A6)))

最优二叉搜索树

笔记

二叉搜索树满足如下性质：假设x xx是二叉搜索树中的一个结点。如果l ll是x xx的左子树的一个结点，那么l.key≤x.key l.key ≤ x.keyl.key≤x.key。如果r rr是x xx的右子树的一个结点，那么r.key≥x.key r.key ≥ x.keyr.key≥x.key。
也就是说，二叉搜索树中的任意一个结点，它的左子树中的所有结点都不大于它，它的右子树中的所有结点都不小于它。下图给出了一个二叉搜索树的例子。

最优二叉搜索树(Optimal Binary Search Tree)问题描述如下。给定一个n nn个不同关键字的已排序的序列K[1..n]=（因此k1 ，表示搜索过程中可能遇到的所有不在K[1..n] K[1..n]K[1..n]中的元素。d0表示所有小于k1的元素；dn 表示所有大于kn 的元素；对i=1,2,…,n−1 i = 1, 2, …, n-1，di表示所有在ki到ki+1之间的元素。对每个伪关键字di，也有一个概率qi 表示对应的搜索概率。在二叉搜索树中，伪关键字di 必然出现在叶结点上，关键字ki 必然出现在非叶结点上。每次搜索要么成功（找到某个关键字ki），要么失败（找到某个伪关键字di）。关键字和伪关键字的概率满足：

假定一次搜索的代价等于访问的结点数，也就是此次搜索找到的结点在二叉搜索树中的深度再加1 11。给定一棵二叉搜索树T TT，我们可以确定进行一次搜索的期望代价。

其中depthT表示一个结点在二叉搜索树T中的深度。

对于一组给定的关键字和伪关键字，以及它们对应的概率，我们希望构造一棵期望搜索代价最小的二叉搜索树，这称之为最优二叉搜索树。现在我们用动态规划方法来求解最优二叉搜索树问题。

首先我们描述最优二叉搜索树问题的最优子结构：假设由关键字子序列K[i..j]= 和伪关键字子序列D[i−1..j]= 构成的一棵最优二叉搜索树以kr(i≤r≤j)为根结点。那么它的左子树由子序列K[i..r−1]和D[i−1..r−1]构成，这颗左子树显然也是一棵最优二叉搜索树。同样，它的右子树由子序列K[r+1..j]和D[r..j]构成，这颗右子树显然也是一棵最优二叉搜索树。
这里有一个值得注意的细节—空子树。如果包含子序列K[i..j]的最优二叉搜索树以ki为根结点。根据最优子结构性质，它的左子树包含子序列K[i..i−1]，这个子序列不包含任何关键字。但请注意，左子树仍然包含一个伪关键字di−1。同理，如果选择kj为根结点，那么右子树也不包含任何关键字，而只包含一个伪关键字dj。
用e[i,j] 表示包含关键字子序列K[i..j]= 的最优二叉搜索树的期望搜索代价。我们最终希望计算出e[1,n]。
对于j=i−1的情况，由于子树只包含伪关键字di−1 ，所以期望搜索代价为e[i,i−1]=qi−1。
当j≥i时，我们要遍历以ki,ki+1,…,kj作为根结点的情况，然后从中选择期望搜索代价最小的情况作为子问题的最优解。假设选择kr(i≤r≤j)作为根结点，那么子序列K[i..r−1]构成的最优二叉搜索树作为左子树，左子树的期望搜索代价为e[i,r−1]；子序列K[r+1..j]构成的最优二叉搜索树作为右子树，右子树的期望搜索代价为e[r+1,j]。
当一棵子树链接到一个根结点上时，子树中所有结点的深度都增加了1 ，那么这棵子树的期望搜索代价的增加值为它的所有结点的概率之和。对于一棵包含子序列K[i..j]的子树，所有结点的概率之和为

接上文，若kr(i≤r≤j)作为包含关键字子序列K[i..j]的最优二叉搜索树的根结点，可以得到如下公式 e[i,j]=pr+(e[i,r−1]+w[i,r−1])+(e[r+1,j]+w[r+1,j]) 由于w[i,j]=w[i,r−1]+pr+w[r+1,j]，所以上式可重写为 e[i,j]=e[i,r−1]+e[r+1,j]+w[i,j] 我们要遍历以ki,ki+1,…,kj作为根结点的情况，并选择期望搜索代价最小的情况作为子问题的最优解。于是我们可以得到下面的递归式。

e[i,j]给出了最优二叉搜索树子问题的期望搜索代价。我们还需要记录最优二叉搜索树子问题的根结点，用root[i,j]来记录。
根据上文给出的递归式，我们可以采用自下而上的动态规划方法来求解最优二叉搜索树问题。下面给出了伪代码。

练习

T15.5-2:若7 77个关键字的概率如下所示，求其最优二叉搜索树的结构和代价。

i 0 1 2 3 4 5 6 7
pi 0.04 0.06 0.08 0.02 0.10 0.12 0.14
qi 0.06 0.06 0.06 0.06 0.05 0.05 0.05 0.05

代码如下:

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
public class Main {

	static void optimal_bst(double [] p,double [] q,double [][] e,double [][] w, int [][] root){
		int n = p.length - 1;
		for(int i=1;i<=n+1;i++)
		{
			e[i][i-1] = q[i-1];
			w[i][i-1] = q[i-1];
		}
		for(int l=1;l<=n;l++)
		{
			for(int start = 1;start<=n-l+1;start++)
			{
				int end = start + l -1;
				w[start][end] = w[start][end-1] + p[end] + q[end];
				e[start][end] = 1000;
				for(int r = start;r<=end;r++)
				{
					double t = e[start][r-1] + e[r+1][end]  + w[start][end];
					if(t<e[start][end])
					{
						e[start][end] = t;
						root[start][end] = r;
					}
				}
			}
		}
	}

	static void print(int [][] root,int a, int b, int p){
		if(p == -1)
			System.out.println("k" + root[a][b] + "为根");

		int r = root[a][b];
		//左子树
		if(r == a)
		{
			System.out.println("d" + (a - 1) + "是k" + a + "d的左孩子");
		}
		else
		{
			System.out.println("k" + root[a][r-1] + "是k" + r +"的左孩子");
			print(root,a,r-1,0);
		}
		//右子树
		if(r == b)
		{
			System.out.println("d" + b + "是k" + b + "的右孩子");
		}
		else
		{
			System.out.println("k" + root[r+1][b] + "是k" + r + "的右孩子");
			print(root,r+1,b,0);
		}
	}
	public static void main(String[] args) {
		double [] p1 = {0,0.04,0.06,0.08,0.02,0.10,0.12,0.14};
		double [] q1 = {0.06,0.06,0.06,0.06,0.05,0.05,0.05,0.05};
		double [] p = new double[8];
		double [] q = new double[8];
		System.arraycopy(p1,0,p,0,8);
		System.arraycopy(q1,0,q,0,8);
		int n = 7;

		double [][] e = new double[n+2][n+2];
		int [][] root = new int[n + 2][n + 2];
		double [][] w = new double[n + 2][n + 2];
		optimal_bst(p,q,e,w,root);
		print(root,1,n,-1);
	}

}

运行结果如下：

k5为根
k2是k5的左孩子
k1是k2的左孩子
d0是k1d的左孩子
d1是k1的右孩子
k3是k2的右孩子
d2是k3d的左孩子
k4是k3的右孩子
d3是k4d的左孩子
d4是k4的右孩子
k7是k5的右孩子
k6是k7的左孩子
d5是k6d的左孩子
d6是k6的右孩子
d7是k7的右孩子

最优二叉搜索树如下所示。期望搜索代价为3.12。

图片及部分内容来自yangtzhou。