算法复习题(5)

33．当作业数n＝7，

（p1，p2，??，p7）＝（7, 6, 5, 4, 3, 2, 1） （d1，d2，??，d7）＝（4, 2, 4, 3, 1, 4, 6）

时，利用算法5.5（作业排序的更快算法）求解上述作业排序问题的最优解。（要求按步骤运行并给出集合树的变化情况及当前最优解）。

34．举例说明最优性原理是什么？

最优性原理是指，过程的最优决策序列具有如下性质：无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。

例如：

35．举例说明支配规则的内容。

36．由最优性原理指出的过程的最优决策序列具有的性质是什么？

答：无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。 37．什么样的决策过程构成多阶段决策过程？

答：活动过程可以分为若干个阶段，而且在任一阶段后的行为都仅依赖于i 阶段的过程状态，而与i 阶段之前如何到达这种状态的方式无关，这样的过程就构成一个多阶段决策过程。

38．使用动态规划求解问题的前提条件是什么？试举出两个例子，这两个例子都可以看作是多阶段决策问题，但一个例子可以用动态规划来解，而另一个例子不能用动态规划求解。

39．修改过程ALL_PATHS，使其输出每对结点（i,j）间的最短路径，这个新算法的时间和空间复杂度是多少？

Procedure ShortestPath(COST, n, A, Max)

integer i , j, k

real COST(n, n), A(n, n), Path(n, n), Max

for i←1 to n do

for j←1 to n do

A(i ,j)←COST(i ,j)

if i≠j and A(i, j)≠Max then Path(i, j )←j else Path(i, j)←0 endif

repeat repeat

for k←1 to n do

for i←1 to n do for j←1 to n do

if A(i,j)>A(i,k)+A(k,j)

then A(i,j)←A(i,k)+A(k,j) Path(i,j)←Path(i,k) endif

repeat repeat

repeat

for i←1 to n do

for j←1 to n do

print(“the path of i to j is ” i )

k←path(i, j) while k≠0 do print( ,k) k←path(k, j) repeat repeat

repeat

end ShortestPath

时间复杂度O(n3)，空间复杂度O(n2) 40.已知图的邻接矩阵

?01?7??2015???? ?9302????8?20?（1）按照每对结点间的最短路径算法ALL-PATH，求每对结点间的最短路径长度矩阵A4

（2）求路径结点矩阵P。P(i,j)表示从i到j的最短路径的第一步结点。

?0?1P初始如下：??1??12*4?03*?? 204??*30?（3）根据P和A4，分别给出结点2到结点4，结点1到结点3的最短路径及长度

解: 计算得:

?0?2A1 =??9??817??0?10159?? P1=??1302???920??1?204?031?? 204??130??0?22

A =??5??81167??0?10159?2? P=??2302???920??1224?031?? 204??130?

?0?23

A =??5??71167??0?10159?3? P=??2302???520??3224?031?? 204??330?

?0?2A4 =??5??717??0?10119?? P4=??2302???520??39244?011?? 202??330?结点2到结点4的最短路径长为9，最短路径是2→1→4. 结点1到结点3的最短路径长为9，最短路径是1→4→3.

41．给出一个使得DKNAP(算法6.7)出现最坏情况的例子，它使得|Si|=2i, 0≤i

解：取(P1,P2,?,Pi,?)=(W1,W2,?,Wi,?)=(20,21,?,2i-1,?)

P和W取值相同，使支配原则成立，也就是说不会因为支配原则而删除元素；只要说明不会出现相同元素被删除一个的情形，即可知是最坏的情况。可用归纳法证明此结论。

42．①递推关系式（6.8）对(P151,图6.16)成立吗？为什么？ ②递推关系式（6.8）为什么对于含有负长度环的图不能成立？ 解：①成立，不包含负长度环 ②可以使节点间的长度任意小。

43.设0/1背包问题中(w1,w2,w3,w4)=(10,15,6,9),(p1,p2,p3,p4)=(2,5,8,1),对0≤i≤4，生成每个fi阶跃点的序偶集合Si。 解：S0={(0,0)} S11={(2,10)}

S1={(0,0), (2,10)} S12={(5,15), (7,25)}

S2={(0,0), (2,10), (5,15), (7,25)} S13={(8,6), (10,16) ,(13,21),

(15,31)}

S3={(0,0), (8,6), (10,16), (13,21), (15,31)} S14={(1,9),

(9,15) ,(11,25), (14,30), (16,40)}

S4={(0,0), (8,6), (9,15), (10,16), (13,21), (14,30), (15,31), (16,40)}

44.对于标识符集（a1,a2,a3,a4）=（end, goto, print, stop），已知已知P(1:4)=(1，4，2，1)和Q(0:4)=(4，2，4，1，1)。使用动态规划方法构造一棵最佳二叉排序树（计算出C、W、R阵的结果）。

解: 矩阵W 矩阵C 矩阵R

4715182021013154719 3107223239010202707012 30012220222033

040

最佳二叉排序树为:

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库算法复习题(5)在线全文阅读。