算法分析与设计课程报告

《算法分析与设计课程报告》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、算法分析与设计课程报告重庆邮电大学研究生堂下考试答卷2015-2016学年第2学期考试科目算法分析与设计姓名年级学号专业计算机科学与技术2016年6月2日算法分析与设计课程报告算法分析与设计课程报告摘要：本文选取了两个不同的问题，查找特定元素和单源节点间最短路径问题，采用不同的的求解算法来对问题进行分析求解，从理论分析上给出了不同算法在解决该问题时的效率和开销，并通过程序仿真实验，对理论分析结果进行验证。在解决查找问题时，采用了线性表直接查找，二叉排序树查找，平衡的二叉排序树查找三种方法。在解决单源节点间最短路径问题时，采用了蛮力搜索和迪杰斯特拉算法两种方法。

2、通过对数据实例的仿真结果的分析与对比，对不同算法在解决同一个问题的实际性能与理论分析进行了比较验证。关键词：查找；单源节点最短路径；理论分析；实验仿真1问题和算法的定义该部分对报告所分析的两个问题，查找问题和单元节点间最短路径问题进行了介绍和定义，并对解决对应问题给出了所选算法的的介绍。1．1查找问题查找问题就是在给定的集合（或者是多重集，它允许多个元素具有相同的值）中找寻一个给定的值，我们称之为查找键。有许多查找算法可供选择，其中既包括直截了当的顺序搜索，也包括效率极高但应用受限的折半查找，还有那些将原集合用另一种形式表示以方便查找的算法。最后一类算法对于现

3、实应用具有特别重要的价值，因为它们对于大型数据库的信息存取来说是不可或缺的。对于查找来说，没有一种算法在任何情况下都是最优的。有些算法速度比其他算法快，但需要较多的存储空间；有些算法速度非常快，但仅适用于有序的数组，诸如此类。和排序算法不同，查找算法没有稳定性问题，但会发生其他问题。具体来说，如果应用里的数据相对于查找次数频繁变化，查找问题就必须结合另外两种操作一起考虑：在数据集合中添加和删除元素的操作。在这种情况下，必须自习选择数据结构和算法，以便在各种操作的需求之间达到一个平衡。而且，对于用于高效查找的特大型数据集合来说，如何组织其结构是一项不同寻常的挑战

4、，而这对实际应用具有非常重要的意义。报告中，针对查找问题采用了三种方法：线性表直接查找，二叉排序树查找，平衡二叉排序树查找三种方法。1）其中线性表(LinearList,LL)直接查找，通过将数据集合存储在数组中，每次从数组首地址开始一直搜索到数组末尾，直到查找到待查元素和到达数组末尾为止。并针对该方法给出了一个优化的算法，对数组中的元素增加一个频度域，将查找频度最高的元素放在数组最前面，依次按频度对数组中元素进行排序。2）二叉排序树（BinarySortTree,BST）查找，BST又称二叉搜索树，其定义为：二叉排序树或者是一颗空树，或者是具有如下性质的二叉

5、树：①若左子树不空，则左子树上所有节点的值均小于它的根节点的值；②若右子树不空，则右子树上所有节点的值均大于它的根节点的值；③左、右子树也分别是二叉排序树；④没有键值相等的节点。从BST的定义中可知，在BST中查找一个元素的过程，即从根节点开始，每次根据待查元素与根节点的比较，决定查找成功或者依左或右子树查找，直到找到待查元素或者都到叶子节点为止。3）平衡二叉查找树（Adelson-VelskiiandLandis，AVL树），一棵AVL树是一棵二叉查找树，其中每个节点的平衡因子定义为该节点左子树和右子树的高度差，这个平衡因子要么是0，要么为+1或者-1（一棵

6、空树的高度定义为-1）。因此AVL树是一种特殊的二叉查找树，其左右分支深度比较平衡，这样就缩短了树的高度，从而降低了查找的次数。在AVL树种查找元素的过程类似在二叉排序树中查找元素。1．2单源节点间最短路径问题在报告中，考虑单源点最短路径问题，对于一个加权连通图的一个称为起点的给定定点，求出它到所-24-算法分析与设计课程报告有其他定点之间的一系列最短路径。需要说明的是，这里所关心的不是从一个起点出发访问所有其他定点的单条最短路径，这种问题的难度更大。单起点最短路径问题要求的是一组路径，每条路径都从起点出发通向图中的一个不同顶点，其中某些路径可能具有公共边。在

7、求带权连通图中最短路径问题有两个著名的算法，Dijkstra算法和Floyd算法，其中Dijkstra算法是解决单源节点间最短路径问题，报告中采用的就是这种算法，而Floyd算法是求解图中每对节点间的最短路径问题。报告中考虑的两种算法如下：1）基于全排列的蛮力搜索算法，对连通图中除首节点和尾节点外，其他节点进行全排列，对其中每一个排列构成的路径首先进行合法性检测，然后通过笔记记录，找到最短路径。2）Dijkstra算法，该算法的基本思想是按照路径长度的增长来通过迭代，依次求得v0节点到其他节点的路径长度，当经过n次迭代后，即可求出v0到其他n-1个节点之间的最

8、短路径长度。首先将节点分为两个集合S1