最短路径算法的研究和应用开题报告.doc

PAGE PAGE 2 集美大学毕业设计（论文）开题报告 理 学院 数学与应用数学 专业 2014 年 设计（论文）题目 最短路径算法的研究与应用 学生姓名 甘小红 学号 指导教师 赵玲 选题目的和意义（包括本课题的研究现状和发展趋势）： 最短路径问题一直是计算机科学、运筹学、地理信息科学等学科的一个研究热点。国内外大量专家学者对此问题进行了深入研究。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。它们在空间复杂度、时间复杂度、易实现性及应用范围等方面各具特色。针对串行计算机的最短路径算法,已经几乎到达理论上的时间复杂度极限。现在的研究热点,一是针对实际网络特征优化运行结构,在统一时间复杂度的基础上尽可能地提高算法的运行效率;二是对网络特征进行限制,如要求网络中的边具有整数权值等,以便采用基数堆等数据结构设计算法的运行结构;三是采用有损算法,如限制范围搜索、限定方向搜索及限制几何层次递归搜索;四是采用拓扑层次编码路径视图,对最短路径进行部分实例化编码存储;五是采用并行算法,为并行计算服务。 本文研究目的在于关于最短路径的多种算法，为研究最短路径问题在一些出行问题、旅游问题、工程问题等应用，为企业和个人提供方便的选择方法。同时，也为参加数学建模的同学提供一些解题的思路与方法，为比赛提供有利的资源。 主要研究内容： 本课题主要从以下四个方面来探讨最短路径多种算法； （1）简单阐述图论的基本概念包括图论的历史背景以及基本概念。 （2）研究常见基本的最短路径算法。，先阐述最短路径的问题形式，列举常见的最短路径的算法Dijkstra算法，Floyd算法 （3）补充其他最短路径算法，例如遗传算法、动态规划算法等 （4）最短路径的应用，采用Dijkstra算法，Floyd算法解出最优截断切割问题 重点解决的问题是在于研究最短路径的基本算法，其他算法、以及最短路径的应用。 完成设计（论文）的条件、方法及措施： 1、文献调研较充分，目前查阅到的相关期刊7篇、专著1部，学位论文2篇，这为完成毕业论文提供了基本条件。 2、在指导教师的指导下，分析、筛选已有的信息资料，对相关内容进行认真研读，做到真正理解概念和掌握方法。在此基础上，重点研究最短路径算法的研究，分析常见算法的优缺点，选出最优方案。 3、论文撰写按构思框架、编写提纲、专题研讨几个步骤进行。研究过程中应主动与指导教师保持联系，向指导教师请教，这是完成毕业论文的保证。 预期的课题进度计划： 2014-1-15——2014- 2014-3-11——2014- 2014-5-18——2014 指导教师的意见及建议： 签名： 年 月 日 注：此表前五项由学生填写后交指导教师签署意见，否则不得开题；此表作为毕业设计 （论文）评分的依据 集美大学毕业设计（论文）开题报告 理 学院（系） 数学与应用数学 专业 2009 年 2 设计（论文）题目 Lebesgue积分与广义Riemann积分的相互关系 学生姓名 郭某 学号 2005xxxxxx 指导教师 高某 选题目的和意义（包括本课题的研究现状和发展趋势）： L积分与R积分是两种不同的积分，在一般分析教科书中，只是揭示 L积分与R定积分的关系，指出L积分是R积分的一种推广，由于广义R积分是在R积分基础上定义的，我们希望能得到广义R积分与相应的L积分的联系。但是，由于广义R积分的收敛性与绝对收敛性不是同一个概念，它们之间不是等价的，而L积分却具有绝对可积性，这就使得广义R积分的敛散性（可积性）与L积分的可积性之间的关系会更加复杂。本课题将针对这一问题展开研究，探讨在某些条件下L积分与广义R积分之间的相互蕴含关系。通过大量文献调研，目前查阅到有关这方面研究的文章甚少，内容也不完整，因此可以尝试在理论上作进一步深入研究。 本课题对L积分与广义R积分相互关系这个问题的研究，目的在于进一步阐明L积分是R积分推广的补充，进一步促进和完善L积分与R积分，也是对积分理论的进一步发展，这对于积分理论研究与实分析教学研究有着重要的意义。 主要研究内容： 本课题主要从以下三个方面来探讨L积分与广义R积分的相互关系： 1、探讨并证明一维广义R积分与L积分的相互关系（包括一维无穷限R积分与L积分的相互关系；一维R瑕积分与L积分的相互关系；一维无穷限R瑕积分与L积分的相互关系