算法设计与分析报告

算法设计与分析期末作业

算法设计与分析期末作业

学校 专业班级 学号 学院 任课教师 学生姓名 第一题：简述递归算法、分治算法、动态规划算法、回溯算法的基本思想和步骤。

第二题：自拟一组数据，从插入排序、选择排序、合并排序、快速排序四种算法中任选两种算法，以图示描述方式描述算法求解过程。

第三题：从以下高级图算法(即宽度优先搜索算法、深度优先搜索算法、Kruskal算法、Prim算法、BellmanFord算法 、Dijkstra算法)中任选一种，结合现实情况构造一具体案例，并使用所选择的图算法以图示描述方式予以求解。

要求：在此作业模板下答题，电子文档及其打印文档均需上交，其中，电子文档发送至duyuanwei@foxmail.com，打印文稿于16周上课时上交。

1

算法设计与分析期末作业

第一题

答：一、递归算法：

（1）基本思想：把一个问题划分为一个或多个规模更小的子问题，然后用同样的方法解规模更小的子问题。(递归=递推+回归) （2）步骤：

1：找到问题的初始条件(递归出口)，即当问题规模小到某个值时，该问题变得很简单，能够直接求解。(出口)

2：设计一个策略，用于将一个问题划分为一个或多个一步步接近递归出口的、相似的、规模更小的子问题。(递推)

3：将所解决的各个小问题的解组合起来，即可得到原问题的解。(回归)

二、分治算法：

（1）基本思想：把一个复杂的问题分解成若干个较为简单的子问题(这些子问题与原问题相似，但问题规模更小)，然后递归地解决子问题，最后把子问题的解组合成原问题的解。 （2）步骤：

1：把一个复杂的问题分解成若干子问题(D(n))； 2：递归地解决子问题(T(n/b))；

3：把子问题的解组合成原问题的解(C(n)) 。

三、回溯算法：

（1）基本思想：回溯是穷举方法的一个改进, 它在所有可行的选择中，系统地搜索问题的解. 它假定解可以由向量形式 (x1,x2,…,xn) 来表示, 其中xi的值表示在第i次选择所作的决策值,并以深度优先的方式遍历向量空间,逐步确定xi 的值，直到解被找到. 回溯法列举出解空间中所有可能的情形来确保解的正确性。

（2）步骤：

1： 定义问题的解空间. 这个空间必须包含一个问题的最优解。解的空间：如果Si 是 xi的范围, 那么 S1 × S2 × ... × Sn 是问题的解空间，通常这个解空间是非常巨大的, 所以搜索一个目标解的代价是很难想象的. 为了使回溯算法更有效率,我们必须缩小搜索空间。

2：组织好解空间以便使搜索更容易。典型的组织方式是利用图或树的结构。

3：以深度优先方式搜索解空间，利用剪枝函数来避免搜索进入不可能得到解的子空间。

2

算法设计与分析期末作业

第二题

答：自拟数据：H、G、F、E、D、C、B、A （1） 合并排序

H G F E ? D C B A ? 1 2 3 4 6 7 8 9 7 2 9 4 ? 2 3 8 6 1 ? 1 7 2 ? 9 4 ? 3 8 ? 6 1 ? 7 ?

2 ? 9 ? 4 ? 3 ? 8 ? 6 ? 1 ? H G F E ? D C B A ? 1 2 3 4 6 7 8 9 H G ? F E ? 2 4 7 9 3 8 6 1 ? 1 3 8 6 7 2 ? 9 4 ? 3 8 ? 6 1 ? 7 ?

2 ? 9 ? 4 ? 3 ? 8 ? 6 ? 1 ? 3

算法设计与分析期末作业

H G F E ? D C B A ? 1 2 3 4 6 7 8 9 H G ? F E ? 2 4 7 9 3 8 6 1 ? 1 3 8 6 H ? G ? 2 7 9 4 ? 4 9 3 8 ? 3 8 6 1 ? 1 6 7 ?

2 ? 9 ? 4 ? 3 ? 8 ? 6 ? 1 ? H G F E ? D C B A ? 1 2 3 4 6 7 8 9 H G ? G H ? 2 4 7 9 3 8 6 1 ? 1 3 8 6 H ? G? 2 9 4 ? 3 8 ? 6 1 ? H ? H 2 ? 2

9 ? 9 4 ? 4 3 ? 3 8 ? 8 6 ? 6 1 ? 1 4

算法设计与分析期末作业

H G F E ? D C B A ? 1 2 3 4 6 7 8 9 H G ? F E ? 2 4 7 9 3 8 6 1 ? 1 3 8 6 H ? G ? 2 7 9 4 ? 4 9 3 8 ? 3 8 6 1 ? 1 6 H? H G ? G

9 ? 9 4 ? 4 3 ? 3 8 ? 8 6 ? 6 1 ? 1 H G F E ? D C B A ? 1 2 3 4 6 7 8 9 H G ? F E ? 2 4 7 9 3 8 6 1 ? 1 3 8 6 H ? G ? G H 9 4 ? 4 9 3 8 ? 3 8 6 1 ? 1 6 H ? H G? G

9 ? 9 4 ? 4 3 ? 3 8 ? 8 6 ? 6 1 ? 1 5

本文来源：https://www.bwwdw.com/article/y03d.html