算法设计与分析

1、算法设计与分析实验指导书 11 力77曹严元计算机与信息科学学院2007 年 5 月实验一递归算法与非递归算法 2.实验二 分治算法 4.实验三贪心算法 6.实验四动态规划 8.实验五回溯法.10实验六分枝限界算法13实验七课程设计.16i实验一递归算法与非递归算法1. 了解并掌握递归的概念，递归算法的基本思想；2. 掌握基于归纳法的递归的思想方法；3. 了解适用于用递归求解的问题类型，并能设计相应递归算法；4. 掌握递归算法复杂性分析方法，比较同一个问题的递归算法与循环迭代算法的效 率。预习与实验要求1. 预习实验指导书及教材的有关内容，掌握递归的基本思想；2. 严格按照实验内容进行实验，培

2、养良好的算法设计和编程的习惯;3. 认真听讲，服从安排，独立思考并完成实验。实验设备与器材硬件：PC机软件：C+或Java等编程环境。实验原理简单说来，当一个函数用它自己来定义时就称为递归。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时， 递归前进；当边界条件满足时， 递归返回。因此，在考虑使用递归算法编写程序时，应满足两点：1）该问题能够被递归形式描述；2）存在递归结束的边界条件。 递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。一般说来，一个递归算法可以转换称为一个与之等效的非 递归算法，但转换后的非递归算法代码将成倍地增加。

3、实验内容以下两个问题选做一项：1. 写出并实现计算斐波那契数列的递归和非递归算法。（1）认识斐波那契数列Q 其中 aj = a2=1，ai= aiai d，i =1,2,3，；（2）用递归的思想写出计算斐波那契数列的伪码算法；（3）用非递归的思想写出计算斐波那契数列的伪码算法；（4）用C+或JAVA等高级程序语言实现上述伪码算法；（5）比较递归和非递归实现的结果，验证算法的正确性。150或1为元素的数组,2. 用递归和非递归方式各写一布尔函数，由该函数获取一个以 并要求确定每个连续为 1的序列的大小是否为偶数。（1）形式化地描述该问题，确定采用的数据结构；（2）用递归的思想写出求解该问题的伪码

4、算法；（3）用非递归的思想写出求解该问题的伪码算法；（4）用C+或JAVA等高级程序语言实现上述伪码算法；（5）比较递归和非递归实现的结果，验证算法的正确性，并作时空复杂性分析。实验报告1. 按照实验报告手册的要求认真填写相关栏目；2. 写出用递归和非递归方法实现的伪码算法，写出算法所用到的主要数据结构；3. 得出结果，并分别写出用递归和非递归算法时的时间复杂性和空间复杂性。实验心得4. 详细填写完成实验的收获和得失，实验过程中遇到的问题、解决的办法、以及对该实验的建议和意见。思考题递归方法和非递归方法解决问题各有什么优劣之处呢?实验二分治算法1. 掌握分治法的基本思想方法；2. 了解适用于用

5、分治法求解的问题类型，并能设计相应分治法算法；3. 掌握分治法复杂性分析方法，比较同一个问题的递归算法与循环迭代算法的效率。预习与实验要求1. 预习实验指导书及教材的有关内容，掌握分治法的基本思想；2. 严格按照实验内容进行实验，培养良好的算法设计和编程的习惯;3. 认真听讲，服从安排，独立思考并完成实验。实验设备与器材硬件：PC机软件：C+或Java等编程环境实验原理分治是一种被广泛应用的有效方法，它的基本思想是把最初的问题分解成若干子问题，然后在逐个解决各个子问题的基础上得到原始问题的解。所谓分治就是“分而治之”的意思。因而分治策略往往能够降低原始问题分治策略又可分为两种情形：第一，原由于

6、分解出的每个子问题总是要比最初的问题容易些, 的难度，或者提高解决原始问题的效率。根据如何由分解出的子问题求出原始问题的解， 始问题的解只存在于分解出的某一个子问题中，则只需要在原始问题的一个划分中求解即 可；第二，原始问题的解需要由各个子问题的解再经过综合处理得到。无论是哪一种情况, 分治策略可以较快地缩小问题的求解范围，从而加快问题求解的速度。分治策略运用于计算机算法是， 往往会出现分解出来的子问题与原始问题类型相同的现象，而与原问题相比，各个子问题的规模变小了，这刚好符合递归的特征。因此分治策略往往是和递归联系在一起的。实验内容以下三个问题选做一项:1. 用分治策略写出并实现二分检索算法

7、。（1）选择合适的数据结构来表示问题中的数列；（2）根据分治法的基本原理，写出求解二分检索的伪码算法;（3）编制C+或JAVA等咼级语言程序实现伪码算法；（4）上机运行程序，验证算法的正确性，并分析算法的时空复杂性。2. 实现多项式乘积的分治算法。（1）选择合适的数据结构来表示问题；（2）根据分治法的基本原理，写出求解多项式乘积的伪码算法；（3）编制C+或JAVA等高级语言程序实现伪码算法；（4）上机运行程序，验证算法的正确性，并分析算法的时空复杂性。3. 用分治策略实现斯特拉森矩阵乘法。（1）选择合适的数据结构来表示问题；（2）根据分治法的基本原理，写出斯特拉森矩阵乘法的伪码算法；（3）编制

8、C+或JAVA等高级语言程序实现伪码算法；（4）上机运行程序，验证算法的正确性，并分析算法的时空复杂性。实验报告1. 描述分治法的基本原理；写出算实验心得2. 写出用分治法实现二分检索、多项式乘积或斯特拉森矩阵乘法的伪码算法，法所用到的主要数据结构；3. 得出结果，并写出算法的时间复杂性和空间复杂性。4. 详细填写完成实验的收获和得失，实验过程中遇到的问题、解决的办法、以及对该实验的建议和意见。思考题1. 怎样才能合理地把一个问题分解成满足分治策略的若干子问题呢?2. 求出子问题的解之后，怎么处理才能得出原始问题的解呢？3. 分治策略和递归是怎么结合在一起的呢？实验三贪心算法1. 掌握贪心法的

9、基本思想方法；2. 了解适用于用贪心法求解的问题类型，并能设计相应贪心法算法;3. 掌握贪心算法复杂性分析方法分析问题复杂性。预习与实验要求1. 预习实验指导书及教材的有关内容，掌握贪心法的基本思想；2. 严格按照实验内容进行实验，培养良好的算法设计和编程的习惯;3. 认真听讲，服从安排，独立思考并完成实验。实验设备与器材硬件：PC机软件：C+或Java等编程环境实验原理有一类问题是要从所有的允许解中求出最优解，其策略之一是“贪心法”，即逐次实施“贪心选择”：在每个选择步骤上做出的选择都是当前状态下最优的。贪心选择依赖于在此之前所做出的选择， 但不依赖于后续步骤所需要的选择，即不依赖于后续待求

10、解子问题。显然，这种选择方法是局部最优的，但不是从问题求解的整体考虑进行选择，因此不能保证最后所得一定是最优解。贪心法是求解问题的一种有效方法，所得到的结果如果不是最优的， 通常也是近似最优的。实验内容以下两个问题选做一项:1. 用贪心算法实现单源最短路径问题。（1）选择合适的数据结构来表示问题中的赋权图以及其他变量和结果；（2）根据贪心算法的基本原理，写出求解单源最短路径问题的伪码算法;（3）编制C+或JAVA等高级语言程序实现伪码算法；（4）上机运行程序，验证算法的正确性。2. 实现最小花费生成树问题。（1）按照Kruskal算法或Prim算法，选择合适的数据结构来表示问题中的赋权图、最小

11、花费生成树以及其他变量；(2) 根据Kruskal算法或Prim算法的基本原理，写出求解最小花费生成树问题的伪 码算法；(3) 编制C+或JAVA等高级语言程序实现伪码算法；(4) 上机运行程序，验证算法的正确性；(5) 考察Kruskal算法和Prim算法的时间复杂性和空间复杂性，比较它们的优劣。实验报告1. 描述贪心算法的基本原理；2. 写出用贪心算法实现单源最短路径问题或最小花费生成树问题的伪码算法，写出算法所用到的主要数据结构；3. 得出结果，并写出算法的时间复杂性和空间复杂性。4. 详细填写完成实验的收获和得失，实验过程中遇到的问题、解决的办法、实验心得以及对该实验的建议和意见。思考

12、题1. 选用不同的数据结构来表示单源最短路径问题会对算法的时空复杂性产生什么样 的影响呢？2. 从本质上来说，是什么导致了Kruskal算法和Prim算法具有不同的时空复杂性？这两种算法在什么地方体现了贪心算法的基本原理？3. 为什么贪心法不能保证得出的结果是最优的？试举一例说明。为什么用贪心法解决本实验中的两个问题时能得到最优结果？实验四动态规划1. 掌握动态规划的基本思想方法；2. 了解适用于用动态规划方法求解的问题类型，并能设计相应动态规划算法；3. 掌握分治法复杂性分析方法，比较同一个问题的递归算法与循环迭代算法的效率。预习与实验要求1. 预习实验指导书及教材的有关内容，掌握动态规划的

13、基本思想；2. 严格按照实验内容进行实验，培养良好的算法设计和编程的习惯;3. 认真听讲，服从安排，独立思考并完成实验。实验设备与器材硬件：PC机软件：C+或Java等编程环境实验原理将待求解问题分解为若干子问题，通过子问题的解得到原问题的解，这是问题求解的有效途径。但是如何实施分解呢？分治策略的基本思想是将规模为n的问题分解为k个规模较小的子问题，各子问题相互独立但与原问题求解策略相同。但并不是所有问题都可以这样处理。问题分解的另一个途径是将求解过程分解为若干阶段（级），一次求解每个阶段即得到原问题的解。通过分解得到的各子阶段不要求相互独立，但希望它们具有相同类型，而且前一阶段的输出可以作为

14、下一阶段的输入。这种策略特别适合求解具有某种最优性质的问题。 贪心法属 于这 类策略：对 问题P n，其求 解过程中各 贪心选 择步 骤构成 决策序列 D =D-D?,，Di的最优性仅仅依赖于 D-D?,Di4。贪心法不保证最后求出解 的最优性。动态规划法也是一个分阶段判定决策过程，其问题求解策略的基础是决策过程的最优原理：为达到某问题的最优目标 T,需要一次作出决策序列 D = D,D2/ ,D。如果D是 最优的，则对任意ili : k，决策子序列DjD,Dk也是最优的，即当前决策的最 优性取决于其后续决策序列是否最优。由此追溯至目标，再由最终目标决策向上回溯， 导出决策序列D = D1,D

15、2/ , D。因此动态规划方法可以保证问题求解是全局最优的。实验内容以下两个问题选做一项：1. 实现资源分配的动态规划算法。（1）选择合适的数据结构来表示问题；（2）根据动态规划法的基本原理，写出求解资源分配问题的伪码算法;（3）编制C+或JAVA等高级语言程序实现伪码算法；（4）上机运行程序，验证算法的正确性。2. 实现设备更新的动态规划算法。（1）选择合适的数据结构来表示问题；（2）根据动态规划法的基本原理，写出求解设备更新问题的伪码算法;（3）编制C+或JAVA等高级语言程序实现伪码算法；（4）上机运行程序，验证算法的正确性。实验报告1. 描述动态规划的基本原理；2. 写出用动态规划法实

16、现资源分配问题或设备更新问题的伪码算法，写出算法所用到的主要数据结构；3. 得出结果，并写出算法的时间复杂性和空间复杂性。4. 详细填写完成实验的收获和得失，实验过程中遇到的问题、 解决的办法、实验心得以及对该实验的建议和意见。思考题1. 为什么动态规划法能保证最终结果的最优性，而贪心法不能？2. 比较分治法、贪心法和动态规划法，在本质上，它们有何不同?实验五回溯法1. 掌握回溯法的基本思想方法；2. 了解适用于用回溯法求解的问题类型，并能设计相应回溯法算法;3. 掌握回溯法算法复杂性分析方法，分析问题复杂性。预习与实验要求1. 预习实验指导书及教材的有关内容，掌握回溯法的基本思想；2. 严格

17、按照实验内容进行实验，培养良好的算法设计和编程的习惯;3. 认真听讲，服从安排，独立思考并完成实验。实验设备与器材硬件：PC机软件：C+或Java等编程环境实验原理回溯法是最常用的解题方法，有“通用的解题法”之称。当要解决的问题有若干可行解时，则可以在包含问题所有解的空间树中，按深度优先的策略，从根节点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，贝y跳过对以该结点为根的子树的搜索，继续查找该结点的兄弟结点，若它的兄弟结点都不包含问题的解，则返回其父结点一一这个步骤称为回溯。否则进入一个可能包含解的子树，继续按深度优先的策略进行搜索。

18、这种以深度优先的方式搜索问题的解的算法称为回溯法。它本质上是一种穷举法， 但由于在搜索过程中不断略过某些显然不合适的子树，所以搜索的空间大大少于一般的穷举，故它适用于解一些组合数较大的问题。回溯法也可以形式化地描述如下：假设能够用n元组X,X2,，Xi,，Xn表示一个给定问题P的解，其中Xi S。如果n元组的子组 X!,X2/ ,Xii n满足一定的约束条件，则称为部分解。如果它已经是满足约束条件的部分解，则添加Xi S ,形成新的子组（Xi,X2，Xj,Xr ），并检查它是否满足约束条件，若仍满足则继续添加Xi七w St，并以此类推。如果所有的 X + ES +都不满足约束条件，那么去掉Xi

19、+，回溯到Xi的位置，并去掉当前的Xi，另选一个xS，组成新的子组（Xi,X2，x：），并判断其是否满足约束条件。 如此反复下去，直到得到解或者证明无解为止。实验内容以下三个问题选做一项：1. 实现n皇后问题的回溯算法，作时空复杂性分析。（1）选择合适的数据结构来表示问题；（即开始回溯的条（2）确定出对n皇后问题的解空间树的深度优先搜索停止的条件 件）；（3）根据回溯法的基本原理，写出求解n皇后问题的伪码算法;（4）编制C+或JAVA等高级语言程序实现伪码算法；（5）上机运行程序，验证算法的正确性，作时空复杂性分析。2. 实现分派问题的回溯算法，作时空复杂性分析。问题描述如下：给n个人分派n件

20、 工作，COST（i, j）为把工作j分配给第i个人的成本，要求在给每个人分派一件不同工作的情 况下使总成本最小。（1）选择合适的数据结构来表示问题；（2）确定出对分派问题的解空间树的深度优先搜索停止的条件（即开始回溯的条 件）；（3）根据回溯法的基本原理，写出求解分派问题的伪码算法；（4）编制C+或JAVA等高级语言程序实现伪码算法；（5）上机运行程序，验证算法的正确性，作时空复杂性分析。3. 实现哈密尔顿回路的回溯算法。（1）选择合适的数据结构来表示问题；（2）确定出对分派问题的解空间树的深度优先搜索停止的条件（即开始回溯的条 件）；（3）根据回溯法的基本原理，写出求解哈密尔顿回路的伪码算

21、法；（4）编制C+或JAVA等高级语言程序实现伪码算法；（5）上机运行程序，验证算法的正确性，作时空复杂性分析。实验报告1. 描述回溯法的基本原理和形式化描述；2. 写出用回溯法实现 n皇后问题、分派问题或求哈密尔顿回路问题的伪码算法，写出算法所用到的主要数据结构，简要画出各问题的解空间树以及搜索过程，确定搜索停止的条件（即开始回溯的条件）；3. 得出结果，并写出算法的时间复杂性和空间复杂性。实验心得4. 详细填写完成实验的收获和得失，实验过程中遇到的问题、解决的办法、以及对该实验的建议和意见。思考题1. 根据回溯法的基本原理，想一想还可以用回溯法解决什么样的问题呢?2. 回溯法的缺点是什么？

22、23实验六分枝一限界算法实验目的1. 掌握分枝一限界的基本思想方法；2. 了解适用于用分枝一限界方法求解的问题类型，并能设计相应动态规划算法;3. 掌握分枝一限界算法复杂性分析方法，分析问题复杂性。预习与实验要求1. 预习实验指导书及教材的有关内容，掌握分枝一限界的基本思想;2. 严格按照实验内容进行实验，培养良好的算法设计和编程的习惯;3. 认真听讲，服从安排，独立思考并完成实验。实验设备与器材硬件：PC机软件：C+或Java等编程环境实验原理分枝一限界算法类似于回溯法，也是一种在问题的解空间树上搜索问题解的算法。但两者求解方法有两点不同：第一，回溯法只通过约束条件剪去非可行解，而分枝一限界

23、法不仅通过约束条件，而且通过目标函数的限界来减少无效搜索，也就是剪掉了某些不包含最优解的可行解；第二，在解空间树上，回溯法以深度优先搜索，而分枝一限界法则以广度优先或 最小耗费优先的方式搜索。分枝一限界的搜索策略是，在扩展节点处，首先生成其所有的儿 子结点（分支），然后再从当前的活结点表中选择下一个扩展结点。为了有效地选择下一扩 展结点，以加速搜索进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函数值从当前活结点表中选择一个最有利的结点做为扩展，使搜索朝着解空间树上最优解的分支推进，以便尽快找出一个最优解。分枝一限界法常以广度优先或以最小耗费优先的方式搜索问题的解空间树（问题

24、的解空间树是表示问题皆空间的一颗有序树，常见的有子集树和排序树）。在搜索问题的解空间树时，分枝一限界法的每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点， 就一次性产生其所有儿子结点。 在这些儿子结点中，那些导致不可行解或非最优解的儿子结 点将被舍弃，其余儿子结点被加入活结点表中。 此后，从活结点表取出下一结点成为当前扩 展结点，并重复上述扩展过程，直到找到最优解或活结点表为空时停止。实验内容以下三个问题选做一项:1. 实现0-1背包问题的分枝一限界算法。（1）选择合适的数据结构来表示问题，其中要求使用大小固定的元组表示动态状态空间树；（2）确定限界函数；（3）根据分枝一限界法的基

25、本原理，写出求解0-1背包问题的伪码算法；（4）编制C+或JAVA等高级语言程序实现伪码算法；（5）上机运行程序，验证算法的正确性；（6）作时空复杂性分析，并与用回溯法解0-1背包问题作比较。2. 实现货郎担问题的分枝一限界算法。（1）选择合适的数据结构来表示问题；（2）确定限界函数；（3）根据分枝一限界法的基本原理，写出求解货郎担问题的伪码算法;（4）编制C+或JAVA等高级语言程序实现伪码算法；（5）上机运行程序，验证算法的正确性；（6）作时空复杂性分析，并与用动态规划法解货郎担问题作比较。3. 实现带有期限的作业排序问题的分枝一限界算法。（1）选择合适的数据结构来表示问题；（2）确定限界

26、函数；（3）根据分枝一限界法的基本原理，写出求解带有期限的作业排序问题的伪码算法；（4）编制C+或JAVA等高级语言程序实现伪码算法；（5）上机运行程序，验证算法的正确性；（6）作时空复杂性分析，并与用贪心法解带有期限的作业排序问题作比较。实验报告1. 描述分枝一限界法的基本原理；2. 写出用分枝一限界法实现 0-1背包问题、货郎担问题或带有期限的作业排序问题的伪码算法，写出算法所用到的主要数据结构，简要画出各问题的解空间树以及搜索过程，写出限界函数；3. 得出结果，并写出算法的时间复杂性和空间复杂性，并与其他算法解题作比较。实验心得4. 详细填写完成实验的收获和得失，实验过程中遇到的问题、解

27、决的办法、以及对该实验的建议和意见。思考题1. 分枝一限界法适合解决哪些问题？2. 怎样确定限界函数？限界函数是固定不变的吗?实验七课程设计实验目的1. 在已学的算法基本设计方法的基础上，理解算法设计的基本思想方法；2. 掌握对写出的算法的复杂性分析的方法，理解算法效率的重要性；3. 能运用所学的基本算法设计方法对问题设计相应算法，分析其效率，并建立对算法 进行改进，提高效率的思想意识。预习与实验要求1. 预习实验指导书及教材的有关内容，回顾所学过的算法的基本思想;2. 严格按照实验内容进行实验，培养良好的算法设计和编程的习惯；3. 认真听讲，服从安排，独立思考并完成实验。实验设备与器材硬件：

28、PC机软件：C+或Java等编程环境实验原理参见前面各个实验的实验原理。实验内容以下四个问题选做一项：1. 设计并实现课表自动编排系统。要求做算法的事前分析和事后测试。（1）认识课表自动编排问题：设有一组课程C = ic1, c2 / ,cf，教室集合Rri2,，时间集合T = ,t2,垢匚那么时间集合与教室集合的 笛卡尔乘积N=TR/t,忧2,，t1,n,，tmJn表示时间一教室对，要为每一门课程寻找一个合适的时间一教室对，这组时间一教室对满足经验常识和某些限制条件，并且不能相互冲突；（2）选用所学过的一个合适的算法策略求解该问题；（3）选择合适的数据结构来表示问题；（4）根据所选算法的基本原理，写出求解该问题的伪码算法；（5）编制C+或JAVA等高级语言程序实现伪码算法；（6）上机运行程序，验证算法的正确性，作时空复杂性分析。2. 设计并实现运动员