R(0)?0?0???0??0100000000??0??10(1)? R???01???0??0100000000??0??10(2)? R???01???0??0100000001??1? 1??0?
?0?0???0??0100000001??0??10(4)? R???01???0??0100000001??1? 1??0?R(3)3. 如果不使用额外的存储空间来存储warshall算法中间矩阵的元素,如何实现? Hints:
Warshall算法计算新矩阵是按下面的递推关系:
(k-1)(k)
可以看出从R生成R时,第k行和第k列的并没有改变.因此,对每个i,j来说,第i
(k)(k-1)
行第j列的新值R[i,j]可以覆盖对应位置上的R[i,j]
4. 如何重构warshall算法最内层循环,使得它到少对于某此输入来说运行得列快? hints:
(k-1)
如果R[i,k]=0,那么 R(k)(k?1)?[i,j]?R[i,j]??(k?1)?[i,k]andR?R(k?1)[k,j](k-1)
?R(k?1)[i,j],则不需要进行最内层循环.
由于R[i,k]不依赖于j,所以R[i,k]=0这个判断可以在最内层j循环外面进行.算
法改进如下:
Warshall2(A[1..n,1..n])
//内层循环更有效的Warshall 算法 //输入:n节点的有向图的邻接矩阵A //输出:该图的传递闭包A for k←1 to n do for i←1 to n do if A[i,k]
for j←1 to n do if A[k,j]
A[i,j]=true Return A 习题8.3
1.完成本节构造最优二叉查找树例题中余下的计算. 解:
(k-1)
36
2.a. 算法optimalBST的时间效率为什么是立方级? b. 算法optimalBST的空间效率为什么是平方级? 解:a.最内层循环执行的次数:
37
b. 算法optimalBST使用了两个表:C--(n+1)×(n+1),R--n×n,并且每个表只填了一半. 3.写一个线性时间算法的伪代码,来从根表中生成最优二叉查找树 Algorithms OptimalTree(i,j) //输入:有序列表的第一和最后序号
//输入:先序遍历最优二叉查找树节点编号的列表
38
习题9.1 1、 2、
给出一个找零问题的实例,使得贪婪算法不能输出一个最优解.
为找零问题写一个贪婪算法的伪代码,它以金额n和硬币的面额d1>d2>…>dm作为输入.以n的函数形式给出该算法的效率类型.
Hints:
Algorithms change(n,D[1..m]) //用贪婪法求找零问题
//输入:非负整数n,硬币面额以降序排列的数组D
//输出:数组A[1..m]----每种面额硬币的数量,或者无解
习题9.4 1.(题略) a.
39
b. c.
b.该问题的实例中共有多少个不同的最优子集？ 解答：只有一个，为{0,0,1,0,1}
c.一般来说，如何从动态规划算法所生成的表中判断背包问题的实例是不是具有不止一个最优子集？
40
解答：一般来说，可以通过判断表中最后一列的最大值个数来判断，因为背包问题的最优值的产生只会在最后一列产生。
41