?0?1P初始如下：??1??1202**3034??*? 4??0?（3）根据P和A4，分别给出结点2到结点4，结点1到结点3的最短路径及长度
解: 计算得:
?0?21
A =??9??8?0?22
A =??5??81039103510351039?1502161502161502911027??0??911? P=??12???0??17??0??912? P=??22???0??17??0??913? P=??22???0??37??0??91? P4=??22???0??3202120232023202123032303410303034??1? 4??0?4??1? 4??0?4??1? 4??0?4??1? 2??0?
?0?23
A =??5??7
?0?24
A =??5??7结点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)} 1S={(0,0), (2,10)} S1={(5,15), (7,25)} 22S={(0,0), (2,10), (5,15), (7,25)} S1={(8,6), (10,16) ,(13,21), (15,31)} 33S={(0,0), (8,6), (10,16), (13,21), (15,31)} S1={(1,9), (9,15) ,(11,25), 4(14,30), (16,40)} 4S={(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 4721510418137120159 31070221003220703902710202230223 402 1230 最佳二叉排序树为: goto end stop print 45.设n=4, 且( a1,a2,a3,a4)=(do,if,read,while)，已知P(1:4)=(3,3,1,1)和Q(0:4)=(2,3,1,1,1)，使用动态规划方法构造一棵最佳二叉排序树（计算出C、 W、R阵的结果）。 解: ?0?? C=?????80197025123032??2??19??8? W= ???3???0???8312711493116??0??11??5? R=???3???1???1012022302??2?3? ?4?0?? 最佳二叉排序树为: IF DO READ WHILE 46．①证明算法OBST的计算时间是O(n2)。 ②在已知根R(i, j)，0≤i < j≤4的情况下写一个构造最优二分检索树T的算法。证明这样的树能在O(n)时间内构造出来。 解：① 将C中元素的加法看做基本运算，则算法OBST的时间复杂性为： nn?mnn?m ??(R(i?1,j)?R(i,j?1)?1)???(R(i?1,i?m)?R(i,i?m?1)?1)?m?2i?0m?2i?0n?(R(n?m?1,n)?R(0,m?1)?n?m?1)?O(n) m?22 ② Procedure BuildTree(m, n, R, Root) integer R(n,n), k TreeNode Root, LR, RR k←R(m,n) if k≠0 then data(Root)←k, BuileTree(m, k-1, R, LR), BuileTree(k, n, R, RR) left(Root)←LR, right(Root)←RR else data(Root)←m, left(Root)←null, right(Root)←null, endif end BuildTree 时间复杂性分析：T(n)=c+T(k)+T(n-k-1)，此递推式保证算法的时间复杂性为O(n)，也可从递归的角度出发，递归的次数正是结点的个数，而每次递归时间复杂性为常数，所以算法的时间复杂度也为O(n)。 47.设计一个由设备D1,D2,D3组成的三级系统。每台设备的成本分别为30元、15元和20元，可靠性分别为0.9,0.8和0.5，计划建立该系统的投资不得超过105元。假定级有mi台设备Di并联，则该级的可靠性?i(mi)?1?(1?ri)mi。使用 序偶集合的方法求解该问题（要求给出求解过程中产生的所有序偶集合）。 解：s11 ={(0.9,30)} s1={(0.99,60)} 2S={(0.9,30) , (0.99,60)} s1={(0.72,45),(0.792,75)} s2={(0.864,60)} s3={(0.8928,75)} 2221S={(0.72,45), (0.864,60),(0.8928,75)} s1={(0.36,65),(0.432,80),(0.4464,95)} 32s2={(0.54,85),(0.648,100)} s3={(0.63,105)} 33S={(0.36,65),(0.432,80),(0.54,85),(0.648,100)} 3最优设计有0.648的可靠性,需用资金100元。 m1=1, m2=2, m3=2。 48.对于有a，b两台设备的流水线调度问题，设数组A(n)，B(n)分别存储a，b的任务完成时间。A=(1,5,3,9,7), B=(4,2,8,6,10)，给出这四个作业的调度序列,并给出调度图和调度时间. 答: 对A,B分类后的序列是{a1,b2,a3,b1,a2,b4,a5,b3,a4,b5} 得调度序列为{1,3,5,4,2} 49.修改算法6.1和6.2，使它们只求出问题的一个解而不是问题的全部解 算法6.1 procedure BACKTRACK(n) integer k,n; local X(1: n) k ← 1 while k>0 do if还剩有没检验过的X(k)使得 X(k) ∈ T ( X(1), ? ,X(k-1)) and Bk ( X(1), ? ,X(k)) = true then if ( X(1), ? ,X(k) ) 是一条抵达一答案节点的路径 then print ( X(1), ? ,X(k)) return endif k ←k ＋ 1 else k ←k － 1 endif repeat end BACKTRACK 算法6.2 procedure RBACKTRACK(k) global n, X(1:n) for 满足下式的每个X(k) X(k) ∈ T ( X(1), ? ,X(k-1)) and Bk ( X(1), ? ,X(k)) = true do if ( X(1), ? ,X(k))是一条抵达一答案结点的路径 then print ( X(1), ? ,X(k)) return endif call RBACKTRACK(k+1) repeat end RBACKTRACK 50．在关于解空间树结构的术语中，什么是活结点？什么是E-结点？什么叫答案状态？什么是死结点？ 51．什么是状态空间树？回溯法求解问题的过程中，状态空间树所有结点没有完全遍历到，但为什么能够得到所有的解？
相关推荐：
loading