算法分析与设计实验指导书样本.doc

资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。
算法分析与设计

本书是为配合《计算机算法分析与设计》而编写的上机指导, 其目的是使学生消化理论知识, 加深对讲授内容的理解, 增强算法分析与设计实践动手能力。
上机实验注意事项如下:
( 1) 课前认真做好预习, 准备好实验工具, 熟悉实验流程和手段。
( 3) 课中根据实验指导书, 结合课本实例进行编程实验。实验时, 一人一组, 独立上机调试, 上机时出现疑问, 能够举手询问实验指导老师, 或者与周边同学小声讨论, 鼓励独立解决问题。
( 4) 课后按时按质按量整理出实验报告。实验报告应独立完成, 拒绝抄袭。
实验内容覆盖: 递归与分治策略、 动态规划、 贪心算法、 回溯法、 分支限界法等。
实验一 递归与分治策略
一． 实验目的与要求
（1） 理解和掌握递归与分治策略的基本原理。
（2） 理解课本中的示例代码。
（3） 调试代码经过。
二． 递归与分治的基本思想
（1） 递归与分治方法。
递归与分治方法的基本思想是: 将一个难以解决的大问题, 分割成一些规模较小的、 相同的子问题, 以便各个击破, 分而治之。
（2） 递归。
递归问题分析时, 要把握如下两个要素:
l 递归出口。
l 递归公式。
其中:
l 递归出口给出了最简单情况下问题的解。
l 递归公式则给出了一般意义下大问题( 原问题) 和小问题( 子问题) 之间的递归关系。经过递归公式, 一个难以解决的大问题会随着递归不断分解为多个小问题, 小问题继续递归变为更小的小问题, 直到最后到达递归出口得到解。
三． 实验代码分析和说明
本部分实验, 需完成”棋盘覆盖”( 课本P20) 和”快速排序”( 课本P22) 两个问题。
3.1 棋盘覆盖
1. 棋盘覆盖问题的思路:
（1） 首先, 将原始的棋盘覆盖问题看作最初的大问题。
（2） 然后, 将棋盘的行、 列一分为二, 从而将原始的大棋盘分为四个同样大小的小棋盘。
（3） 接着, 采用P21的图2-5中合适的L型骨牌, 覆盖原始大棋盘的中心位置, 将四个同样大小的小棋盘都转化为特殊棋盘。
（4） 最后, 对四个特殊小棋盘进行递归处理即可。
以上步骤( 2) 和步骤( 3) 合起来, 完成了将大问题划分为小问题的过程, 特别需要注意的是: 小问题必须要和大问题相同或相似, 否则无法递归。具体到本例当中, 注意步骤( 3) 选取L型骨牌时, 必须要能够将原始大棋盘转化为四个小的特殊棋盘。如果不是转化为四个小的特殊棋盘, 显然L型骨牌选择是不正确, 因为此时无法进行递归处理。
小问题必须和大问题相同或者相似, 是采用递归与分治方法的重要一点, 必须掌握。
2. P21代码的说明。
（1） ChessBoard的输入参数: tr是左上角方格的行坐标( table row) , tc是左上角方格的列坐标( table column) ; dr是特殊方格的行坐标, dc是特殊方格的列坐标; size是棋盘大小。
（2） 以覆盖左上角为例,
if (dr < tr+s && dc < tc + s)
该判断条件判断特殊方格是否在左上角小棋盘中。
如果在, 就直接进行递归, 即: ChessBoard( tr, tc, dr, dc, s) 。
如果不在, 那么首先用t号骨牌覆盖( 具体选择P21中的哪种骨牌, 参见前述说明) 。覆盖之后, 左上角的小棋盘就变成了特殊小棋盘, 此时就能够递归处理了, 即: ChessBoard(tr, tc, tr+s-1, tc+s-1, s)。
【问题】前后两次递归, ChessBoard的参数为什么这样设置?
3.2 快速排序
1. 快速排序的基本思路。
假设需要排序的数存储在数组”a[p], a[p+1], ……, a[r]”中。为了描述方便, 将上述数组简记为: a[p:r]。
（1） 首先, 以a[p]为基准元素, 将a[p:r]划分为三段, 分别是: a[p: q-1], a[q], a[q+1: r]。其中, a[p: q-1]中的任何一个元素都小于等于a[q]; a[q]小于等于a[q+1: r]中的任何一个元素。注意: 算法工作时, 以a[p]为基准进行a[p:r]划分; a[q]是在划分完成时确定的。
（2） 对划分得到的a[p: q-1]和a[q+1: r]类似地, 进行划分。
（3） 注意到a[p: q-1], a[q], a[q+1: r]的关系, 不要任何计算, 数组a[p: r]就已经自动排好序。
【问题】快速排序的上述思想中, 是如何体现”将大问题划分为相同或相似的小问题”的?
四． 实验内容
（1） 完成代码, 并调试经过。
（2） 回答实验指导书中的问题。
（3） 体会递归与分治策略的基本思想, 以及在编程中如何实现。

实验二 动态规划
一． 实验目的与要求
（1） 理解动态规划的基本思想。
（2） 理解课本中示例代码并调试经过。
（3） 根据自己的理解, 回答实验指导书中的问题。
二． 动态规划的基本思想
（1） 动态规划问题需要满足两个特征, 分别是:
l 最优子结构性质。即: 大问题的最优解当中, 包含了子问题的最优解。这是利用动态规划解决问题的最关键特征。
l 重叠子问题。即: 动态规划问题中, 许多子问题被重复计算。因此, 动态规划将这些需要重复计算的子问题保存下来, 当下次需要的时候, 只需要查询即可, 从而能够提高算法的效率。
（2） 动态规划本质上也是一种”递归与分治”的思想。只是, 与普通的递归与分治问题相比, 动态规划问题具有自己另外的特征, 即: 最优子结构性质+重叠子问题, 从而在递归与分治的基础上, 再采用特殊手段( 如记录重叠子问题) , 能够进一步提升效率。也就是说, 动态规划问题是一种特殊的”递归与分治”问题。
（3） 动态规划方法有一种变形, 叫做备忘录方法。两者的关系是: 备忘录方法是动态规划的一种变形, 两者的思想是一致的。两者的区别是: 动态规划方法采用自底向上的方法, 备忘录方法采用自顶向下的方法。两者的适用场景是: 如果一个问题的所有子问题都需要至少求解一次时, 采用动态规划方法较好; 如果一个问题中只是部分子问题需要求解时, 采用备忘录方法较好。
三． 实验代码分析和说明
本部分实验完成”矩阵连乘”问题( P45-P48) 和”0-1背包”问题( P71-73) 。
3.1 矩阵连乘问题
1. 矩阵连乘问题基本思想。
假设有任意矩阵Ai*Ai+1*…*Aj共有( j-i+1) 个矩阵相乘。为了描述方便, 记为A[i:j]。即: A[i:j]= Ai*Ai+1*…*Aj。显然, A[i:j]一定是有一个最优的计算次序的, 虽然不知道这个最优次序是多少, 可是不妨假设是从Ak处断开。换句话说, 对于A[i:j], 其最优计算次序为: (Ai*…*Ak) * (Ak+1*…*Aj)。显然, 上述计算次数由三部分构成。构成1: (Ai*…*Ak)的计算次数, 用X表示; 构成2: (Ak+1*…*Aj)的计算次数, 用Y表示; 构成3: (Ai*…*Ak)和(Ak+1*…*Aj)的乘积, 也就是( A[i]的行数*A[k]的列数*A[j]的列数) 。用公式表示如下:
A[i:j]的计算次数 = X + Y + A[i]的行数*A[k]的列数*A[j]的列数
注意到: 由于已经固定从Ak处断开, 因此构成3是一个定值。因此, 要A[i:j]的计算次数最少, 就需要X和Y分别是最小。这说明: 原问题A[i:j]的最优解包含了子问题A[i:k]和子问题A[k+1:j]的最优解。因此, 能够使用动态规划算法。
2. 动态规划算法的递归公式
如果用m[i][j]表示A[i:j]的最优值, 那么有:
( 1) 如果i=j, A[i:j]是单独一个矩阵, 不需要计算, 因此, m[i][j]=0;
( 2) 如果i<j, 那么根据上述分析, m[i][j]=min{m[i][k]+m[k+1]+ A[i]的行数*A[k]的列数*A[j]的列数}
递归公式的形式化形式参见P47顶上。
3. P47代码说明。
( 1) MatrixChain的输入参数: p记录了数组链A[0:n]的列数信息; n是相乘的数组的个数; m记录的是最优值; s记录了断开位置。
( 2) 算法中, 循环变量r用来控制循环变量i和j之间的距离, 完成如下计算。每计算一个子问题, 就将子问题的计算结果记录到m当中。这样, 当计算大问题的时候, 能够直接查询m得到。计算次序和过程如下( 从左到右, 从上到下) :
m[1][2] m[2][3] …… m[n-3][n-2] m[n-2][n-1] m[n-1][n]
m[1][3] m[2][4] …… m[n-3][n-1] m[n-2][n]
m[1][4] m[2][5] …… m[n-3][n]
……
m[1][n-1] m[2][n]
m[1][n]
【问题】理解算法的工作流程。
3.2 0-1背包问题
1. 0-1背包问题基本思想。
0-1背包问题也满足最优子结构性质, 证明如下。
设是所给0-1背包问题的一个最优解, 则是下面相应子问题的一个最优解:

证明: 采用反证法。
假设不是上述子问题最优解, 那么假设是上述问题的最优解。代入子问题可得:
, 以及

由有: ;
由有: 。
以上两式说明, 比更优, 这与是最优解相矛盾。
2. 0-1背包问题的递归公式
用表示背包容量为, 可选择物品为从号的物品( 即可选物品为) 时0-1背包问题的最优值。那么由最优子结构性质, 能够建立如下递归公式:
一般情形:
特殊情形:
上述递归公式解释如下:
( 1) 首先, 对于一般情形。
的含义是: 如果, 则说明第个物品( 该物品的重量为) 的重量小于当前背包的容量, 因此能够选择该物品, 也能够不选择该物品。其中, 计算不选择该物品的结果; 计算选择该物品的结果( 的含义是: 选择了物品, 因此背包容量变为。同时, 背包的最优价值变为, 再加上所选择的号物品的价值) 。并选取两者的最大值作为最优值。
的含义是: 如果, 则说明物品 重量超过了背包的容量, 因此不能选取。
( 2) 其次, 对于特殊情形。
当只有一个物品时, 如果背包容量还能够容纳物品, 则选择该物品, 因此价值为; 否则不能选择该物品, 价值为0。
3. P71-P73代码说明。
( 1) 本算法针正确是背包容量和每个物品的重量都为整数的情形。对于实数情形不能处理。
( 2) 算法输入: v是数组, v[i]代表物品i的价值; w是数组, w[i]代表物品i的重量; c是背包现有容量; n是物品数量; m是数组, m[i][j]的含义是: 在背包容量为j, 可选物品为( i, i+1, ..., n)的情况下的最优解。
( 3) 算法输出: 背包问题最优解。
( 4) 第一行: jMax=min(w[n]-1, c)。
本质等价于: , 从函数的定义容易证明。
( 5) 第二三行的两个for循环。
对应于P72的特殊情形, 也就是递归出口。
其中, 第二行的for对应于P72特殊情形中的情况; 第三行的for对应于P72特殊情形中的情形。
( 6) 第四、 六、 七行的for循环。
对应于P72的一般情形, 也就是递归公式。
第五行的jMax=min(w[i]-1, c), 其含义同上, 本质上等价于。
第四行for循环中, 逐步缩减到, 采用的是动态规划的方法, 先计算小问题并记录下来, 再根据小问题已有的结果, 计算大问题, 最后得到原问题的解。
第六行和第七行的for循环, 对应于P72的一般情形。其中, 第六行对应的是P72中的; 第七行对应的是P72中的的情形。
( 7) 第八、 九行的for循环。
第八行首先令, 然后第九行根据P72的一般情形, 计算, 得到最终解。
为什么首先令, 实际上第八九行能够合并成如下等价的语句:
if (c>=w[1]) m[1][c] = max (m[2][c], m[2][c-w[1]] + v[1]);
上述语句和P73代码语义是一致的, 这也是赋值的含义。
【问题1】理解递归公式的含义。
【问题2】算法本身有没有做无用的计算, 为什么?
四． 实验内容
( 1) 完成代码, 并调试经过。
( 2) 回答实验指导书中的问题。
( 3) 理解动态规划的基本思想( 本质依然是递归与分治, 但满足最优子结构性质, 从而能够用动态规划方法进一步提升效率。最优子结构性质需要证明, 证明往往采用反证法) , 以及如何编程实现( 分为三个步骤: 首先, 证明最优子结构性质; 其次, 寻找大问题和小问题之间的递归关系; 最后, 将递归关系进行形式化表示, 并编程实现) 。