算法设计与分析试题及答案.doc

按分治策略求解棋盘覆盖问题时,对于如图所示的24×24的特殊棋盘,共需要多少个L型骨牌;并在棋盘上填写L型骨牌的覆盖情况。
物品
A
B
C
D
E
F
G
重量
35
30
50
60
40
10
25
价值
10
40
30
50
35
40
30
假设有7个物品,给出重量和价值。若这些物品均不能被分割,且背包容量M=140,使用回溯方法求解此0-1背包问题。请画出状态空间搜索树。
假设有7个物品,它们的重量和价值如下表所示。若这些物品均可以被分割,且背包容量M=140,使用贪心算法求解此背包问题。请写出求解策略和求解过程。
W(35,30,50,60,40,10,25)p(10,40,30,50,35,40,30)
在给出的电路板中,阴影部分是已作了封锁标记的方格,请按照队列式分支限界法在图中确定a到b的最短布线方案,要求布线时只能沿直线或直角进行,在图中标出求得最优解时各方格情况。
画出字符表的哈夫曼编码对应的二叉树。
已知,k=1,2,3,4,5,6,r1=5,r2=10,r3=3,r4=8,r5=5,r6=20,r7=6,求矩阵链积A1×A2×A3×A4×A5×A6的最佳求积顺序。
给出城市网络图,售货员要从城市1出发,经过所有城市回到城市1,画出该问题的解空间树,描述出用优先队列式分支限界法求解时的搜索情况。表示出优先队列、当前扩展结点等的变化情况。
依据优先队列式分支限界法,求从s点到t点的单源最短路径,画出求得最优解的解空间树。
假设有7个物品,它们的重量和价值如下表所示。若这些物品均不能被分割,且背包容量M=150,使用回溯方法求解此背包问题。请写出状态空间搜索树(20分)。

物品
A
B
C
D
E
F
G
重量
35
30
60
50
40
10
25
价值
10
40
30
50
35
40
30
答:按照单位效益从大到小依次排列这7个物品为:FBGDECA。将它们的序号分别记为1~7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得:【排序1分】
【状态空间搜索树及其计算过程17分,每个节点1分】
a.
b.
c.
d.
e.
f.
g.
h.
i.
j.
在Q1处获得该问题的最优解为,背包效益为170。即在背包中装入物品F、B、G、D、A时达到最大效益,为170,重量为150。【结论2分】
已知,k=1,2,3,4,5,6,r1=5,r2=10,r3=3,r4=12,r5=5,r6=50,r7=6,求矩阵链积A1×A2×A3×A4×A5×A6的最佳求积顺序。(要求:给出计算步骤)(20分)
答:使用动态规划算法进行求解。
求解矩阵为:【每个矩阵18分】
1
2
3
4
5
6
1
0
150
330
405
1655
2010
2
0
360
330
2430
1950
3
0
180
930
1770
4
0
3000
1860
5
0
1500
6
0
1
2
3
4
5
6
1
0
1
2
2
4
2
2
0
2
2
2