前言：中文期刊网精心挑选了运筹学最短路径范文供你参考和学习，希望我们的参考范文能激发你的文章创作灵感，欢迎阅读。
运筹学最短路径范文1
关键词： 高职院校 Dijkstra算法 标号法 表格
Dijkstra算法是典型的最短路算法，用于计算一个顶点到其他所有顶点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的顶点很多，因此效率低。但Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构、图论、运筹学等。
给定一个带权有向图，其中每条边的权是一个非负实数。另外给定图中的一个顶点，称为源。现在我们要计算从源到所有其他各顶点的最短路径长度。这里的长度指路上各边权之和。这个问题通常称为单源最短路径问题。Dijkstra算法（标号法）是按各顶点与源点间的路径长度的递增次序，生成源点到各顶点的最短路径的算法，即先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从源点到其他各顶点的最短路径全部求出为止。
关于最短路问题Dijkstra算法的教学，看上去不难，但老师讲授起来很费劲，学生学起来更加感觉困难。对此，不寻找恰当的教学方法，一味地啃书本是难以达到良好的教学效果的。往往还会致使学生厌学，从而对相关课程的学习失去兴趣。高职学生相对于其他普通本科院校的学生，在数学学习方面能力要弱一些，因此，高职院校的数学教师更应该注意寻找适合的教学方法来提高学生的学习兴趣，从而提高课堂教学效率。教师应改变过去“填鸭式”、“灌输式”的教学方法，充分发挥学生的主体作用，灵活运用启发式教学方法，激发学生思维和质疑，培养学生的创新精神和独立探讨问题的能力。要引导学生对问题多思考，多问几个“为什么”，抓住内容相关和相反的部分，对知识进行横向和纵向的比较，并掌握它们之间的内在联系和规律，培养学生系统而全面的思维方式。教师应鼓励学生主动发表自己的见解，互相探讨、启迪，培养学生勇于探索，敢于创新的精神，引导学生自主学习。此外，教学中还应注意确保学生有充分思考的时间，切实加强学生对问题的认识程度，让高职学生真正感受到对数学的学习并不是那么困难的事情，不断增强学习数学的成功感，增强学习信心，从而优化课堂教学效果。
。
各行的数据是怎么计算出来的呢？
例：用Dijkstra算法求下图从顶点到其余顶点的最短路。
参考文献：
［1］王信峰.计算机数学基础［M］.高等教育出版社，2009.
运筹学最短路径范文2
【关键词】配电网；动态规划技术；恢复供电
当前，智能电网的发展在一定程度上带动了电网技术的发展，并且成为了电网技术发展的重要方向。实际上，智能电网的重要组成部分在于智能配电网，智能配电网的主要特征为拥有完备的自愈能力，同时还能够最大程度的减少电网故障给用户带来的影响。而配电网故障的恢复是智能配电网自愈功能实现的重要过程，配电网故障恢复问题主要指配电网发生故障以后，在故障定位与故障隔离的基础之上，应用一定的故障恢复策略对其进行操作，从而确保供电的平稳与正常。
一、对最佳路径的分析
配电网故障区域恢复供电的最佳路径事实上是在故障情况下的配电网络重构。主要的目的在于，能够快速的将非故障区域供电恢复，与此同时，还能够有效的满足线路负载容量的要求以及线损最小等各个方面的条件。现阶段，在配网自动化领域中研究最多的在于怎样能够快速的实现故障隔离以及快速的恢复费故障区域的供电技术方法，因此，在恢复路径的最优化选择方面出现了较多的研究。
一般而言，配电网故障区域恢复供电的路径为多目标最佳路径问题，现阶段在最佳路径问题的研究上较多的便是城市交通网络中的最短路径问题的研究。由于问题解决的思路存在着极大的不同点，因此最短路径问题能够被分为单元最短路径算法与基于启发式搜索最短路径算法[1]。这与邓群，孙才新，周驳仍凇恫捎枚态规划技术实现配电网恢复供电》一文中的观点极为相似。其中，单元最短路径算法主要体现在几个方面，即：
第一，在GIS空间查询语言方面的最短路径。该职工路径的研究方法在当前还停留在理论研究方面，例如在MAX中定义了一套空间查询语言，该套语言对其完备性给予了相关证明，同时通过举证的方式，对范围查询与时态查询等进行了应用分析。
虽然，对于GIS空间发展研究GeoSQL为一种有效的处理最短路径的手段，但是GIS受到数据库技术发展的制约与影响，导致实际的应用领域和背景的不同，使其和商用之间还有很长的一段距离。
第二，在功能模块思想路径方面，需要按照不同的分类方法实施，而单元最短路径问题的算法能够被分为很多种，例如神经网络法与基于人工智能的启发式搜索算法等，对于不同的背景应用需求和具体软件应用的环境，各种算法在空间的复杂程度与时间的复杂程度等都有明显的体现[2]，这与李振坤，周伟杰，钱啸等在《有源配电网孤岛恢复供电及黑启动策略研究》一文中有着相似的观点。并且各种算法在故障恢复方法中各具特色。
另外，启发式搜索最短路径算法也是一种有效的手段。基于启发式方向策略最短路径算法，其中包括空间有效方向的可控参数法，该方法能够有效的调节相关系数，在有效方向上路径无效的时候，能够确保得到有效的路径。
二、最佳路径的选择方法分析
事实上，配电网故障区域恢复供电的最佳路径并不是简单的路径问题，而是多目标最佳路径问题。为此，在研究配电网非故障区域恢复供电的最佳路径过程中，需要对其展开综合的分析。
首先，在多目标分析方面，通常在选择配电网非故障区域恢复供电最佳路径的时候，最为重视的目标为：
第一，在恢复供电路径的过程中，馈线负荷不能过载，同时，还需要确保恢复区域的电压质量能够与实际规定的标准要求相吻合。当供电质量可靠性最高的时候，那么恢复的时间将会很短[3]；这与邓昆英，汪凤娇，饶杰等在《智能配电网有功自治互动建模研究》一文中的观点极为相似。另外，供电过程中，线损最低，证明开关拉合的次数最少，同时现场的操作点也会最少。
第二，在动态规划技术恢复供电的最短路径方面需要明确，动态规划主要是运筹学的一个分支，它是求解决策过程的最优的数学方式。早在很久以前，就已经有研究人员对多阶段过程转化问题转化为一系列的单阶段问题，并且逐一进行求解，这标志着解决这类过程优化问题的新方法的创立，即动态规划技术。
本文主要将一典型的复杂配电网络作为研究例子，该连通系包括10个电源点，8个分支点，同时联络开关有16个。将其加入到配网潮流方向和典型的运动方式中，将联络开关和电源点作为定点，那么可以将其分为26个定点。尽管从数量上顶点比较多，但是由于存在着较为复杂的网络关系，使得该问题成为一个极为简单的最短路径问题[4]。这与杨建在《配电网无功补偿系统的关键技术研究》一文中的观点有着相似之处。加之恢复路径主要指费故障区域相关的联络开关与相应路由，为此我们可以将其理解为从不同电源点出发到各个联络开关的最短路径问题，这样一来，故障恢复工作的实施便简单的多。
总结
本文主要从两个方面左手，共同分析了采用动态规划技术实现配电网恢复供电的方法与效果，一方面着手于最佳路径的分析，另一方面着手于最佳路径的选择方法。从这两个方面可以看出，利用动态规划技术去实现配电网恢复供电是一种可行的方法。但是，受到历史原因的影响，我国城市配电网络还缺少标准的规范要求，导致配电网常常出现一些事故。因此，恢复配电网供电已经成为当务之急。随着科技的发展，智能配电网已经被广泛的应用在供电方面，这为平稳供电提供了一定的保障，同时也为恢复配电网故障供电创建了良好的环境与条件等。
参考文献
[1]邓群，孙才新，周驳.采用动态规划技术实现配电网恢复供电[J].重庆大学学报（自然科学版），2006，29（3）：40-44.
[2]李振坤，周伟杰，钱啸等.有源配电网孤岛恢复供电及黑启动策略研究[J].电工技术学报，2015，30（21）：67-75.
[3]邓昆英，汪凤娇，饶杰等.智能配电网有功自治互动建模研究[J].机电工程技术，2014，（2）：4-7.
[4]杨建.配电网无功补偿系统的关键技术研究[D].中南大学，2002，（12）：56-78.
运筹学最短路径范文3
关键词：LINGO；动态规划； 最短路问题； 生产批量计划问题
中图分类号：G642 文献标识码：A 文章编号：1009-3044（2014）04-0743-04
在交通专业课程如《交通运筹学》、《交通系统分析方法》等的教学过程中，大量涉及到可划分为多阶段的优化问题求解，这些问题的求解一般使用动态规划（dynamic programming）方法。动态规划将决策问题的全过程划分为若干个相互联系的子过程（每个子过程为一个阶段），然后按照一定的次序来求解。当划分的阶段个数较多时，手工求解动态规划问题相当麻烦。由于在实际的交通工程规划实践中，涉及到的动态规划优化问题规模往往较大，指导学生掌握相应的优化软件求解动态规划问题一方面能增进学生对动态规划法的理解掌握，另一方面能锻炼学生的编程能力，是一项十分有意义的教学工作。
美国LINDO系统公司开发的LINGO由其求解问题的高效性和稳定性，成为目前广泛使用的优化软件。LINGO是一套专门用于求解最优化问题的软件包，其内置了一种建立最优化模型的的语言，可以简便表达出问题，同时利用LINGO高效的求解器可快速求解并分析结果。LINGO在处理含有大量变量和约束条件的优化问题时，一般使用数组和矩阵的输入方法：LINGO程序首先定义集合段，确定需要的集合及其属性，然后定义数据段，用于输入已知原始数据，最后使用函数对集合进行操作。在通常介绍LINGO使用的文献中[1][2]，一般着重于叙述其如何求解线性规划和非线性规划等具有明确目标函数的优化问题，很少关注如何用LINGO求解复杂的动态规划问题，该文通过分析交通运输中常见的最短路问题和生产批量计划问题，给出用动态规划方法求解的LINGO代码，指出LINGO可以在不需要目标函数的情况同样很好地求解多阶段优化问题。
1 动态规划法求解实例
实例1 最短路问题
在纵横交错的公路网中（图1所示），货车司机希望找到一条从一个城市到另一个城市的最短路。图中节点1—8代表货车可以停靠的城市，弧旁的数字表示两个城市之间的距离（百公里）。若货车要从城市1出发到达城市8，问如何选择行驶路线使所经过的路程最短。
问题分析：该最短路问题满足动态规划的最优性原理，即“从节点1到节点8的最短路的子路径仍然是相应节点间的最短路”，用[D（i，j）]表示从节点[i]和[j]有弧相连时相应的距离，[L（i）]表示从节点1到节点i的最短路程数。则不难得到以下的动态规划由前向后递推方程：
根据式（1），再进一步定义当节点[i]在从节点1到节点[j]的最短路径上时，[P（i，j）=1]，否则[P（i，j）=0]，编写如下LINGO求解代码：
运行LINGO得到如图1所示的最优解报告。
从报告中可以看到，最短路径找到，由[L（8）]的值可以得出，从城市1到城市8的最短路程数为14，由各个[P（i，j）]的值分析可知，从城市1到城市8的最短路线为[1258]。
实例2（生产批量计划问题）
某企业生产某种产品用以满足市场需求。通过统计，该产品今后[T]4周的外部需求（订货量）分别是[d1]千件、[d2]千件、[d3]千件和[d4]千件。如果第[t]周要开工生产，则第[t]周开工所需的生产准备费为[st]千元（与生产的数量无关），每件产品的生产费为[ct]千元。如果在满足需求后周末有产品剩余，每千件产品的存储费为[ht]千元。设第[t]周末的库存量为[It]，假设开始没有库存，记为[I0=0]且不考虑生产能力限制，问工厂应如何安排生产，在按时满足需求的条件下，使总费用最小？
问题分析：对于生产批量计划问题，分析可知有如下两条性质成立：
由于以上两个性质，只有当上一时段库存[It-1=0]时，本时段才考虑进行生产，且一旦生产，其生产量一定为某些后续时段需求量的总和，即[xt∈{dt，dt+dt+1，…，dt+dt+1+…+dT}]。这样如用[ft]表示当[t]时段初始库存为0时，从[t]时段到[T]时段的子问题的最优费用值，可以建立如下的递推关系：
运行LINGO得到如下最优解报告：
从报告可以看到，[F（1）=561]，即从第1周到第4周末的最优费用为561（千元），分析其它[F]值得到，最优的生产批量计划为第1周生产2（千件），第2周生产5（千件），第3周不生产，第4周生产4（千件）。
2 结束语
本文针对用动态规划方法手工求解多阶段优化决策问题十分繁琐的特点，利用LINGO软件将各个动态规划递推方程简洁明确地编程实现，帮助学生更好的理解了各阶段决策变量之间相互递进的关系，同时更重要的是交通专业学生熟练地掌握了软件的使用，才能解决实际工程规划中的大规模复杂优化问题，LINGO软件的教学实践促进了《交通运筹学》、《交通系统分析方法》与《交通规划》等课程的融合。
参考文献：
[1] 李晓川，朱晓敏，赵乃东. 基于Lingo的运输优化系统设计与开发[J]. 物流技术，2010（Z1）.
运筹学最短路径范文4
关键词 物流管理；运筹学；资源配置；最优化
中图分类号 F252
文献标识码 A
文章编号 （2014）13-0112-01
物流业是指物品从发出地实体流动向接受地的过程。当货物数量不断增加，运送方式日趋多样化时，如何配置运送物品时的资源成为较少物流企业成本，使企业利益最大化的关键。这其中就要运用到运筹学的思想，在既定的条件下，寻找能使目标函数最大化的组合。
一、运筹学与物流管理之间的关系
运筹学课概括为“依照给定条件和目标，从众多方案中选择最佳方案”，即在实行操作管理的各个领域，运用数学方法和包括概率论、数理分析、线性代数等在内的工具，对需要进行管理的问题统筹规划人、财、物的组织、调度等，作出决策使系统运行最优解而必须使用的的一门应用科学。
在科学技术快速发展的社会，企业间的竞争变得异常激烈。减少开支，节约成本成为了企业管理中首要的问题。因此，随着科学管理被越来越多的企业所重视，运筹学作为管理学的核心与基础，自然有着极其重要的作用。作为管理工具，运筹学在企业产品定价问题，生产库存问题，运输问题等等一系列方面可以提供最优化模型。而物流系统的主要功能是将物品用最小的成本在两地之间进行运输，其追求的是一种及时快速，能够最大程度节约人力物力的物流服务。从这一点上讲，是与运筹学解决资源最优配置的目的不谋而合的。
物流管理较运筹学的起步较晚，但现代社会运筹学在物流企业中的作用不断扩大。将两者结合在一起，才能更好的实现达到企业节约成本的目的。
二、运筹学在物流系统中的运用
运筹学的主要理论包括规划论、图论、排队论、博弈论等。在物流运输这一庞大的系统中，每个环节都可以与运筹学中的理论相对应。规划论中的线性规划可以用来求解物资配送、人员分配等问题；整数规划可以用来求解工作人员及机器数目、厂房选址等问题，动态规划可以解决最优路径生产调度、设备更新等问题。图论可以直观的将构建的模型反映出来，运用最短路径和最大流等理论知识，可以求解运输费用最小化、运输路径最短等重要问题。排队论可以使物流运输时最大程度得利用场地资源，解决运输机或货车应从哪个入口进入、如何离开等问题，提高物流系统的运作效率。
因此，物流系统中几个关键的环节，包括运输、储存、装卸、搬运、流通加工、配送等，都可以用运筹学中与之对应的方法。
三、运用运筹学节约物流成本
（一）基于线性规划的运输成本最优化问题
Z表示的是运输所需的总费用，利用上述所给模型进行求解，即能得到一个使运输费用最小的调配方案。
（二）基于图论的物流网络优化问题
设某种物资从m个仓库发出，称之为出发点，需要运输至n个目的地，成为收货点，在制定运输方案时，首先需要画一个示意图，表明收发点的大致所在位置、货物的收发量、运输路途的长度。在示意图上出发点用“”表示，收货点用“”表示，将收货量标记在其中。收发点之间的运费及其线路的长度标记在路途示意线的旁边。然后做运输物资的流向图，物资运输的方向用“”来表示，把调运物资的量记在“”的右边并加括号表示和运输线路长度的区别，这样就构成了如下所示的物资调运流量图。
在物流调运中，将物资从发点调运到收点的运输方案有很多，但我们优化物流网络的目的是使用运输力量最小的方案。
（三）基于排队论的仓库人员配置问题
设某仓库中，需要s个具有相同能力的工作人员为运货车辆装载，平均每人每小时可装载μ辆货车，平均每小时有λ辆货车需要装载，设货车到来服从泊松分布，服务时间服从负指数分布。
根据排队论的基本理论，我们可以轻易地看出在这里运货车辆是顾客，工作人员是服务设施。我根据排队论中关于标准的M/M/C的算法
多个服务站下 ， 表示系统中没有运货车辆的概率， 表示系统中有n个顾客的概率。因此平均队长为 。平均等待时间为 。为了使系统中的运货车辆不会排成无限的队列，s必须满足条件： 。
四、结语
物流业的发展离不开科学技术的支持，其中尤以运筹学为主。运筹学通过将物流系统中各个环节的变量和所要优化的目标抽象成模型，通过模型来理论的配置资源，使资源得到最合理的利用，从而达到节约成本、提高利润的目的。
参考文献：
[1]熊义杰.运筹学教程[M].北京：国防工业出版社，2004.
[2]宋伟刚.物流工程及应用[M].北京：机械工业出版社，2003.
运筹学最短路径范文5
关键词:最短路;迪杰斯特拉;数据结构;标准模板库;优化算法
中图分类号:TP312 文献标识码: A文章编号:1009-3044(2009)13-3439-04
1 引言
最短路问题是一个经典问题,过程涉及算法设计、数据结构、运筹学、图论等多方面的知识,有很深远的理论研究意义,并在许多学科中有重要应用。在实际生活以及工程实际应用中,最短路问题的求解算法也尤为重要,例如交通路线的选择、公用设施的地点布局、管道线路的安排、智能机器人的路线选择、最短时间规划等等。
实际问题中又以单源最短路问题居多,解决单源最短路问题有比较优秀的迪杰斯特拉算法,著名的E.W.Dijkstra在1959年提出该算法,是图论中求解最短路问题的一个经典算法。由单源最短路问题可以引申出更多类似的问题,比如时间规划问题、成本预算问题、收益最大化问题等,这些与最短路同构的问题,往往可以应用Dijkstra算法得到满意的结果。
随着计算机技术的发展,绝大多数算法问题已经转变为在计算机平台上实现,其中又以使用计算机程序处理为主。在计算机编程实现的过程中,程序往往不够优化,达不到令人满意的结果,效率瓶颈突出。本文通过分析Dijkstra算法的本质,透彻分析计算机语言的特点,加之合理的数据结构,并使用C++语言实现优化的Dijkstra算法,达到了一般意义下的时间复杂度和空间复杂度的下限。
2迪杰斯特拉算法
2.1 迪杰斯特拉算法基本思想
单源最短路问题是指在一个有权的图中求出源点到其他所有点的最短路径,而Dijkstra算法是解决单源最短路问题的有效算法,在图中不存在负环(即一条从源点到源点不经过重复的边并且权值之和为负的路径)的情况下,可以得到正确的结果。其基本思想是算法中的贪心思想:每次找到一条最短的未知路径,然后用该路径更新其他未知路径的最短距离,直到不存在未知路径为止。
2.2 迪杰斯特拉算法数学描述
步骤如下:
图G=(V,E),其中V为点的集合,E为边的集合,源点为src,已经求得最短路的目的点集设为S, 源点到点i的距离d[i]
1)?坌(src,i)∈E,置d[i] = V(src, i)
2)?坌(src,i)?埸E,置d[i] =∞
3)d[src] = 0;
4)?埚j∈V,j?埸S,使得d[j]=min{d[x]},x∈V,x?埸S
5)S=S+{j}
6)?坌i∈V,i?埸S,置d[i]=min{d[i],d[j]+weight(j,i)}
7)若|S|≠|V|,转至2)
8)结束
2.3 迪杰斯特拉算法复杂度分析
分析2.2的数学描述,算法的时间消耗主要在循环上,而每次循环耗费时间的就是步骤4),即找未探索点中的最近点。设n=|V|,即n表示图中顶点的个数;m = |E|,即m表示图中边的条数。则最多循环n次,因为每次循环将使得S中的点数增加一个;同时,每次循环中找最近点的过程需要找n次,因为总共有n个点。综合考虑后,传统迪杰斯特拉算法的时间复杂度为O(n2)。空间消耗主要在图的存储上,如果采用邻接矩阵表示图,则空间复杂度为O(n2)。
3 算法优化探究
3.1 使用链表优化
从上面的分析可以得到空间复杂度为O(n2)的算法,似乎空间复杂度不是很高,然而对于顶点很多,而边却很少的稀疏图,用邻接矩阵表示的图在空间利用率上会相当低。因此,我们考虑到了使用基于链表的邻接表来表示图,从而将空间复杂度从O(n2)转变为O(m),对于处理稀疏图,有很大优势。
在访问图中的边时,若采用邻接表,则访问的次数也会有所降低,这是因为用邻接矩阵表示图的时候,对于边的访问,必须从一个顶点循环枚举到所有顶点的边,然而由于图的稀疏性,一个点所连接的边可能很少,甚至出度为0,此时用邻接表就要明显优于邻接矩阵表示的图。
3.2 使用静态内存的链表优化
链表具有灵活和高效的特点,然而的实际应用过程中往往不那么容易。一方面是因为早期的C语言不具有链表数据结构,必须自己手动编写链表结构,程序很容易出错。对于参加程序设计大赛的选手来说,手写代码量较大的数据结构,除非在万不得已时,一般是不会手写数据结构代码的,因为容易出错,对于程序的正确性难以保证。在最短路问题中,若用邻接表来表示图,只需要编写创建链表和访问链表的函数,所以程序量在该算法中不是很大。
经常写程序的话,就会体会到使用动态内存的数据结构,不但容易出错,在效率上更是会明显地降低。以约瑟夫问题举例来说,使用链表数据结构按照理论应该是比数组直接简单模拟的算法要快,然而在实际过程中就会发现两者无太大差别,在数据量比较大的时候,数组反而比链表快得多。实际上这是链表使用了动态内存的原因,申请动态内存将会占据大量的时间。这就留给我们一个问题,在使用链表的过程中,是否可以使用静态内存?对于程序设计很熟悉的人员,马上可以想到,先申请一个很大的数组,然后将该数组作为动态数据申请的数据段,就可以实现静态内存的链表。这样优化之后,可以在很大程序上减少程序的运行时间,同时也可以减少系统管理动态内存出错导致的问题。该优化措施的有效性可以在后面的实验中得到验证。
设有权有向图G=(V,E),V是顶点的集合,|V|=n;E是边的集合,|E|=m。下面给出使用静态内存链表的定义过程,申请内存过程,以及创建邻接表的过程,使用C++代码表示如下:
//程序头部
#include
#include
#include
using namespace std;
const int N = 31000, M = 2500000, INF = 1000000000;
//链表定义
struct data
{
int id, w; //指向顶点,权值
data *next; //链表后继
}mem[M];
int mem_size, size, n, m;
//申请内存过程
node new_node(int id, int w)
{
mem[mem_size++] = (data){id,w,0};
return mem+mem_size-1;
}
//读入边的信息
for(i = 0; i < m; i++)
{
scanf("%d%d%d",&j,&id,&w);
tmp = g[j]->next;
g[j]->next = new_node(id,w);
g[j]->next->next = tmp;
}
3.3 使用高级数据结构进行优化
上面两个步骤的优化都是行之有效的方法,然而在使用了静态内存链表的数据结构后,我们仍不能降低该问题的理论时间复杂度上限O(n2)。再来透彻地分析一下原始的迪杰斯特拉算法,我们发现对于每次循环查找最近点的过程,最坏情况下循环上限是n次,查找问题是算法中一个典型的问题,我们通常会想到使用哈希表来查找,这样可以将查找的的复杂度降低至O(1)的复杂度,然而哈希技术一般是针对数字方面的查找,对于从给定集合中查找最小值的问题,似乎束手无策,那么还有什么好的技术可以使用呢?
二杈搜索树BST(Binary Search Tree)的查找过程和插入过程以及其他一些常用操作都只需要O(log n)的时间复杂度,常用的二杈搜索树有AVL、Treap、Splay、红黑树等等,这些高级数据结构都有着很高执行效率,在解决算法问题的过程中得到了广泛的应用,在数据库技术中也有很多应用,是数据处理技术的理论基础。然而要想自己写出这些高级数据结构的全部操作,对于一般的程序设计者来说,还是有相当大的困难,虽然可以花费长时间来写出模板,然后在以后应用过程中直接调用即可,但是在程序设计比赛等一些特殊场合来说,程序的精简性尤为重要。
说到程序的精简性,我们一定会想到STL(Standard Template Library),即标准模板库。STL中包含了很多种数据结构的通用模板,使用起来尤为方便,程序简洁,且不容易出错。例如上面提到的BST,在C++ STL中使用了红黑树来实现,虽然不能实现BST的所有操作,但是对于处理最短路问题,使用C++ STL中的BST数据结构set,可以满足要求。set具有插入,查找,删除等操作,完全可以胜任最短路问题中的查找要求。
回头再来思考Dijkstra算法,过程中主要的操作就是查找最小值,以及删除最小值。只是对最小值处理的话,其实我们有更简单的数据结构来处理,这就是被称作“堆”的数据结构,堆支持查找最小值,删除最小值,插入某个数值等操作,在最短路算法过程中使用堆的数据结构,不仅程序编写量小,更重要的是查找效率比BST高得多,查找的时间复杂度可以降低至O(1)。可见,如果使用的堆来查找,可以极大的降低时间复杂度,查找的时间复杂度为O(1),删除最小值的时间复杂度为O(log n),总共循环n次,可见时间复杂度已经降低至O(n*log n),相比于原先的O(n2),有了很大的提高。
5 使用优先队列全面优化程序
一个好的程序,不仅要求效率高,还要求容易实现,容易编写,这也是为什么即使计算机的运算速度达到无限快时,我们还要继续研究算法的原因。堆的数据结构实现起来并不困难,但是对于不熟悉的人来说还是有一定难度。其实这里我们可以继续使用STL来简化程序,简化后的程序程序量小,简洁易懂,应用价值很高。
STL中拥有heap的数据结构,也就是堆,但是STL中的heap并没有封装成类,在通用性和安全性上还存在问题,使用起来也不是很方便。STL同时提供优先队列priority_queue,实际上就是把heap进行类的封装,以方便使用。需要注意的是priority_queue默认为大根堆,而我们需要的是小根堆,所以需要自行编写比较函数,以使用小根堆,具体的C++代码如下:
typedef data * node;
node g[N];
bool mark[N];
int dist[N];
//定义堆内数据类型
struct heap
{
int id, dist;
};
//自定义比较函数以使用小根堆
bool operator < (const heap& x, const heap& y)
{
return x.dist > y.dist;
}
priority_queue a;
//最短路核心求解过程
int dijkstra(int s, int t)
{
int i, j, k, u, v, tmp;
node p;
dist[s] = 0;
a.push((heap){s,0});
for(i = 1; i
if(i!=s)
{
dist[i] = INF;
}
while(!mark[t] && !a.empty())
{
u = a.top().id;
a.pop();
if(mark[u])continue;
mark[u] = true;
for(p = g[u]->next; p; p = p->next)
{
j = dist[u] + p->w;
v = p->id;
if(j < dist[v])
{
dist[v] = j;
a.push((heap){v,dist[v]});
}
}
}
return dist[t];
}
6 算法效率评价
6.1 理论复杂度分析
再来分析一下上述算法的空间复杂度和时间复杂度。由于采用链表存储,因此实际使用的内存不会超过2×m×sizeof(data),空间复杂度为O(m)。算法需要循环查找n次,而每次查找过程需要O(1)时间,删除最小值需要O(log n)时间,整体时间复杂度为O(n*log n)。
6.2 实际效率分析
程序的效率最终体现在是否能在最短时间内得到正确结果,实际效率受到的影响因素较多,同一程序,同一时间,在同一台机器上运行同样的程序,其执行时间可能有不小差别,但是实际的运行时间体现了一般意义下的实际效率,值得研究。
编写一般的Dijkstra最短路算法,和我们上面所写的程序进行对比,在Visual Studio 2005中运行,得到如图1结果。
可见,在图的顶点数比较多的情况下,优化后的算法优势明显,原始的算法已经很难接受了。
7 结论
单源最短路问题是一个经典问题,在交通运输、生产规划、人工智能等方面有广泛的应用。通过该文章的分析以及总结,我们对单源最短路问题已经得到了令人满意的解答。将时间复杂度从O(n2)降低至O(n*log n),极大的减少了运行时间,在实际应用中可以得到更好的应用,即使在一些实时系统,我们也可以运用文章描述的优化算法,算法的实际运行时间基本上在毫秒级别,保证了时间上的高效。通过STL标准模板库,使得算法的编写也变得很容易,即使在一些特殊环境中,也能得到应用。
对问题的优化探究,往往来自于对问题的深刻认识,对工具的灵活运用,以及多学科之间的综合分析,这是我们在科学研究中应该时刻铭记的。
参考文献:
[1] Leiserson C E,Rivest R L,Stein C.算法导论(影印版)[M].2版.北京:高等教育出版社,2002:580-619.
[2] Sahni S.数据结构、算法与应用――C++语言描述[M].北京:机械工业出版社,2000:408-408.
[3] 魏宝刚,陈越,王申康.数据结构与算法分析[M].浙江:浙江大学出版社,2004:224-227.
[4] 陈媛,何波,涂晓红,等.算法与数据结构[M].北京:清华大学出版社,2005:165-168.
[5] 朱承学,李锡辉.数据结构(C/C++描述)[M].北京:中国电力出版社,2004:131-135.
[6] 陈明.数据结构实用教程[M].北京: 清华大学出版社,2004:143-144.
[7] Bondy J A,Murty U S R.图论以及应用[M].北京:科学出版社,1984.
运筹学最短路径范文6
【关键词】图论；单目标优化；旅游线路；lingo
【基金项目】2015年安徽省大学生创新训练项目：基于图论的自驾游路线的设计与实践（201510380025）.
随着经济的发展，家庭汽车的普及，人们不满足于传统的旅游方式，自驾游出行成为人们出游的重要方式.随之人们需要一个更加符合自身要求的旅游路线.因此，以人本主义为出发点，将旅游线路设计的普适性与个性化结合，设计出一种更加符合自驾游者自身条件的旅游路线，有着极大的市场需求，并且会促进整个旅游业的健康发展.
通过我们的网络调查问卷，对收集到的问卷进行分析，结果表明自驾游爱好者主要是大学生及上班的工作人员，自驾游出行时间主要集中在假期，影响自驾游出行路线的主要因素有时间（自驾游车程所耗费的时间）、费用（自驾游车程所耗费的费用）、路程、到达目的地所转折的道路节点数等.现选取6个旅游景点作为自驾游的目的地进行相关的线路优化设计.
一、模型假设
1.在自驾过程中汽车平均以60 km/h的速度行驶，行程中无其他意外突发事件，以最短路径作为行车路线.
2.每天的自驾时间和旅游时间为10小时，然后就找住宿的地方休息.
3.汽车在自驾过程中耗油为0.5元/km.（包括过桥、过路费用）.
4.旅游外出时间主要是自驾时间和旅游景点游玩时间，其他时间不计入.
5.每个景点的游玩费用固定不变，景点每天都按时间正常开放.
6.自驾游爱好者在景点的食宿费用为每个景点所在地一户人家一天的平均消费费用.
二、模型的建立与求解
把游客要游览的每个景点看作图中的一个节点，各景点之间的距离、时间、费用看作图中对应边上的权，各景点的线路网就转化成一个加权无向图G.自驾游爱好者从某一节点出发，游遍图中的每一个节点有且H有一次，最终回到出发点使得总时间、总费用或总路程最优的自驾游路线，即旅行售货员问题，旅行售货员问题是一个完全NP问题[1].对于单目标优化问题，问题可行解的优劣可以通过比较解的大小来判断优劣，从而得出问题的最优解[2].我们将以芜湖为出发地，其他地点作为自驾游的目的地.其中，将游览景点的节点分别记为vi（i=1表示在出发地芜湖，i=2，3，…，6分别代表游览景点黄山、杭州、舟山、扬州、南京），通过经纬度换算等方式计算给出以下相关的数据，分别建立了以路程最短和费用最少为目标函数的路线模型.
