算法分析与设计实验指导书.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） 理解动态规划的基本思想（本质仍然是递归与分治，但满足最优子结构性质，从而可以用动态规划方法进一步提高效率。最优子结构性质需要证明，证明往往采用反证法），以及如何编程实现（分为三个环节：一方面，证明最优子结构性质；另一方面，寻找大问题和小问题之间的递归关系；最后，将递归关系进行形式化表达，并编程实现）。