最新论文格式(参考模板).doc

现实很骨感，没有人会帮我们一辈子，所以我们要奋斗一生-附件1河南农业大学华豫学院毕业设计（论文）任务书分 院 计算机科学与技术学院 专 业 信息与计算科学 班 级 信计本0801 学 生 杨蔓蔓 学 号 08802080 指导教师 潘莹慧 设计（论文）题目 关于运筹学中最短路径及其算法的研究 1、设计（论文）的主要任务及目标论文的主要任务是：对多种最短优径算法进行比较，针对生活中出现的不同路径问题，找出最优的解决方法。论文的目标是：为研究最优路径问题在一些出行问题、管理问题、工程问题及实际生活问题中的应用，为企业和个人提供方便的选择方法。2、设计（论文）的主要内容本文根据运筹学中最优路径系统课题的研究背景及运筹学中最优路径系统开发的目的，对运筹学中最优路径的算法进行可行性分析。并进一步对运筹学中最优路径的算法进行比较，从而针对最短路径问题进行多种最短路径算法，找出最优的算法。3、主要文献；1王莉、李文权.公共交通系统最佳路径算法.东南大学报，2004；34(2):265-267.2马良河，刘信斌，廖大庆.城市公交线路网络图的最短路径与乘车路线问题.数学的实践与认识，2004；34（6）：3844.3章永龙.dijkstra最短路径算法优化J:南昌工学院校报,2006,25(3):30-33.4李峰，张建中.网络最短路径的算法及实现J.厦门：厦门大学学报（自然学科），2005，（44）：4042.5乐阳等.dijkstra最短路径算法的一种高效率实现J.武汉:武汉测绘科技大学学报，1999,24（3）：6264.4、设计（论文）进度安排设计（论文）各阶段名称起 止 日 期1选题及下达任务书2011.10.20 2011.11.202撰写开题报告2011.11.19 2011.12.103撰写初稿2011.12.11 2012.2.294中期检查及修改初稿2012.03.01 2012.05.065论文答辩2012.05.07 2012.05.23注：一式三份，学院、指导教师、学生各一份。附件2 学号：08802080关于运筹学中最短路径及其算法的研究分 院 计算机科学与技术学院 专 业 名 称 信息与计算科学 班 级 信计本0801 姓 名 杨蔓蔓 指 导 教 师 潘莹慧 年 月 日附件3河南农业大学华豫学院毕业设计（论文）中期检查表分 院计算科学与技术学院专 业信息与计算科学班 级信计本0701设计（论文）题目关于运筹学中最短路径及其算法的研究学生姓名杨蔓蔓学 号08802080导师姓名潘莹慧职 称讲师计划完成时间2011年4月设计（论文）的进度计划；1. 选定论文题目，收集相关资料。2011年11月2. 查阅相关期刊最新资料，提交开题报告。2011年12月3. 撰写论文初稿。2012年1月3月4. 论文修改。2012年4月5月5. 论文定稿。2012年5月。已经完成的内容：1. 选定论文题目，收集相关资料。2. 查阅相关期刊最新资料，并提交开题报告。指导教师意见：导师签字： 年 月 日 备注：附件4摘 要随着社会的进步，科技的飞速发展，人们的办事效率也得到了极大的提高，在当今的社会里，花费最小的代价收获最大的效益，成为了当今社会里各行各业一直信奉的理念，这种理念最直接地体现在求最短路径的问题上，在生活中最常见的有通信问题、公交网络问题、旅游线路设计与优化中的运筹学问题等。解决这些问题的方法有很多种，但是针对不同的问题哪一种方法才是最优的呢?这就是在解决最短路径问题时首先要解决的问题。求最短路径的方法有：dijkstra算法、floyd算法、bellman-ford算法、SPFA算法，如果我们能从这些算法中找出解决最短路径问题的最优方法，那么当人们再遇到这样的问题时，就可以节省很多人力物力，极大地提高了办事的效率。关键词：dijkstra算法、floyd算法、bellman-ford算法、SPFA算法AbstractAlong with the progress of the society, the rapid development of science and technology, the efficiency of the people also get improved tremendously, in todays society, spend a minimum cost the benefit of the biggest gain, became todays society in all walks of life have been believe in the idea, the idea is most directly reflected in for the shortest path problem, in the life the most common are communication problems, bus network problems, tourist line design and optimization of operations research, etc. To solve these problems a variety of ways, but according to the different problem which method is the best? This is the shortest path problem solving the first to solve the problem. For the shortest path method is: dijkstra algorithm, Floyd algorithm, bellman-ford algorithm, SPFA algorithm, if we can from these algorithms to find the shortest path problem solving the optimal method, so when people again encountered this kind of problem, can 附录5save a lot of manpower and material resources to greatly improve the efficiency of the work.Keywords: dijkstra algorithm, Floyd algorithm, bellman-ford algorithm, SPFA algorithm .附录6目 录0 引言 71 求最短路径算法的定义 81.1 dijkstra算法的定义 附录7u 0 引言最短路径研究的背景：（1）通信问题：假设要在n个城市之间建立通信联络网，则连通n个城市只需要n-1条线路。这时，自然会考虑这样一个问题，如何在最节省经费的前提下建立这个通信网。在每两个城市之间都可以设置一条线路，相应地都要付出一定的经济代价。n个城市之间，最多可能设置n(n-1)/2条线路，那么，如何在这些可能的线路中选择n-1条，以使总的耗费最少呢？ (2)公交网络问题：随着能源价格的不断上涨，城市空气质量的日益下降，在大力提倡环保提倡节能的今天，公共交通工具已经成为大中城市广大市民出行的首选交通工具。在一些大中城市中，公共交通网络的线路数量和覆盖范围在不断扩大，公共交通工具也由单一的公交巴士发展到包括地铁、轻轨在内的多种出行选择；不同路线和种类的公交工具的收费标准、发车间隔、拥挤程度等各不相同。这些诸多的因素为公交乘客出行路径的选择造成了一定的困难。路径选择是各类交通信息系统的核心功能，即在给定的起点和终点之间选择一条最优的路径，但是公交网络最优路径的选择不同于普通交通道路网络中最短路径的选择，由于必须考虑不同的公交线路，所以经典的最短路径算法（如Dijkstra算法、Floy算法及Moore算法等）并不能够直接用来对公交网络进行选路。由于公交线路和站点数量庞大、乘客出行选路心理多样。如何合理的组织公交网络中的线路和站点信息，以及如何表述公交出行中的换乘问题是公交网络最优路径选择的关键问题。再者是选路算法的设计，从20世纪70年代初开始人们提出了许多的公交选路算法，这些算法往往各有优缺点，也存在算法过于复杂，计算量过大，或者存储空间需求过多等缺点，且由于国内复杂的公交网络状况，乘客多样的出行策略，现有的算法往往不能很好地满足乘客的需求。（3）旅游线路设计与优化中的运筹学问题：不管是在旅游的景观线路规划过程中，还是在旅行社旅游线路设计过程中，旅游线路都是使用频率很高的一个词。就旅游者而言，对旅游线路的期望是最大化地满足其消费需要，成本最小，日程安排最方便；对旅行社来说，则希望在满足旅游者需求的前提下，降低成本，提高效益，并可面对突发事件及时调整路线；旅游景区在规划设计时就要考虑景区内线路空间布局的合理性、科学性，在管理中也要考虑如何分流、控制游客数量的问题。显然，附录8不管从哪个角度来说，旅游线路问题都是十分重要并值得深入研究的问题。本问题将从运筹学的角度出发，探讨旅游线路的优化问题。研究的意义：（1）通信最优路径问题是现如今国内外都在积极解决的问题，如果每个城市间的通信网络都是采取的最优路径的话，就可以节省很多的资源，使总的耗费最少。（2）公交网络最优路径问题是社会中普遍存在的一个亟待解决的问题，如果每条公交网络都选择最优的路径，那么城市空气质量会得到提高，也能节省资源，还能提高市民们的生活质量。（3）旅游线路设计与优化中的运筹学问题是旅游规划研究中一个重要的问题，最优旅游线路的制定，可以最大化的满足消费需要、成本最小、日程安排最方便。1 最短路径算法的定义1.1 dijkstra 算法的定义：设目的节点为,任一条链路的长度为，每个结点到的最短路径长度估计为；定义所有节点的集合为A，定义集合，并设定集合的初始值为。在算法迭代过程中，如果已经变成一个确定值，则将标记为固定点，并将其加入集合。在算法的每一步迭代中，在以外的节点中，必定是选择与目的节点最近的节点加入到中，算法的具体步骤如下：（1），。(若和不是相邻节点，则)（2）求解使成立的，即寻找下一个和目的节点最近的节点；令，