《算法设计与分析》

《算法设计与分析》实验指导书曹严元计算机与信息科学学院2007年5月目录实验一递归算法与非递归算法............................................................2实验二分治算法......................................................................................4实验三贪心算法....................................................................................6实验四动态规划....................................................................................8实验五回溯法......................................................................................10实验六分枝—限界算法......................................................................13实验七课程设计..................................................................................16实验一递归算法与非递归算法实验目的1.了解并掌握递归的概念，递归算法的基本思想；2.掌握基于归纳法的递归的思想方法；3.了解适用于用递归求解的问题类型，并能设计相应递归算法；4.掌握递归算法复杂性分析方法，比较同一个问题的递归算法与循环迭代算法的效率。预习与实验要求1.预习实验指导书及教材的有关内容，掌握递归的基本思想；2.严格按照实验内容进行实验，培养良好的算法设计和编程的习惯；3.认真听讲，服从安排，独立思考并完成实验。实验设备与器材硬件：PC机软件：C++或Java等编程环境。实验原理简单说来，当一个函数用它自己来定义时就称为递归。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。因此，在考虑使用递归算法编写程序时，应满足两点：1）该问题能够被递归形式描述；2）存在递归结束的边界条件。递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。一般说来，一个递归算法可以转换称为一个与之等效的非递归算法，但转换后的非递归算法代码将成倍地增加。实验内容以下两个问题选做一项：1.写出并实现计算斐波那契数列的递归和非递归算法。（1）认识斐波那契数列a，其中aa1，aaa，i1,2,3,；n12i2ii1（2）用递归的思想写出计算斐波那契数列的伪码算法；（3）用非递归的思想写出计算斐波那契数列的伪码算法；（4）用C++或JAVA等高级程序语言实现上述伪码算法；（5）比较递归和非递归实现的结果，验证算法的正确性。2.用递归和非递归方式各写一布尔函数，由该函数获取一个以0或1为元素的数组，并要求确定每个连续为1的序列的大小是否为偶数。（1）形式化地描述该问题，确定采用的数据结构；（2）用递归的思想写出求解该问题的伪码算法；（3）用非递归的思想写出求解该问题的伪码算法；（4）用C++或JAVA等高级程序语言实现上述伪码算法；（5）比较递归和非递归实现的结果，验证算法的正确性，并作时空复杂性分析。实验报告1.按照实验报告手册的要求认真填写相关栏目；2.写出用递归和非递归方法实现的伪码算法，写出算法所用到的主要数据结构；3.得出结果，并分别写出用递归和非递归算法时的时间复杂性和空间复杂性。4.详细填写完成实验的收获和得失，实验过程中遇到的问题、解决的办法、实验心得以及对该实验的建议和意见。思考题递归方法和非递归方法解决问题各有什么优劣之处呢？实验二分治算法实验目的1.掌握分治法的基本思想方法；2.了解适用于用分治法求解的问题类型，并能设计相应分治法算法；3.掌握分治法复杂性分析方法，比较同一个问题的递归算法与循环迭代算法的效率。预习与实验要求1.预习实验指导书及教材的有关内容，掌握分治法的基本思想；2.严格按照实验内容进行实验，培养良好的算法设计和编程的习惯；3.认真听讲，服从安排，独立思考并完成实验。实验设备与器材硬件：PC机软件：C++或Java等编程环境实验原理分治是一种被广泛应用的有效方法，它的基本思想是把最初的问题分解成若干子问题，然后在逐个解决各个子问题的基础上得到原始问题的解。所谓分治就是“分而治之”的意思。由于分解出的每个子问题总是要比最初的问题容易些，因而分治策略往往能够降低原始问题的难度，或者提高解决原始问题的效率。根据如何由分解出的子问题求出原始问题的解，分治策略又可分为两种情形：第一，原始问题的解只存在于分解出的某一个子问题中，则只需要在原始问题的一个划分中求解即可；第二，原始问题的解需要由各个子问题的解再经过综合处理得到。无论是哪一种情况，分治策略可以较快地缩小问题的求解范围，从而加快问题求解的速度。分治策略运用于计算机算法是，往往会出现分解出来的子问题与原始问题类型相同的现象，而与原问题相比，各个子问题的规模变小了，这刚好符合递归的特征。因此分治策略往往是和递归联系在一起的。实验内容以下三个问题选做一项：1.用分治策略写出并实现二分检索算法。（1）选择合适的数据结构来表示问题中的数列；（2）根据分治法的基本原理，写出求解二分检索的伪码算法；（3）编制C++或JAVA等高级语言程序实现伪码算法；（4）上机运行程序，验证算法的正确性，并分析算法的时空复杂性。2.实现多项式乘积的分治算法。（1）选择合适的数据结构来表示问题；（2）根据分治法的基本原理，写出求解多项式乘积的伪码算法；（3）编制C++或JAVA等高级语言程序实现伪码算法；（4）上机运行程序，验证算法的正确性，并分析算法的时空复杂性。3.用分治策略实现斯特拉森矩阵乘法。（1）选择合适的数据结构来表示问题；（2）根据分治法的基本原理，写出斯特拉森矩阵乘法的伪码算法；（3）编制C++或JAVA等高级语言程序实现伪码算法；（4）上机运行程序，验证算法的正确性，并分析算法的时空复杂性。实验报告1.描述分治法的基本原理；2.写出用分治法实现二分检索、多项式乘积或斯特拉森矩阵乘法的伪码算法，写出算法所用到的主要数据结构；3.得出结果，并写出算法的时间复杂性和空间复杂性。4.详细填写完成实验的收获和得失，实验过程中遇到的问题、解决的办法、实验心得以及对该实验的建议和意见。思考题1.怎样才能合理地把一个问题分解成满足分治策略的若干子问题2.求出子问题的解之后，怎么处理才能得出原始问题的解3.分治策略和递归是怎么结合在一起的呢？呢？呢？实验三贪心算法实验目的1.掌握贪心法的基本思想方法；2.了解适用于用贪心法求解的问题类型，并能设计相应贪心法算法；3.掌握贪心算法复杂性分析方法分析问题复杂性。预习与实验要求1.预习实验指导书及教材的有关内容，掌握贪心法的基本思想；2.严格按照实验内容进行实验，培养良好的算法设计和编程的习惯；3.认真听讲，服从安排，独立思考并完成实验。实验设备与器材硬件：PC机软件：C++或Java等编程环境实验原理有一类问题是要从所有的允许解中求出最优解，其策略之一是“贪心法”，即逐次实当前状态下最优的。贪心选择依赖于在此需要的选择，即不依赖于后续待求解子问题。显然，这种选择方法是局部最优的，但不是从问题求解的整体考虑进行选择，因此不能保证最后所得一定是最优解。贪心法是求解问题的一种有效方法，所得到的结果如果不是最优的，施“贪心选择”：在每个选择步骤上做出的选择都是之前所做出的选择，但不依赖于后续步骤所通常也是近似最优的。实验内容以下两个问题选做一项：1.用贪心算法实现单源最短路径问题。（1）选择合适的数据结构来表示问题中的赋权图以及其他变量和结果；（2）根据贪心算法的基本原理，写出求解单源最短路径问题的伪码算法；（3）编制C++或JAVA等高级语言程序实现伪码算法；（4）上机运行程序，验证算法的正确性。2.实现最小花费生成树问题。（1）按照Kruskal算法或Prim算法，选择合适的数据结构来表示问题中的赋权图、最小花费生成树以及其他变量；（2）根据Kruskal算法或Prim算法的基本原理，写出求解最小花费生成树问题的伪码算法；（3）编制C++或JAVA等高级语言程序实现伪码算法；（4）上机运行程序，验证算法的正确性；（5）考察Kruskal算法和Prim算法的时间复杂性和空间复杂性，比较它们的优劣。实验报告1.描述贪心算法的基本原理；2.写出用贪心算法实现单源最短路径问题或最小花费生成树问题的伪码算法，写出算法所用到的主要数据结构；3.得出结果，并写出算法的时间复杂性和空间复杂性。4.详细填写完成实验的收获和得失，实验过程中遇到的问题、解决的办法、实验心得以及对该实验的建议和意见。思考题1.选用不同的数据结构来表示单源最短路径问题会对算法的时空复杂性产生什么样的影响呢？2.从本质上来说，是什么导致了Kruskal算法和Prim算法具有不同的时空复杂性？这两种算法3.为什么贪心法不能保证得出的结果是最优的？试举一例说明。为什么用贪心法解决本实验中的两个问题时能得到最优结果？在什么地方体现了贪心算法的基本原理？实验四动态规划实验目的1.掌握动态规划的基本思想方法；2.了解适用于用动态规划方法求解的问题类型，并能设计相应动态规划算法；3.掌握分治法复杂性分析方法，比较同一个问题的递归算法与循环迭代算法的效率。预习与实验要求1.预习实验指导书及教材的有关内容，掌握动态规划的基本思想；2.严格按照实验内容进行实验，培养良好的算法设计和编程的习惯；3.认真听讲，服从安排，独立思考并完成实验。实验设备与器材硬件：PC机软件：C++或Java等编程环境实验原理将待求解问题分解为若干子问题，通过子问题的解得到原问题的解，这是问题求解的有效途径。但是如何实施分解呢分？治策略的基本思想是将规模为n的问题分解为k个规模较小的子问题，各子问题相互独立但与原问题求解策略相同。但并不是所有问题都可以这样处理。问题分解的另一个途径是将求解过程分解为若干阶段（级），一原问题的解。通过分解得到的各子阶段不要求相互独立，但希望它们具有相同类型，而且前一阶段的输出可以作为下一阶段的输入。这种策略特别适合求解具有某种最优性质的问题。次求解每个阶段即得到贪心法属于这类策略：对问题Pn，其求解过程中各贪心选择步骤构成决策序列DD,D,,DD的最优性仅仅依赖于D,D,,D。贪心法不保证最后求出解，12k12i1i的最优性。动态规划法也是一个分阶段判定决策过程，其问题求解策略的基础是决策过程的最优原,,,D。如果D是次作出决策序列DDD理：为达到某问题的最优目标T，需要一12k最优的，则对任意iik，决策子序列1D,D,,D也是最优的，即当前决策的最i1i2k优性取决于其后续决策序列是否最优。由此追溯至目标，再由最终目标决策向上回溯，导出决策序列DDD,,,D。因此动态规划方法可以保证问题求解是全局最优的。12k实验内容以下两个问题选做一项：1.实现资源分配的动态规划算法。（1）选择合适的数据结构来表示问题；（2）根据动态规划法的基本原理，写出求解资源分配问题的伪码算法；（3）编制C++或JAVA等高级语言程序实现伪码算法；（4）上机运行程序，验证算法的正确性。2.实现设备更新的动态规划算法。（1）选择合适的数据结构来表示问题；（2）根据动态规划法的基本原理，写出求解设备更新问题的伪码算法；（3）编制C++或JAVA等高级语言程序实现伪码算法；（4）上机运行程序，验证算法的正确性。实验报告1.描述动态规划的基本原理；2.写出用动态规划法实现资源分配问题或设备更新问题的伪码算法，写出算法所用到的主要数据结构；3.得出结果，并写出算法的时间复杂性和空间复杂性。4.详细填写完成实验的收获和得失，实验过程中遇到的问题、解决的办法、实验心得以及对该实验的建议和意见。思考题1.为什么动态规划法能保证最终结果的最优性，而贪心法不能？2.比较分治法、贪心法和动态规划法，在本质上，它们有何不同？实验五回溯法实验目的1.掌握回溯法的基本思想方法；2.了解适用于用回溯法求解的问题类型，并能设计相应回溯法算法；3.掌握回溯法算法复杂性分析方法，分析问题复杂性。预习与实验要求1.预习实验指导书及教材的有关内容，掌握回溯法的基本思想；2.严格按照实验内容进行实验，培养良好的算法设计和编程的习惯；3.认真听讲，服从安排，独立思考并完成实验。实验设备与器材硬件：PC机软件：C++或Java等编程环境实验原理回溯法是最常用的解题方法，有“通用的解题法”之称。当要解决的问题有若干可行解时，则可以在包含问题所有解的空间树中，按深度优先的策略，从根节点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的搜索，继续查找该结点的兄弟结点，若它的兄弟结点都不包含问题的解，则返回其父结点——这个步骤称为回溯。否则进入一子树，继续按深度优先的策略进行搜索。这种以深度优先的方式搜索问题的解的算法称为回溯法。它本质上是一种穷举法，但由于在搜索过程中不断略过某些显然不合适的子树，所以个可能包含解的搜索的空间大大少于一般的穷举，故它适用于解一些组合数较大的问题。下：假设能够用n元组x,x,,x,,x表示一个给回溯法也可以形式化地描述如12in定问题P的解，其中xS。如果x,x,,xn元组的子组in满足一定的约束条ii12i件，则称为部分解。如果它已经是满足约束条件的部分解，则添加xS形成新的子组i1i1x,x,,x,x，并检查它是否满足约束条件，若仍满足则继续添加xS，并以此12ii1i2i2类推。如果所有的xS都不满足约束条件，那么去掉x，回溯到x的位置，并去掉i1ii1i1个xS，组成新的子组x,x,,x，并判断其是否满足约束条件。iii12当前的x，另选一i如此反复下去，直到得到解或者证明无解为止。实验内容以下三个问题选做一项：1.实现（1）（2）n皇后问题的回溯算法，作时空复杂性分析。选择合适的数据结构来表示问题；确定出对n皇后问题的解空间树的深度优先搜索停止的条件（即开始回溯的条件）；（3）根据回溯法的基本原理，写出求解n皇后问题的伪码算法；（4）编制C++或JAVA等高级语言程序实现伪码算法；（5）上机运行程序，验证算法的正确性，作时空复杂性分析。2.实现分派问题的回溯算法，作时空复杂性分析。问题描述如下：给n个人分派n件工作，COST(i,j)为把工作j分配给第i个人的成本，要求在给每个人分派一件不同工作的情况下使总成本最小。（1）选择合适的数据结构来表示问题；（2）确定出对分派问题的解空间树的深度优先搜索停止的条件（即开始回溯的条件）；（3）（4）编制C++或JAVA等高级语言程序实现伪码算法；（5）根据回溯法的基本原理，写出求解分派问题的伪码算法；上机运行程序，验证算法的正确性，作时空复杂性分析。3.实现哈密尔顿回路的回溯算法。（1）选择合适的数据结构来表示问题；（2）确定出对分派问题的解空间树的深度优先搜索停止的条件（即开始回溯的条件）；（3）根据回溯法的基本原理，写出求解哈密尔顿回路的伪码算法；（4）编制C++或JAVA等高级语言程序实现伪码算法；（5）上机运行程序，验证算法的正确性，作时空复杂性分析。实验报告1.描述回溯法的基本原理和形式化描述；2.写出用回溯法实现n皇后问题、分派问题或求哈密尔顿回路问题的伪码算法，写出及搜索过程，确定搜索算法所用的到主要数据结构，简要画出各问题的解空间树以停止的条件（即开始回溯的条件）；3.得出结果，并写出算法的时间复杂性和空间复杂性。4.详细填写完成实验的收获和得失，实验过程中遇到的问题、解决的办法、实验心得以及对该实验的建议和意见。思考题1.根据回溯法的基本原理，想一想还可以用回溯法解决什么样的问题呢？2.回溯法的缺点是什么？实验六分枝—限界算法实验目的1.掌握分枝—限界的基本思想方法；2.了解适用于用分枝—限界方法求解的问题类型，并能设计相应动态规划算法；3.掌握分枝—限界算法复杂性分析方法，分析问题复杂性。预习与实验要求1.预习实验指导书及教材的有关内容，掌握分枝—限界的基本思想；2.严格按照实验内容进行实验，培养良好的算法设计和编程的习惯；3.认真听讲，服从安排，独立思考并完成实验。实验设备与器材硬件：PC机软件：C++或Java等编程环境实验原理分枝—限界算法类似于回溯法，也是一种在问题的解空间树上搜索问题解的算法。但两者求解方法有两点不同：第一，回溯法只通过约束条件剪去非可行解，而分枝—限界法不仅通过约束条件，而且通过目标函数的限界来减少无效搜索，也就是剪掉了某些不包含最优解的可行解；第二，在解空间树上，回溯法以深度优先搜索，而分枝—限界法则以广度优先或最小耗费优先的方式搜索。分枝—限界的搜索策略是，在扩展节点处，首先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展结点。为了有效地选择下一扩展结点，以加速搜索进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函数值从当前活结点表中选择一个最有利的结点做为扩展，使搜索朝着解空间树上最优解的分支推进，以便尽快找出一个最优解。分枝—限界法常以广度优先或以最小耗费优先的方式搜索问题的解空间树（问题的解空间树是表示问题皆空间的一颗有序树，常见的有子集树和排序树）。在搜索问题的解空间树时，分枝—限界法的每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，那些导致不可行解或非最优解的儿子结点将被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表取出下一结点成为当前扩展结点，并重复上述扩展过程，直到找到最优解或活结点表为空时停止。实验内容以下三个问题选做一项：1.实现0-1背包问题的分枝—限界算法。（1）选择合适的数据结构来表示问题，其中要求使用大小固定的元组表示动态状态空间树；（2）确定限界函数；（3）根据分枝—限界法的基本原理，写出求解0-1背包问题的伪码算法；（4）编制C++或JAVA等高级语言程序实现伪码算法；（5）上机运行程序，验证算法的正确性；（6）作时空复杂性分析，并与用回溯法解0-1背包问题作比较。2.实现货郎担问题的分枝—限界算法。（1）选择合适的数据结构来表示问题；（2）确定限界函数；（3）根据分枝—限界法的基本原理，写出求解货郎担问题的伪码算法；（4）编制C++或JAVA等高级语言程序实现伪码算法；（5）上机运行程序，验证算法的正确性；（6）作时空复杂性分析，并与用动态规划法解货郎担问题作比较。3.实现带有期限的作业排序问题的分枝—限界算法。（1）选择合适的数据结构来表示问题；（2）确定限界函数；（3）根据分枝—限界法的基本原理，写出求解带有期限的作业排序问题的伪码算法；（4）编制C++或JAVA等高级语言程序实现伪码算法；（5）上机运行程序，验证算法的正确性；（6）作时空复杂性分析，并与用贪心法解带有期限的作业排序问题作比较。实验报告1.描述分枝—限界法的基本原理；2.写出用分枝—限界法实现0-1背包问题、货郎担问题或带有期限的作业排序问题的伪码算法，写出算法所用到的主要数据结构，简要画出各问题的解空间树以及搜索过程，写出限界函数；3.得出结果，并写出算法的时间复杂性和空间复杂性，并与其他算法解题作比较。4.详细填写完成实验的收获和得失，实验过程中遇到的问题、解决的办法、实验心得以及对该实验的建议和意见。思考题1.分枝—限界法适合解决哪些问题？2.怎样确定限界函数？限界函数是固定不变的吗？实验七课程设计实验目的1.在已学的算法基本设计方法的基础上，理解算法设计的基本思想方法；2.掌握对写出的算法的复杂性分析的方法，理解算法效率的重要性；3.能运用所学的基本算法设计方法对问题设计相应算法，分析其效率，并建立对算法进行改进，提高效率的思想意识。预习与实验要求1.预习实验指导书及教材的有关内容，回顾所学过的算法的基本思想；2.严格按照实验内容进行实验，培养良好的算法设计和编程的习惯；3.认真听讲，服从安排，独立思考并完成实验。实验设备与器材硬件：PC机软件：C++或Java等编程环境实验原理参见前面各个实验的实验原理。实验内容以下四个问题选做一项：1.设计并实现课表自动编排系统。要求做算法的事前分析和事后测试。,,,（1）认识课表自动编排问题：设有一组课程Cccc，教室集合12kRr,r,,r，时间集合Tt,t,,t，那么时间集合与教室集合的m12n12NTR,,,,,,,,,ntrtrtrtr表示时间笛卡尔乘积—教室11121nm对，要为每一门课程寻找一个合适的时间—教室对，这组时间—教室对满足经验常识和某些限制条件，并且不能相互冲突；（2）选用所学过的一个合适的算法策略求解该问题；（3）选择合适的数据结构来表示问题；（4）根据所选算法的