算法设计与分析
实验指导书
信电工程学院 2015.7
1
算法设计与分析
一.实验目的
算法设计与分析是计算机相关专业的核心课程之一。本实验加深学生对算法设计的基本策略、主要方法及实验过程的理解；培养学生针对具体的问题，选择合适的数据结构和设计结构清晰、正确有效的算法的能力。
二.实验内容
E05210801 算法概述 E05210802 分治法 E05210803 动态规划 E05210804 贪心法 E05210805 回溯法 E05210806 分支限界法 E05210807 NP完全问题 E05210808 近似算法
三.实验方法
本课程所有实验均需上机进行，每个实验都有明确的实验目的，并根据实验要求提供实验题。每位同学通过独立思考、与同学讨论、老师辅导答疑相结合的方法完成相应的实验题，在对题目进行分析、选择有效的方法、编程及测试的过程中，将达到加深学生印象、锻炼学生运用书本知识实际解决问题的能力。
四. 实验要求
学生按照实验要求，上机前写好上机实验预习报告。 上机实验时按实验要求完成每一个实验的内容。
认真书写实验报告，内容包括：实验的目的、实验原理、实验内容、实验步骤、实验结果等。
2
实验一 算法概述
1. 实验目的
(1) 复习数据结构课程的相关知识，实现课程间的平滑过渡； (2) 掌握并应用算法的数学分析和后验分析方法；
(3) 理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。
2. 实验内容
求两个自然数m和n的最大公约数。
3. 实验要求
(1) 至少设计出三个版本的求最大公约数算法；
(2) 对所设计的算法采用大O符号进行时间复杂性分析；
(3) 上机实现算法，并用计数法和计时法分别测算算法的运行时间； (4) 通过分析对比，得出自己的结论。
3
实验二 分治法
1. 实验目的
(1) 进一步掌握递归算法的设计思想以及递归程序的调试技术； (2) 理解这样一个观点：分治与递归经常同时应用在算法设计之中。
2. 实验内容
设p1, p2, …, pn是平面上n个点构成的集合S，设计算法找出集合S中距离最近的点对。
3. 实验要求
(1) 分别用蛮力法和分治法求解最近对问题；
(2) 分析算法的时间性能，设计实验程序验证分析结论。
4
实验三 动态规划
1. 实验目的
(1) 深刻掌握动态规划法的设计思想并能熟练运用；
(2) 理解这样一个观点：同样的问题可以用不同的方法解决，一个好的算法是反复努力和重新修正的结果。
2. 实验内容
给定由n个整数组成的序列(a1, a2, …, an)，求该序列的子段和的最大值，当所有整数均为负整数时，其最大子段和为0。
3. 实验要求
(1) 分别用蛮力法、分治法和动态规划法设计最大子段和问题的算法； (2) 比较不同算法的时间性能； (3) 给出测试数据，写出程序文档。
5
实验四 贪心算法
1. 实验目的
(1) 掌握最优子结构性质的证明方法； (2) 掌握贪心法的设计思想并能熟练运用。
2. 实验内容
一辆汽车加满油后可以行驶一定距离。旅途中有若干个加油站。若要使沿途的加油次数最少，应在那些加油站停靠加油。
3. 实验要求
(1) 设计贪心算法求解汽车加油问题； (2) 证明算法的正确性；
(3) 设计测试数据，写出程序文档。
6
实验五 回溯法
1. 实验目的
(1) 掌握回溯法的设计思想；
(2) 掌握解空间树的构造方法，以及在求解过程中如何存储求解路径； (3) 考察回溯法求解问题的有效程度。
2. 实验内容
给定n种物品和一个容量为C的背包，物品i（1≤i≤n）的重量是wi，其价值为vi，0/1背包问题是如何选择装入背包的物品（物品不可分割），使得装入背包中物品的总价值最大?
3. 实验要求
(1) 设计可能解的表示方式，构成解空间树； (2) 设计回溯算法完成问题求解；
(3) 设计测试数据，统计搜索空间的结点数；
7
实验六 分支限界法
1. 实验目的
(1) 进一步掌握分支限界法的设计思想，掌握限界函数的设计技巧； (2) 考察分支限界法求解问题的有效程度，并与回溯法进行对比； (3) 理解这样一个观点：好的限界函数不仅计算简单，还要保证最优解在搜索空间中，更重要的是能在搜索的早期对超出目标函数界的结点进行丢弃，减少搜索空间，从而尽快找到问题的最优解。
2. 实验内容
给定n个城市集合C={c1,c2,…,cn}, 从一个城市到另一个城市的距离 dij 为正整数，求一条最短且每个城市恰好经过一次的巡回路线。
3. 实验要求
(1) 对旅行售货员问题建立合理的模型，通过实验确定一个合理的限界函数；
(2) 设计算法实现旅行售货员问题；
(3) 设计测试数据，统计搜索空间的结点数。
8
实验七 NP完全问题
1. 实验目的
(1) 掌握NP完全问题的特点；
(2) 理解这样一个观点：NP完全问题的算法具有指数时间，而指数时间算法的计算时间随着问题规模的增长而快速增长。
2. 实验内容
SAT问题也称为合取范式的可满足问题，一个合取范式形如：A1∧A2
∧…∧An，子句Ai（1≤i≤n）形如：a1∨a2∨…∨ak，其中，ai称为文字，为某一布尔变量或该布尔变量的非。SAT问题是指：是否存在一组对所有布尔变量的赋值（TRUE或FALSE），使得整个合取范式取值为真。
3. 实验要求
(1) 设计算法求解SAT问题；
(2) 设定问题规模为3、5、10、20、50，设计实验程序考察算法的时间性能。
9
实验八 近似算法
1. 实验目的
(1) 了解处理难解问题的策略；
(2) 掌握近似算法的设计思想并能熟练运用； (3) 掌握近似算法的评价标准。
2. 实验内容
0-1背包问题的近似算法。
3. 实验要求
(1) 设计简单贪心算法G-KK；多项式时间近似方案PTAS；多项式时间近似方案FPTAS。
(2) 测试每种算法的性能。
10
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库算法实验指导书详解在线全文阅读。
相关推荐：