下载此文档

最短路径问题设计说明.doc


文档分类:IT计算机 | 页数:约26页 举报非法文档有奖
1/26
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/26 下载此文档
文档列表 文档介绍
目录第1章绪论 (名词定义) 2第2章算法设计与实现 12第3章实验结果分析与算法对比 15第4章总结与展望 16参考文献 。寻找最短路径就是在指定网络中两结点间找一条距离最小的路。最短路不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等。最短路径算法的选择与实现是通道路线设计的基础,最短路径算法是计算机科学与地理信息科学等领域的研究热点,很多网络相关问题均可纳入最短路径问题的范畴之中。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。本文主要解决的问题是:给定带权有向图G=(V,E),对任意顶点,∈V(i≠j),求顶点到顶点的最短路径。即给定一个有向图,再给出任意2个不相邻的顶点,求2个顶点之间的最短距离。 给定一个带权有向图G=(V,E)中的各个顶点之间的权值,对任意输入2个顶点,∈V(i≠j),求出从到的最短路径。 输入:节点数目N,邻接矩阵VR[N][N]约束条件:其中, 输出(目标函数):min{Dist(,)}(名词定义)(1)时间复杂度算法的时间复杂性是指执行算法所需要的时间。一般来说,计算机算法是问题规模n的函数f(n),算法的时间复杂性也因此记做T(n)=O(f(n))。因此,问题的规模n越大,算法执行时间的增长率与f(n)的增长率正相关,称作渐进时间复杂性。(2)空间复杂度空间复杂度(plexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间,包括存储算法本身所占用的存储空间,算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法空间复杂度的计算公式记作:S(n)=O(f(n)),其中,n为问题的规模,f(n)为语句关于n所占存储空间的函数。(3)图的基本概念图:由顶点集V和顶点间的关系集合E(边的集合)组成的一种数据结构,可以用二元组定义为:G=(V,E)。有向图:在图中,若用箭头标明了边是有方向性的,则称这样的图为有向图。权:在图的边或弧中给出相关的数,称为权。权可以代表一个顶点到另一个顶点的距离,耗费等,带权图一般称为网。邻接矩阵:表示一个图的常用存储表示。它用两个数组分别存储数据元素(顶点)的信息和数据元素之间的关系(边或弧)的信息。,具体组织结构如下:第1章绪论。本章主要对最短距离问题进行描述和问题进行分析,同时针对一些名词进行定义和解释。第2章算法的设计与实现。本章主要针对最短距离问题是用穷举法、回溯法、贪心法、动态规划法实现,并对算法进行描述、设计和分析。第3章实验结果分析与算法对比。本章主要对输入数据阐述,并对实验结果进行分析和算法分析与对比。第4章总结与展望。总结了本文的主要工作、重要贡献以及存在的不足,提出了进一步的工作内容,并对以后的研究工作进行了展望。(ExhaustiveSearchAlgorithm)法又称列举法,其基本思想是逐一列举问题所涉及的所有情况。穷举法常用于解决“是否存在”或“有多少种可能”等问题。穷举法的算法特点是算法简单,但是运行时所花费的时间量大,需要将问题所涉及的有限种情形须一一列举,既不能重复,又不能遗漏。用穷举法实现广度优先搜索。广度优先搜索算法是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型。其别名又叫BFS,属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位址,彻底地搜索整张图,直到找到结果为止。 对问题使用广度优先遍历,将所有可能的结果首先保存起来,再在结果中查找最短路径的结果,打印出来。 ,其算法步骤可以描述为如下:从文件中读取图的节点数目、读取节点数目Npoint、起始点Start、结束点End、邻接矩阵**WeightArry。动态分配存储空间MyMark[Npoint!]。初始化路

最短路径问题设计说明 来自淘豆网www.taodocs.com转载请标明出处.

相关文档 更多>>
非法内容举报中心
文档信息
  • 页数26
  • 收藏数0 收藏
  • 顶次数0
  • 上传人799474576
  • 文件大小916 KB
  • 时间2020-01-26