算法分析与设计实验指导书.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. 快速排序的基本思绪。假设需要排序的数存储在数组“ap, ap+1, , ar”中。为了描述方便，将上述数组简记为：ap:r。（1） 一方面，以ap为基准元素，将ap:r划分为三段，分别是：ap: q-1, aq, aq+1: r。其中，ap: q-1中的任何一个元素都小于等于aq；aq小于等于aq+1: r中的任何一个元素。注意：算法工作时，以ap为基准进行ap:r划分；aq是在划分完毕时拟定的。（2） 对划分得到的ap: q-1和aq+1: r类似地，进行划分。（3） 注意到ap: q-1, aq, aq+1: r的关系，不要任何计算，数组ap: 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）个矩阵相乘。为了描述方便，记为Ai:j。即：Ai:j= Ai*Ai+1*Aj。显然，Ai:j一定是有一个最优的计算顺序的，虽然不知道这个最优顺序是多少，但是不妨假设是从Ak处断开。换句话说，对于Ai:j，其最优计算顺序为： (Ai*Ak) * (Ak+1*Aj)。显然，上述计算次数由三部分构成。构成1：(Ai*Ak)的计算次数，用X表达；构成2：(Ak+1*Aj)的计算次数，用Y表达；构成3：(Ai*Ak)和(Ak+1*Aj)的乘积，也就是（Ai的行数*Ak的列数*Aj的列数）。用公式表达如下：Ai:j的计算次数 = X + Y + Ai的行数*Ak的列数*Aj的列数注意到：由于已经固定从Ak处断开，因此构成3是一个定值。因此，要Ai:j的计算次数最少，就需要X和Y分别是最小。这说明：原问题Ai:j的最优解包含了子问题Ai:k和子问题Ak+1:j的最优解。因此，可以使用动态规划算法。2. 动态规划算法的递归公式假如用mij表达Ai:j的最优值，那么有：（1） 假如i=j，Ai:j是单独一个矩阵，不需要计算，因此，mij=0；（2） 假如i=w1) m1c = max (m2c, m2c-w1 + v1);上述语句和P73代码语义是一致的，这也是赋值的含义。【问题1】理解递归公式的含义。【问题2】算法自身有没有做无用的计算，为什么？四 实验内容（1） 完毕代码，并调试通过。（2） 回答实验指导书中的问题。（3） 理解动态规划的基本思想（本质仍然是递归与分治，但满足最优子结构性质，从而可以用动态规划方法进一步提高效率。最优子结构性质需要证明，证明往往采用反证法），以及如何编程实现（分为三个环节：一方面，证明最优子结构性质；另一方面，寻找大问题和小问题之间的递归关系；最后，将递归关系进行形式化表达，并编程实现）。