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

一、假设有 7 个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量 M ＝150，使用回溯方法求解此背包问题。请写出状态空间搜索树（20 分）。 物品 A B C D 重量 35 价值 10 30 40 60 30 50 50 E 40 35 F 10 40 G 25 30 答：按照单位效益从大到小依次排列这 7 个物品为：FBGDECA。将它们的序号分别记为 1～7。 则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得：【排序 1 分】 x  1 a x 2  x  3 0 x  4 1 e x  5 0 a x  1 0 j 0 x  4 h 1 0 e i g x  3 1 a x  4 0 x  2 1 a d x 5 1  e x  6 0 f 1 x  4 a x  5 0 x  6 0 x  7 0 b c Q 1       40 40 30 50 35     b. 每个节点 1 分】 a． 40 40 30 50 30  40  60 c． 40 40 30 50 10 170  d. 60  60 40 40 30 35 30 40 40 50 35 30 e.               150 115 150 115  150 105 150 130 【状态空间搜索树及其计算过程 17 分，  190.625 (1,1,1,1, 7 8 ,0,0)  177.5 (1,1,1,1,0, 7 12 (1,1,1,1,0,0,1) ,0)  167.5 (1,1,1,0,1, 3 4 ,0)  175 (1,1,0,1,1, 1 3 ,0) 

f. 40 40 50 35 10      150 130  35  170.71 (1,1,0,1,1,0, 4 7 ) g. 40 40 50 30 160     h. 40 40 35 30 10     40 30 50 35 30      40 30 50 35 30      i. j. (1,1,0,1,0,1,0) 146.85 (1,1,0,0,1,1, 2 7 ) 167.5 (1,0,1,1,1, 5 12 ,0)  157.5 (0,1,1,1,1, 1 12 ,0)   150 140  35 150 125  60 150 145   60 在 Q1 处获得该问题的最优解为 (1,1,1,1,0,0,1) ，背包效益为 170。即在背包中装入物品 F、B、G、 D、A 时达到最大效益，为 170，重量为 150。【结论 2 分】 一、 已知 A k  ( a ij ( k ) ) i * r r i 1  ，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 分】 2 150 0 2 1 0 3 330 360 0 3 2 2 0 4 405 330 180 0 4 2 2 3 0 1 0 1 0 1 2 3 4 5 6 1 2 3 4 5 6 5 1655 2430 930 3000 0 5 4 2 4 4 0 6 2010 1950 1770 1860 1500 0 6 2 2 4 4 5 0 因此，最佳乘积序列为（A1A2）（（A3A4）（A5A6）），共执行乘法 2010 次。【结论 2 分】 

二、 假设有 7 个物品，它们的重量和价值如下表所示。若这些物品均可以被分割，且背包容 量 M＝150，如果使用贪心方法求解此背包问题，请回答：（20 分）。 （1） 对各个物品进行排序时，依据的标准都有哪些？ （2） 使用上述标准分别对 7 个物品进行排序，并给出利用各个顺序进行贪心求解时获得解。 （3） 上述解中哪个是最优的？ 物品 A B C D E 重量 35 价值 10 30 40 60 30 50 50 40 35 F 10 40 G 25 30 答： （1）标准：重量、价值和单位价值。【3 分，每个 1 分】 （2）使用重量从小到大：FGBAEDC。得到贪心解为：FGBAE 全部放入，而 D 放入 20%，得到 价值为 165。【5 分】 使用价值从大到小：DFBEGCA，得到贪心解为：DFBE 全部放入，而 G 放入 80%，得到价值为： 189。【5 分】 使用单位价值从大到小：FBGDECA，得到贪心解为：FBGD 全部放入，而 E 放入 87.5%，得到价 值为 190.625。【5 分】 （3）显然使用单位价值作为标准得到的是最优解。【2 分】 三、 对于下图使用 Dijkstra 算法求由顶点 a 到其他各个顶点的最短路径。并给出求各个顶点对 之间的最短路径的算法思想。（20 分）。 答：三、用 V1 表示已经找到最短路径的顶点，V2 表示与 V1 中某个顶点相邻接且不在 V1 中的顶点； E1 表示加入到最短路径中的边，E2 为与 V1 中的顶点相邻接且距离最短的路径。【1 分】 

V2 步骤 V1 {b} {a} 1. {d} {a,b} 2. {c,f} 3. {a,b,d} {f} {a,b,d,c} 4. {e} {a,b,c,d,f} 5. {g} 6. {a,b,c,d,e,f} {a,b,c,d,e,f,g} {h} 7. 8. {a,b,c,d,e,f,g,h} {} 结果：从 a 到 h 的最短路径为 a E1 {} {ab} {ab,bd} {ab,bd} {ab,bd,dc,df} {ab,bd,dc,df,fe} {ab,bd,dc,df,fe,eg} {ab,bd,de,df,fe,eg,gh}       ，权值为 18。【1 分】 E2 {ab} {bd} {dc,df} {df} {fe} {eg} {gh} {} 【以上每步 2 分】 b d f e g h 求所有顶点对之间的最短路径可以使用 Dijkstra 算法，使其起始节点从 a 循环到 h，每次求起 始节点到其他节点的最短路径，最终可以求得所有顶点对之间的最短路径。【2 分】