最短路径算法的研究与应用开题报告

1集美大学毕业设计（论文）开题报告理学院数学与应用数学专业2014年4月16日设计（论文）题目最短路径算法的研究与应用学生姓名甘小红学号2010530004指导教师赵玲选题目的和意义（包括本课题的研究现状和发展趋势）：最短路径问题一直是计算机科学、运筹学、地理信息科学等学科的一个研究热点。国内外大量专家学者对此问题进行了深入研究。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。它们在空间复杂度、时间复杂度、易实现性及应用范围等方面各具特色。针对串行计算机的最短路径算法,已经几乎到达理论上的时间复杂度极限。现在的研究热点,一是针对实际网络特征优化运行结构,在统一时间复杂度的基础上尽可能地提高算法的运行效率;二是对网络特征进行限制,如要求网络中的边具有整数权值等,以便采用基数堆等数据结构设计算法的运行结构;三是采用有损算法,如限制范围搜索、限定方向搜索及限制几何层次递归搜索;四是采用拓扑层次编码路径视图,对最短路径进行部分实例化编码存储;五是采用并行算法,为并行计算服务。本文研究目的在于关于最短路径的多种算法，为研究最短路径问题在一些出行问题、旅游问题、工程问题等应用，为企业和个人提供方便的选择方法。同时，也为参加数学建模的同学提供一些解题的思路与方法，为比赛提供有利的资源。2主要研究内容：本课题主要从以下四个方面来探讨最短路径多种算法；（1）简单阐述图论的基本概念包括图论的历史背景以及基本概念。（2）研究常见基本的最短路径算法。，先阐述最短路径的问题形式，列举常见的最短路径的算法Dijkstra算法，Floyd算法（3）补充其他最短路径算法，例如遗传算法、动态规划算法等（4）最短路径的应用，采用Dijkstra算法，Floyd算法解出最优截断切割问题重点解决的问题是在于研究最短路径的基本算法，其他算法、以及最短路径的应用。完成设计（论文）的条件、方法及措施：1、文献调研较充分，目前查阅到的相关期刊7篇、专著1部，学位论文2篇，这为完成毕业论文提供了基本条件。2、在指导教师的指导下，分析、筛选已有的信息资料，对相关内容进行认真研读，做到真正理解概念和掌握方法。在此基础上，重点研究最短路径算法的研究，分析常见算法的优缺点，选出最优方案。3、论文撰写按构思框架、编写提纲、专题研讨几个步骤进行。研究过程中应主动与指导教师保持联系，向指导教师请教，这是完成毕业论文的保证。预期的课题进度计划：2014-1-15——2014-3-10：分析、筛选已有的信息资料，构思论文框架，编写论文提纲，提交开题报告。2014-3-11——2014-5-9：编写论文，提交论文打印初稿。2014-5-18——2014-6-1：毕业论文评审、答辩。3指导教师的意见及建议：签名：年月日注：此表前五项由学生填写后交指导教师签署意见，否则不得开题；此表作为毕业设计（论文）评分的依据集美大学毕业设计（论文）开题报告理学院（系）数学与应用数学专业2009年2月23日设计（论文）题目Lebesgue积分与广义Riemann积分的相互关系学生姓名郭某学号2005xxxxxx指导教师高某4选题目的和意义（包括本课题的研究现状和发展趋势）：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积分的相互关系）；2、探讨并证明多维广义R积分与L积分的相互关系；3、给出L积分与广义R积分相互关系的若干应用。重点解决的问题是：1、一维无穷限R瑕积分与L积分的相互关系；2、二重广义R积分与L积分的相互关系；3、上述相互关系的猜想与理论证明。5完成设计（论文）的条件、方法及措施：1、文献调研较充分，目前查阅到的相关参考书籍8部、论文两篇，这为完成毕业论文提供了基本条件。2、在指导教师的指导下，分析、筛选已有的信息资料，对相关内容进行认真研读，做到真正理解概念和掌握方法。在此基础上，重点分析已有结论成立的条件及证明技巧，尝试减弱或改变条件定理是否成立；尝试将定理推广至二维情形；尝试运用实分析理论与方法证明这些结论。3、论文撰写按构思框架、编写提纲、专题研讨几个步骤进行。研究过程中应主动与指导教师保持联系，向指导教师请教，这是完成毕业论文的保证。预期的课题进度计划：2009-2-23——2009-5-20：确定选题素材，分析、筛选已有的信息资料，构思论文框架，编写论文提纲。提交论文打印初稿。外文资料翻译定稿。2009-5-21——2009-6-5：毕业论文修改、定稿。2009-6-6——2009-6-14：毕业论文评审、答辩。指导教师的意见及建议：郭某某同学拟研究的课题“Lebesgue积分与广义Riemann积分的相互关系”，对其目的和意义、现状有一定程度了解，文献调研较充分，对该课题研究的主要内容及重点解决的问题思路清楚，研究条件基本具备，研究方法和措施可行。作为本科生毕业论文，选题得当，预期成果理论意义明显，将进一步促进和完善积分理论，同时对实分析教学研究能提供有价值参考。同意该同学选此课题，进行毕业论文研究工作。由于本课题的研究有一定难度，希望该同学能集中精力，尽快投入，以确保毕业论文工作顺利完成。同时，建议该同学在研究过程中进一步查阅新的资料，拓宽思维，努力实现研究成果的预期目标。签名：2009年2月23日注：此表前五项由学生填写后交指导教师签署意见，否则不得开题；此表作为毕业设计（论文）评分的依据6集美大学毕业设计（论文）开题报告理学院（系）应用物理学专业2009年2月23日设计（论文）题目中国铁路客运网网络性质的研究学生姓名赵某学号2005xxxxxx指导教师杨某选题目的和意义（包括本课题的研究现状和发展趋势）：在自然界和社会领域中存在着许多复杂系统,这些系统可用复杂网络来进行描述和研究。借助复杂网络的研究方法，我们可以通过计算机来近似模拟现实的复杂系统进而研究其性质。这对人们更好地把握现实的复杂系统有着重要的指导作用。近十年来，人们对复杂网络进行了深入的广泛的研究，如网、因特网、作者协作网、新陈代谢网等。同时,人们提出了许多网络模型，如随机图模型、无标度网络网络模型、Barabasi-Albert(BA)生长模型、Cohen模型及WLLSF模型等。在大量的实际网络中，有很多网络具有无标度网络（SFN）的性质，其度分布P(k)服从幂率定律：)(kP～rk。同时，还有许多网络具有小世界网络的性质，即具有较小的平均网络距离（～)ln(n）和较大的平均群聚系数。此外，真实网络还有很多统计上的特征，例如混合模式、度相关特性、超小世界性质等等。目前，网络上的动力学问题，如网络上的同步、渝渗信息流等，是复杂网络研究非常活跃的领域，特别是各种实际网络的动力学问题引起了人们的广泛关注。铁路系统作为重要的交通运输系统之一，对人们的日常生活和国家的经济建设起着举足轻重的作用。因此铁路系统的拓朴性质引起了人们的广泛关注，很多研究者构建了各种铁路网络和铁路客运网络来研究这一运输系统的性质。例如，Benguigui等人研究铁路网络结构的分形特性；Latora等人对波士顿的铁路系统运用各种不同测量方法研究铁路系统的效率问题。还有，Parongama等人对印度的铁路车流网络（IRN）进行研究，发现IRN的平均网络距离为2.16，平均群聚系数为0.69，故认为IRN为典型的小世界网络。对铁路系统的研究不但可以增加人们对铁路网络和铁路客运网络的了解，还可以为铁路网络的安全及承载能力的设计提供参考。对铁路网络和铁路客运网络拓朴结构和性质的深入研究将有利于优化我国铁路网络，并将对我国铁路交通事业乃至国民经济的发展起到的推动作用。7主要研究内容：利用复杂网络的方法来研究我国铁路客运系统。通过我国铁路客运时刻表上的数据，利用统计的办法，应用计算机模拟技术来研究现实的我国铁路客运系统的一些性质，进而使人们对我国的铁路客运系统有所了解。完成设计（论文）的条件、方法及措施：从两种不同的网络角度来分析我国铁路客运系统的一些性质。一种是现实的铁路地理网络：把每个铁路客运站点当作该网络中的“节点”，同时把连接站点间的铁路轨道当作网络中连接该相应站点的“节点”的“边”。在这样定义的节点和边的基础上，利用统计的方法，研究其网络性质。另一个角度为：把铁路客运系统当作车流网来研究。车流网：把每个铁路客运站点当作该网络中的“节点”，若任意的两个站点都被同一列任意车次的列车经过，则认为该网络的中相应的两节点间存在着边把它们连接起来。然后，同样也利用统计的方法，用计算机来模拟客运系统，进而研究其网络性质。预期的课题进度计划：2009-2-23——2009-5-20：确定选题素材，分析、筛选已有的信息资料，构思论文框架，编写论文提纲。从事计算机模拟，分析数据等具体论文工作，提交论文打印初稿。外文资料翻译定稿。2009-5-21——2009-6-5：实验、数据补充，毕业论文修改、定稿。2009-6-6——2009-6-14：毕业论文评审、答辩。指导教师的意见及建议：赵某某同学拟研究的课题“中国铁路客运网网络性质的研究”，对其目的和意义、现状有一定程度了解，文献调研较充分，对该课题研究的主要内容及重点解决的问题思路清楚，研究条件基本具备，研究方法和措施可行。作为本科生毕业论文，选题得当，预期成果意义明显，将进一步促进……，同时对……有参考价值。同意该同学在此方面从事毕业论文工作。建议该同学在研究过程中进一步查阅新的资料，拓宽思维。同时，要……签名：2009年2月23日注：此表前五项由学生填写后交指导教师签署意见，否则不得开题；此表作为毕业设计（论文）评分的依据8集美大学毕业设计（论文）开题报告理学院（系）应用物理学专业2009年2月23日设计（论文）题目基于Labview技术的Henon系统的虚拟混沌信号发生器的设计学生姓名郑某某学号2005xxxxxx指导教师游某选题目的和意义（包括本课题的研究现状和发展趋势）：目的和意义：混沌是非线性动力系统所特有的一种现象，由于这种现象的复杂性，人们曾一度认为混沌是不可控和不可预测的，因此尽量避免系统进入混沌状态。但是近来的研究表明，混沌不但可控，而且在某种特定环境下具有广泛的用途。目前，混沌研究已成为多学科的研究热点，渗透到通讯、信息科学、医学、生物、工程等多种领域。本课题旨在深入了解Henon混沌系统的特征，并利用Labview虚拟仪器开发平台设计出具有Henon系统特征的虚拟信号发生器。该研究在保密通信等领域具有十分广泛的用途，因此具有一定的研究意义。研究现状和发展趋势：混沌系统理论是当今国际上极其活跃的非线性科学的重要组成部分，混沌理论的研究尤其是混沌控制与同步的研究在工程、生物、社会、特别是在信息、通信等领域有着深远而广泛的前景。当前通信高技术的发展带来一系列的理论问题，迫切需要人们澄清和解决，其中混沌现象的机制与控制是主要问题之一。虽然自然界中很多的系统本身具有混沌行为，但是人们也希望知道给定一个非混沌系统，如何施加控制使其混