算法分析
- 格式：doc
- 大小：64.50 KB
- 文档页数：8
《 算法设计与分析 》
实
验
报
告
授课教师：廖慧芬
授课班级：信A0811/12/13
实验一 分治法（排序）
实验目的：
1. 理解用分治法求解的问题：当要求解一个输入规模为n，且n的取值相当大的
问题时，的，如果问题可以分成k个不同子集合，得到k个不同的可独立求解的
子问题，其中1
2. 掌握分治法的一般控制流程
DanC(p,q)
global n，A[1:n]; integer m,p,q; // 1pqn
if Small(p,q) then return G(p,q);
else m=Divide(p,q); // pm return Combine(DanC(p,m),DanC(m+1,q));
endif
end DanC
3. 实现典型的分治算法的编程与上机实验，验证算法的时间复杂性函数。
实验所需软件：
Visual c++2008、Myeclipse 8.6
实验步骤：
(1)编程实现归并排序算法和快速排序算法，程序中加入比较次数的计数功
能，输出排序结果和比较次数。
(2)输入10组相同的数据，验证排序结果和完成排序的比较次数。
(3)与复杂性函数所计算的比较次数比较。
(4)用表格列出比较结果。
(5)给出文字分析。
编程实现：
实验二 分治法（Linear-Time Selection）
实验目的：
1. 了解一种复杂的排序算法
2. 了解英文原文算法描述
3. 掌握分治思想应用于线性时间选择算法中
4. 实现线性时间选择算法的编程与上机实验，验证算法的时
间复杂性函数。
实验所需软件：
Visual c++2008、Myeclipse 8.6
实验步骤：（50分）
1. 读懂英文算法思想
2. 输入数据序列
3. 对数据序列5个一分组
4. 选择基准点
5. 划分子序列
6. 输出结果
7. 给出文字分析
编程实现：
实验三 动态规划（最短路径）
实验目的：
1）理解最优子结构的问题。
有一类问题的活动过程可以分成若干个阶段，而且在任一阶段后的行为依
赖于该阶段的状态，与该阶段之前的过程如何达到这种状态的方式无关。这类问
题的解决是多阶段的决策过程。在50年代，贝尔曼（Richard Bellman）等人提
出了解决这类问题的“最优化原理”，从而创建了最优化问题的一种新的算法设计
方法－动态规划。
对于一个多阶段过程问题，是否可以分段实现最优决策，依赖于该问题是
否有最优子结构性质，能否采用动态规划的方法，还要看该问题的子问题是否具
有重叠性质。
最优子结构性质：原问题的最优解包含了其子问题的最优解。
子问题重叠性质：每次产生的子问题并不总是新问题，有些子问题被反复
计算多次。问题的最优子结构性质和子问题重叠性质是采用动态规划算法的两个
基本要素。
2）理解分段决策Bellman方程。
实验所需软件：
Visual c++2008、Myeclipse 8.6
实验步骤：
1.找出最优解的性质，并刻画其结构特征；
2.递归地定义最优值（写出动态规划方程）；
3.以自底向上的方式计算出最优值；
4.根据计算最优值时得到的信息，构造一个最优解。
步骤1-3是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤4
可以省略，步骤3中记录的信息也较少；若需要求出问题的一个最优解，
则必须执行步骤4，步骤3中记录的信息必须足够多以便构造最优解。
最短路径
编程实现多段图的最短路经问题的动态规划算法。
1） 图的数据结构采用邻接表。
2） 要求用文件装入5个多段图数据，编写从文件到邻接表的函数。
3） 验证算法的时间复杂性。
编程实现：
实验四 动态规划（longest common subsequence）
实验目的：
1.理解最长公共子序列的英文算法描述。
2.理解算法技巧中的动态规划思想。
3.编程实现最长公共子序列问题。
实验所需软件：
Visual c++2008、Myeclipse 8.6
实验步骤：
1.输入两个字符序列
2.规划矩形方阵
3.描述程序
4.输出结果
5.文字分析算法时间复杂度
编程实现：
实验五 贪心算法（背包问题）
实验目的：
1.优化问题
有n个输入，而它的解就由这n个输入满足某些事先给定的约束条件的某
个子集组成，而把满足约束条件的子集称为该问题的可行解。可行解一般来
说是不唯一的。那些使目标函数取极值(极大或极小)的可行解，称为最优解。
2.贪心法求优化问题
算法思想：在贪心算法中采用逐步构造最优解的方法。在每个阶段，都作出
一个看上去最优的决策（在一定的标准下）。决策一旦作出，就不可再更改。作
出贪心决策的依据称为贪心准则（greedy criterion）。
实验所需软件：
Visual c++2008、Myeclipse 8.6
实验步骤：
1. 根据题意，选取一种量度标准。
2. 按这种量度标准对这n个输入排序
3. 依次选择输入量加入部分解中。如果当前这个输入量的加入，不满足约
束条件，则不把此输入加到这部分解中。
1）实现典型的贪心算法的编程与上机实验，验证算法的时间复杂性函数。
1、 实验内容
1） 编程实现背包问题贪心算法和最小生成树prim算法。通过具体算法理解
如何通过局部最优实现全局最优，并验证算法的时间复杂性。
2） 输入5个的图的邻接矩阵，程序加入统计prim算法访问图的节点数和边数
的语句。
3） 将统计数与复杂性函数所计算的比较次数比较，用表格列出比较结果，
给出文字分析。
2、 背包问题贪心算法和prim算法
编程实现：
实验六 深度优先搜索
实验目的：
1） 理解深度优先搜索策略
是尽可能“深”地搜索图。在深度优先搜索中，对于最新发
现的顶点v，如果边（v，w）是还未探测的边，则沿（v，w）继
续搜索下去。当所有的边（v，w）都己被探寻过，搜索将回溯
到发现结点v的顶点。这一过程一直进行到回到源点为止。如果
还存在未被发现的顶点，则选择其中一个作为源结点并重复以上
过程，整个进程反复进行直到所有结点都被发现为止。
2） 理解深度优先搜索过程中顶点的三种状态
还未到达的顶点，当前路径上经过的顶点，深度优先在搜
索过程中也为结点着色以表示结点的状态。每个顶点开始均为白
色，搜索中被发现时置为灰色，当其邻接表被完全检索之后又被
置成黑色。
实验所需软件：
Visual c++2008、Myeclipse 8.6
实验步骤：
1） 编程实现深度优先搜索算法。
2） 修改算法使之可以找出图的所有树。
3） 修改算法使之可以判断图是否为一棵树。
4） 修改算法使之可以判断图是否存在一个环。
编程实现：
实验七 回溯法
实验目的：
1.理解可用回溯法求解的问题
问题P通常要能表达为对已知的、由n元组(x1，…，xn)组成
的状态空间E={(x1，…，xn)| xiSi,i=1,2,…n}，给定关于n元组中
的分量的一个约束集D，求满足D的全部约束条件的所有n元组。
Si 是 xi 的定义域且Si 是有穷集，称E中满足D 的全部约束条
件的所有n元组为问题P的一个解。
2.理解回溯法的基本思想
回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在
包含问题的所有解的解空间树中，按照深度优先的策略，从根结
点出发搜索解空间树。
算法搜索至解空间树的任一结点时，总是先判断该结点是
否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为
根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子
树，继续按深度优先的策略进行搜索。
实验所需软件：
Visual c++2008、Myeclipse 8.6
实验步骤：
1） 编程实现n皇后算法。
2） 用图形输出中间过程。
3） 在程序中添加统计扩展节点数，估计算法的复杂性。
编程实现：
