算法实验指导书

《算法实验指导书》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、算法设计与分析实验指导书信电工程学院2015.7算法设计与分析实验目的算法设计与分析是计算机相关专业的核心课程之一。本实验加深学生对算法设计的基本策略、主要方法及实验过程的理解；培养学生针对具体的问题，选择合适的数据结构和设计结构清晰、正确有效的算法的能力。二.实验内容E05210801算法概述E05210802分治法E05210803动态规划E05210804贪心法E05210805回溯法E05210806分支限界法E05210807NP完全问题E05210808近似算法三•实验方法本课程所有实验均需上机进行，每个实验都有明确的实验目的，并根据实验要求提供实验题。每

2、位同学通过独立思考、与同学讨论、老师辅导答疑相结合的方法完成相应的实验题，在对题目进行分析、选择有效的方法、编程及测试的过程中，将达到加深学生印象、锻炼学生运用书本知识实际解决问题的能力。四.实验要求学生按照实验要求，上机前写好上机实验预习报告。上机实验时按实验要求完成每一个实验的内容。认真书写实验报告，内容包括：实验的目的、实验原理、实验内容、实验步骤、实验结果等。实验一算法概述1.实验目的(1)复习数据结构课程的相关知识，实现课程间的平滑过渡；(2)掌握并应用算法的数学分析和后验分析方法；(3)理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同

3、，复杂程度不同，解题效率也不同。2.实验内容求两个自然数m和n的最大公约数。3.实验要求(1)至少设计出三个版本的求最大公约数算法；(2)对所设计的算法釆用大0符号进行时间复杂性分析；(3)上机实现算法，并用计数法和计时法分别测算算法的运行时间；(4)通过分析对比，得出自己的结论。实验二分治法1.实验目的(1)进-步掌握递归算法的设计思想以及递归程序的调试技术；(2)理解这样一个观点：分治与递归经常同吋应用在算法设计之中。2.实验内容设Pl,P2,…,Pn是平面上n个点构成的集合S,设计算法找出集合S中距离最近的点对。3.实验要求(1)分别用蛮力法和分治法求解最近对问

4、题；(2)分析算法的时间性能，设计实验程序验证分析结论。实验三动态规划1.实验目的(1)深刻掌握动态规划法的设计思想并能熟练运用；(2)理解这样一个观点：同样的问题可以用不同的方法解决，一个好的算法是反复努力和重新修正的结果。2.实验内容给定由n个整数组成的序列(aba2,…,如),求该序列的子段和的最大值,当所有整数均为负整数时，其最大子段和为0。3.实验要求(1)分别用蛮力法、分治法和动态规划法设计最大子段和问题的算法；(2)比较不同算法的时间性能；(3)给出测试数据，写出程序文档。实验四贪心算法1.实验目的(1)掌握最优子结构性质的证明方法；(2)掌握贪心法的设

5、计思想并能熟练运用。2.实验内容一辆汽车加满油后可以行驶一定距离。旅途中有若干个加油站。若要使沿途的加油次数最少，应在那些加油站停靠加油。3.实验要求(1)设计贪心算法求解汽车加油问题;(2)证明算法的正确性；(3)设计测试数据，写出程序文档。实验五回溯法1.实验目的(1)掌握回溯法的设计思想；(2)掌握解空间树的构造方法，以及奋求解过程中如何存储求解路径；(3)考察回溯法求解问题的有效程度。2.实验内容给定n种物品和一个容量为C的背包，物品i(lWiWn)的重量是w，其价值为J0/1背包问题是如何选择装入背包的物品(物品不可分割)，使得装入背包中物品的总价值最大？3

6、.实验要求(1)设汁可能解的表示方式，构成解空间树;(2)设计冋溯算法完成问题求解；(3)设计测试数据，统计搜索空间的结点数;实验六分支限界法1.实验目的(1)进-步掌握分支限界法的设计思想，掌握限界函数的设计技巧；(2)考察分支限界法求解问题的有效程度，并与回溯法进行对比；(3)理解这样一个观点：好的限界函数不仅计算简单，还要保证最优解在搜索空间中，更重要的是能在搜索的早期对超11!目标函数界的结点进行丢弃,减少搜索空间，从而尽快找到问题的最优解。2.实验内容给定n个城市集合C={C],C2,…,Cn},从一个城市到另一个城市的距离dij为正整数，求一条最短且每个城

7、市恰好经过一次的巡冋路线。3.实验要求(1)对旅行售货员问题建立合理的模型，通过实验确定一个合理的限界函数；(2)设计算法实现旅行售货员问题；(3)设计测试数据，统计搜索空间的结点数。实验七NP完全问题1.实验目的(1)掌握NP完全问题的特点；(2)理解这样一个观点：NP完全问题的算法具有指数吋间，而指数吋间算法的计算吋间随着问题规模的增长而快速增长。2.实验内容SAT问题也称为合取范式的可满足问题，一个合取范式形如：AjAA2A*--AAn,子句A：(lWiWn)形如：aiVaiV*--Vak,其中，务称为文字，为某一布尔变量或该布尔变量的非。SA