导读:本文包含了动态最短路问题论文开题报告文献综述及选题提纲参考文献，主要关键词:网络阻断,最短路,多重网络,对偶算法
动态最短路问题论文文献综述
肖开明[1]（2015）在《动态多重网络最短路阻断问题研究》一文中研究指出网络阻断是一类带有博弈特点的优化决策问题,该问题与网络结构密切相关,在军事、交通运输、基础设施领域具有广泛的应用背景。经典的网络阻断问题以单层网络为研究对象,包含上下两层决策者:网络运营方与阻断方;通常建模为二层混合整数数学规划问题,以进行定量的优化决策。目前的研究仅针对单层网络阻断问题,然而实际中广泛存在的多重网络及其网间依赖关系,对与网络相关的优化问题具有显着的影响。因此,本文在单层网络最短路阻断模型的基础上,建立了动态多重网络最短路阻断模型框架,并设计了相关算法。本文研究的核心在于问题建模和算法设计两个方面,并通过仿真数据和实际案例数据对模型和算法进行验证和分析,内容如下:1)节点阻断型单层网络最短路阻断问题的建模与算法设计。通过引入节点阻断的转换约束,建立针对节点的单层网络最短路阻断模型;同时,在经典的对偶算法和本德斯分解算法的基础上,提出阻断子图分解算法及相关改进策略。此外,以研究资源投入与阻断收益的权衡为目的,建立最大化最短路-最小化阻断资源的双目标最短路阻断模型,提出序列子图分解算法,并以帕累托最优解为基础研究网络阻断问题的饱和特性,为资源投入与阻断收益的权衡和决策提供了理论分析依据。2)动态多重网络最短路阻断问题模型框架的建立与算法设计。以单层网络最短路阻断问题模型为基础,通过引入依赖函数对多重网络的网间依赖关系进行建模,将多重网络最短路阻断问题转换为单层网络最短路阻断问题。同时,以网间反馈关系为例,给出依赖函数的建模方法、逻辑约束的线性化方法,以建立存在此类网间依赖关系的多重网络的最短路阻断模型。此外,本文提出针对动态多重网络最短路阻断模型的算法:对偶算法、本德斯分解算法;以双层网络最短路阻断问题为例,通过利用多重网络的结构信息,提出基于反馈稳态阶段上界的算法改进;在保证解的最优性的前提下,该改进策略可以大幅削减由于多重网络动态失效(故障)传播而引入的逻辑约束,以提高算法效率。3)实验验证与案例分析。结合仿真网络数据与实际案例数据,对上述模型和算法进行实验分析。实验对比分析了上述算法的求解效率,同时分析网络规模、阻断资源总量、网络结构等对上述算法求解时间的影响。实验表明:提出的阻断子图分解算法和以之为基础的序列子图分解算法,大幅提高了单目标和双目标最短路阻断问题的求解效率、扩大了可求解问题的规模;基于反馈稳态阶段上界的算法改进策略大幅提升了原有算法的性能,使得双层网络最短路阻断问题的求解效率得以提高。综上,本文对单层及动态多重网络上最短路阻断问题进行了较为系统的研究,为该问题的研究提供了理论基础和建模框架,为决策者在实际动态多重网络阻断问题中的决策提供了优化模型和算法支撑。(本文来源于《国防科学技术大学》期刊2015-11-01）
葛浩[2]（2009）在《关于动态最短路问题的探讨》一文中研究指出主要研究网络优化领域中一种具有动态特征的最短路问题,给出了离散时间模型下关于时间和费用的动态最短路问题的描述,通过引入时间扩张图概念,将动态最短路问题转化为对应的静态网络中的最短路问题,讨论了两类动态最短路问题的复杂性并给出算法。(本文来源于《东莞理工学院学报》期刊2009年05期）
王丽颖[3]（2008）在《用动态规划模型求解最短路问题的研究》一文中研究指出动态规划法是求解具有多阶段的最短路径的算法,本文以动态规划理论为指导,研究了铺设管道最短路问题实例,采用顺序递推法和逆序递推法两种解决方法,并用LINGO软件编程得到结果.(本文来源于《白城师范学院学报》期刊2008年06期）
易颖华,叶祥企,杭海霞[4]（2008）在《最短路问题的一种新动态规划算法》一文中研究指出结合并行处理及顺序(逆序)递推算法的思想,对有循环不带负弧的有向图中特别指定的2个节点之间的最短路问题提出了一种新的动态规划算法,且新算法在搜索结果上与狄克斯拉(Dijkstra)标号算法相同,但因为新算法采用了双向递推的思想,因而其搜索速度明显优于Dijkstra标号算法。(本文来源于《江西科学》期刊2008年01期）
庞素超,陈实[5]（2007）在《用动态规划方法求解最短路问题》一文中研究指出用动态规划方法求最短路问题,要求所求问题具有明显的阶段.但实际中有些问题不能直接划分出阶段,无法用动态规划方法求解.因此,提出了一种求解的转化方法,将实际问题转化为标准模型,再用动态规划方法求解.应用实例表明,该方法转化过程简单,计算结果可靠.(本文来源于《大庆石油学院学报》期刊2007年03期）
林澜,闫春钢,蒋昌俊,周向东[6]（2007）在《动态网络最短路问题的复杂性与近似算法》一文中研究指出有向网络的最短路问题在交通、通信系统的最优路径计算以及多阶段决策过程的最优轨线设计等实际问题中有着重要应用.经典模型及算法解决固定弧权条件下的最短路问题,而实际中,网络往往是动态的,即弧权依赖于时间变化,例如在交通拥堵时运行时间会变长,这时经典的最短路算法不再适用.文中证明了动态网络的最短路问题是NP-困难的;给出了最短路稳定性的充要条件,并在此基础上提出一种基于稳定区间的近似算法,通过模拟实验验证了该算法的有效性.(本文来源于《计算机学报》期刊2007年04期）
周迎[7]（2003）在《破圈法解动态规划中的最短路问题》一文中研究指出运筹学动态规划多阶段决策中的最短路问题有多种解法。把求最小树的破圈法扩展用于有向图中解最短路问题,较之常用的Dijkstra方法更直现快捷。(本文来源于《西昌农业高等专科学校学报》期刊2003年03期）
陈盛双,胡晓林,许万洪,黄樟灿[8]（2001）在《基于演化计算的动态最短路问题》一文中研究指出提出了一类基于时间变权的动态最短路问题 ,给出了其详细的数学描述 ,扩展了图论中关于最短路问题的概念 ;并设计了适合该问题的编码方式和杂交、变异方式 ,给出了基于演化计算的求解框架 ,其主要特点是染色体变长 ,且首尾基因固定 .最后针对一个简单实例进行了仿真和分析 ,研究结果表明 ,该算法可以获得良好的效果 .(本文来源于《武汉大学学报(理学版)》期刊2001年03期）
郭嵩山,陈明睿[9]（2000）在《国际大学生程序设计竞赛试题与算法分析(叁)──动态规划及其应用──最短路问题》一文中研究指出动态规划实际上是研究一类最优化问题的方法，在经济、工程技术、企业管理、工农业生产及军事等领域中都有广泛的应用。近年来，在ＡＣＭ／ＩＣＰＣ中，使用动态规划（或部分应用动态规划思维）求解的题不仅常见，而且形式也多种多样。而在与此相近的各类信息学竞赛中，应用动(本文来源于《现代计算机》期刊2000年04期）
庞素超[10]（1997）在《经过转化可用动态规划方法求解最短路问题》一文中研究指出最短路问题在实际中应用得非常广泛,用动态规划方法求解此类问题时,要求所求问题具有明显的阶段,但实际工作中的某些问题不能直接划分出阶段,若将此类问题经过转化可变成定阶段的能用动态规划方法求解的“标准模型”。(本文来源于《牡丹江师范学院学报(自然科学版)》期刊1997年02期）
动态最短路问题论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
主要研究网络优化领域中一种具有动态特征的最短路问题,给出了离散时间模型下关于时间和费用的动态最短路问题的描述,通过引入时间扩张图概念,将动态最短路问题转化为对应的静态网络中的最短路问题,讨论了两类动态最短路问题的复杂性并给出算法。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
动态最短路问题论文参考文献
[1].肖开明.动态多重网络最短路阻断问题研究[D].国防科学技术大学.2015
[2].葛浩.关于动态最短路问题的探讨[J].东莞理工学院学报.2009
[3].王丽颖.用动态规划模型求解最短路问题的研究[J].白城师范学院学报.2008
[4].易颖华,叶祥企,杭海霞.最短路问题的一种新动态规划算法[J].江西科学.2008
[5].庞素超,陈实.用动态规划方法求解最短路问题[J].大庆石油学院学报.2007
[6].林澜,闫春钢,蒋昌俊,周向东.动态网络最短路问题的复杂性与近似算法[J].计算机学报.2007
[7].周迎.破圈法解动态规划中的最短路问题[J].西昌农业高等专科学校学报.2003
[8].陈盛双,胡晓林,许万洪,黄樟灿.基于演化计算的动态最短路问题[J].武汉大学学报(理学版).2001
[9].郭嵩山,陈明睿.国际大学生程序设计竞赛试题与算法分析(叁)──动态规划及其应用──最短路问题[J].现代计算机.2000
[10].庞素超.经过转化可用动态规划方法求解最短路问题[J].牡丹江师范学院学报(自然科学版).1997