带二次参数赋权多阶段网络的最短路问题研究

来源 :山西大学 | 被引量 : 0次 | 上传用户:iloveyouguoran
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
网络最短路径问题一直是计算机科学、运筹学、地理信息科学等学科的一个研究热点。目前,静态网络最短路算法已经研究得十分完善,而动态网络最短路算法的研究比较薄弱。静态算法只能处理固定网络拓扑结构和固定权值的网络最短路径问题。但是,在实际中遇到的网络大多是动态的、不确定的,即网络拓扑结构或权值可能会随时间变化,静态算法对此类动态问题不一定有效。随着计算机通信网络、移动通信网络、分布式处理和智能交通系统等诸多领域的蓬勃发展,出现了大量的非静态网络,就迫使人们不得不去深入地研究这种动态的、不确定的更为复杂的赋权网络最短路问题。因此,建立动态网络中的最短路算法已经成为当今网络优化的研究热点之一。当网络中的权值不是常数而是带参数的函数时,它便是一种动态网络,用传统的算法求解这类网络的最短路径变得十分困难,甚至无法求解。如果网络中的权值是带二次参数的函数,这样的网络称之为带二次参数赋权网络。本文采用从特殊到一般的方式循序渐进地研究了带二次参数赋权多阶段网络的最短路问题。首先研究了带特殊二次参数赋权多阶段网络的最短路问题,其次研究了带一般二次参数赋权多阶段网络的最短路问题,最后研究了带线性、二次参数混合赋权多阶段网络的最短路问题。本文采用Dijkstra算法思想和隐枚举方法,在理论分析的基础上,得到了如下主要结果:1.给出了带特殊二次参数赋权多阶段网络的最短路问题的一些隐枚举规则(3.1.3节中的引理3-1-1至引理3-1-4),并以这些规则为支撑给出了带特殊二次参数赋权多阶段网络的最短路算法(3.1.4节中的算法3-1),以及带特殊二次参数赋权多阶段网络的求临界点算法(3.1.5节中的算法3-2);2.给出了带一般二次参数赋权多阶段网络的最短路问题的一些隐枚举规则(3.2.3节中的引理3-2-1至引理3-2-4),并以这些规则为支撑给出了带一般二次参数赋权多阶段网络的最短路算法(3.2.4节中的算法3-3),以及带一般二次参数赋权多阶段网络的求临界点算法(3.2.5节中的算法3-4);3.给出了对于带线性、二次参数混合赋权多阶段网络的最短路问题的一些隐枚举规则(4.3节中的引理4-3-1至引理4-3-4),并以这些规则为支撑给出了带线性、二次参数混合赋权多阶段网络的最短路算法(4.4节中的算法4-1),以及带线性、二次参数混合赋权多阶段网络的求临界点算法(4.5节中的算法4-3)。论文还对带线性、二次参数混合赋权多阶段网络的最短路算法进行了算法复杂性分析,分析结果表明,尽管文中给出的最短路算法不是多项式的,但对于一定规模的该类网络,算法还是十分有效的。
其他文献
近年来,受互联网技术蓬勃发展的影响,完全改变原有的信息传播模式,特别是基于移动互联网的信息传播模式,促使原有的文字传播逐步丧失其市场竞争力,而图文信息或视频信息成为传播模式的主流发展方向。同时,全面分析互联网图文信息传播模式的特征能帮助相关企业建设完善的信息体系及信息路径,大大提升其核心竞争力。本文以互联网图文信息传播为切入点,分析其发展现状,进一步分析其具体传播特征,旨在为相关从业人员积累更多的
单位的带宽相对来说比较快,但是下班回家后如何再利用单位网络呢,毕竟单位一般是局域网(内网),外网很难远程控制。而借助LoVg-10va(http//www.lava-lava.com),就可以远程控制单位电脑,这样在夜里可以用公司的电脑来完成电影下载、数据备份等操作,早上还可以及时远程停止这些操作,从而不影响他人的工作。    第一步:设置被控制方    首先注册2个L0v0-Lava账号,并互加
烟草行业网络安全问题会极大程度上限制烟草行业信息化的发展程度,成为烟草行业重点关注的问题。基于此,进行烟草行业网络安全及其防范策略研究。针对烟草行业网络安全中常见问题,有针对性地提出方法策略。物理安全方面包括:来历不明的EXCEL、WORD文档以及存在风险安全提示的陌生网站;技术脆弱性方面包括:主动恶意攻击以及非故意恶意攻击;安全意识淡薄包括:烟草行业缺乏专业的计算机专业人才,烟草行业网络操作人员
我国电力系统广泛采用有载调压变压器,它起到联络电网,调节无功潮流,稳定负荷中心电压的作用,从而改善了运行条件,提高了供电质量。在变压器的运行过程,有载分接开关难免会出现故障。传统的试验方法中,因为有载分接开关与变压器的线圈绕组是连接的,试验中,要求必须直接与有载开关进行连接才能测试,无法带绕组测量,因此必须将分接开关与变压器整体分离,使它与变压器绕组脱开,再与测试设备连接,人工手动旋转切换开关进行
当前我国经济发展稳中有进,也推动了科学技术水平的长足进步,为人民群众的日常生活带来了较大的便利。智能视频监控系统便是其中的重要组成部分,通过智能视频监控系统的应用,能够有效保障枢纽机场航站楼,相关工作的顺利开展,对于航空公司的良性发展大有裨益。基于此,本文简要介绍了智能视频监控系统的组成部分,并分析了其在枢纽机场航站楼建设中的应用。
大数据语境下,摸底排队在诸多方面发生了深刻变化。本文在厘清摸底排队内涵、特征与摸底排队要素的基础上,全面阐述了摸底排队的变化与基本样态,通过实例分析,阐述了摸底排队在侦查实践中的应用与摸底排队在刑事侦查中的作用。最后指出,要充分发挥摸底排队在刑事侦查中的作用,必须加强相关基础设施和数据库建设。
在我国持续发展过程中,水利工程作为重要的民生工程,为人民群众安居乐业及各行各业发展提供了重要的保障,社会及政策越来越关注工程项目的管理与建设。在新时期水利工程管理方面,应加大对高新技术的应用力度,不断在管理工作中融入水利工程信息化管理理念,通过提高利用、传输以及收集信息化数据水平,促进水利工程建设管理的自动化、智能化发展。基于此,本文主要阐述了将信息技术应用在水利工程管理中的必要性,分析了水利施工
二硫化钼(MoS2)作为一种代表性的半导体二维原子晶体材料,具有优异的物理及电学特性,这使其在光电器件尤其是逻辑器件的应用中具有广泛的前景.总结了MoS2的表面电荷转移掺杂