一、网络最短路径的动态算法（论文文献综述）
张小芳,冯慧芳[1]（2021）在《基于轨迹大数据的动态最优路径规划》文中认为以轨迹大数据为基础,结合城市交通状态与用户个性化需求,提出一种基于改进Viterbi算法的动态最优路径规划算法。首先融合交通状态和真实路网拓扑结构,构建基于有向多重加权复杂网络的交通网络模型。采用基于层次分析法和熵权法相结合的综合赋权法对交通网络模型的多权重属性进行权重分配,得到新的有向加权复杂网络模型。进一步采用改进的Viterbi算法求解最优路径。最后,以兰州市为例,对最优路径规划进行分析,并将该算法与静态规划方法进行比较,验证城市最优路径规划算法的有效性与实时性。实验结果表明,结合城市交通状态与用户偏向的路径规划更加科学合理,能够为兰州市驾车出行、交通管理部门决策提供决策支持和参考。
孙宁,吴伟豪,赵风财,肖广兵[2]（2022）在《基于增强型Dijkstra算法的无信号灯交叉路口智能车辆调度研究》文中研究说明针对车辆在通过无信号灯交叉路口时存在等待时间长、通行效率低等问题,提出了一种基于增强型Dijkstra算法的优化调度方案。以智能车辆为研究对象,在将交叉路口网格化的基础上,综合考虑车辆在每个网格中的方向权值、安全权值和优先级权值,制定了动态网格权值赋值原则,进而搜索通行时间最短的路径。相比Dijkstra算法,提出的增强型Dijkstra算法实现了智能车辆在动态网格权值下最短路径的全局搜索,可以根据实际车辆环境灵活调整每个车辆的行驶轨迹。仿真结果表明,增强型Dijkstra算法不仅能够保持较低的冲突次数,还能有效减少车辆总通行时间。在100 m×100 m的双向六车道的交叉路口环境下,车辆平均停车延误减少1.5 s,冲突率下降13%。
常盟盟,袁磊,丁治明,李路通[3]（2021）在《交通路况感知下的自适应动态路径规划方法》文中指出针对传统路径规划算法在动态网络中的时效性和可用性不足,本文提出一种适用于时变路网环境下的自适应动态路径规划方法。通过引入动态网络流式图划分思想,构建一种分层路网的状态树索引,有效降低了动态路网中路径查找的计算代价,并扩展了传统路径规划算法在动态路网中的普适性。在此基础上,将区域路况的时空变化信息融合到索引树中,进一步提出一种基于时空层次网络的路径映射方法。并按照访问节点的距离逐步收缩最小包含区域来减少路径查找视野,将路径查找过程转化为在层次图中的小范围寻址。为适应路网动态变化特征,路径映射采用多路并行的双向探测策略,使得路径搜索迅速收敛于一个最优解,在动态路况变化和旅行代价之间寻求平衡。最后,结合北京市实时交通路网数据集进行实验评估,在查询性能和自适应调整方面验证了所提出方法的有效性。
闫江毓[4]（2021）在《无线传感网络路由和定位技术研究》文中指出无线传感网络在国民经济和日常生活中得到深入广泛的应用,承担着数据采集、状态测量、设备定位等众多功能。无线传感网络由大量节点通过无线自组织方式连接而成,各个节点独立采集数据,按照设定的路由协议传输数据到中央服务器。针对无线传感网络在不同领域的应用特点,发展出多种路由协议。这些路由协议在节点能耗、数据延迟、拥塞控制等方面性能各有侧重。基于地理位置的路由协议是其中比较重要的一种,其在路由决策时主要利用节点的地理位置信息,因而能有效控制节点能耗和快速应对网络拓扑变化。基于地理位置的路由协议的基础是节点位置信息,而基于无线信号指纹的定位算法具有成本低,定位精度高的特点,适用于无线传感网络中的节点定位。本文针对无线传感网络中拥塞控制、网络能效、节点定位三个方面开展研究,并提出了相应的解决方案。本文的主要工作内容如下:无线传感网络中监控区域的异常事件产生的突发数据流会引发网络拥塞,导致数据包延迟增加、节点能耗增加,严重影响网络的服务质量。针对能量受限传感网络的拥塞问题,提出了一种基于引力竞争的拥塞控制路由算法。根据邻居节点间的距离位置关系和节点缓存状态定义传输引力与能量引力。传输引力从数据包到达率、缓存队列长度及数据包处理能力三方面描述节点的拥塞状态。能量引力采用物理距离估算节点剩余能量,并考虑下游节点的能量分布。根据物理学中功的原理,引入引力竞争强度表示位移,节点引力和引力竞争强度相乘为功,选择功最大的节点为下一跳节点。针对具备能量补充功能的无线传感网络的拥塞问题,提出了一种基于虚拟力的流量感知路由算法。算法依据源节点、邻居节点以及目的节点之间的距离关系定义虚拟内力,以构建数据包的最长单跳距离。定义虚拟外力以感知前向区域数据流量,沿着空闲或低负载节点构建路由。虚拟外力和虚拟内力融合成虚拟合力,从而驱动数据包避开拥塞区域,并尽快传输到目的节点。对于能量受限的传感器节点,提高能效能够延长无线传感网络生命周期,提升网络可用性。基于地理位置的路由可以根据节点距离选择最佳传输功耗,由此提出一种多参数融合能效路由算法。算法定义了五个路由评估参数,包括节点剩余能量、有效转发率、单跳传输比、缓存队列指数和能量均衡度。每个参数从不同角度反映网络及节点的状态。引入可信度系数评估各个参数在路由决策中的可信程度,参数贡献度反映各个参数之间的重要性差异。对于网络中的随机干扰引起的距离测算误差引入模糊贡献度表示。参数贡献度和模糊贡献度合并为融合贡献度,选择最大融合贡献度的节点作为下一跳节点。地理位置路由决策需要节点位置信息,此外在物流和医疗等领域的无线传感网络应用中也需要对节点进行精确定位。诸多定位算法中,免测距的指纹定位算法对节点功能要求低、定位时间短、精度高、部署成本低,近些年获得学术和产业界的很大关注。指纹定位包括两个阶段,离线测量阶段建立定位区域无线信号指纹与位置坐标关系数据库;在线查询阶段根据特定算法估计未知节点坐标。本文提出了两种指纹定位算法,分别针对单区域和多区域节点定位。针对单区域节点定位,提出一种基于高斯分布的指纹定位算法。首先用利用模糊方法融合未知节点指纹与数据库指纹形成模糊决策矩阵。算法以锚节点数量为维度建立多维高斯分布模型,利用马氏距离估算未知节点偏差,选择偏差最小的K个参考节点利用质心法估计未知节点坐标。针对多区域复杂环境定位,依据知识决策理论,提出一种基于模糊决策的指纹定位算法。将定位过程分为三个阶段:知识积累阶段,采用模糊融合形成定位决策矩阵;知识融合阶段,应用拉格朗日优化算法求得不同区域中锚节点的隶属度权重;知识扩展阶段执行定位决策,计算参考点匹配度,将匹配度最高的参考点坐标作为未知节点的位置估算值。本文工作围绕无线传感网络的拥塞控制、能效优化和节点定位展开,以节点间物理距离为出发点,有针对性地提出了路由算法和指纹定位算法,并通过理论分析和软件仿真验证了所提算法的有效性。
范若乔[5]（2021）在《基于城市道路车流量预测的动态路径规划》文中研究指明随着城市化进程的不断深入,城市交通拥堵问题所带来的影响日益明显,交通流预测已成为城市智能交通系统发展的关键。利用大数据和人工智能算法实现对城市路网交通流的预测,可以为出行者推荐最优出行路线、辅助交管部门提前进行交通管制,对智慧城市建设具有重要意义。本文主要研究城市交通流预测和最优路径规划问题,以时空数据为基础,利用深度学习算法实现时间特征与空间特征叠加的交通流预测,并将预测结果用于城市动态路径规划,得到基于预测的最优行驶路径。本文主要工作如下:1)提出一种基于时空融合卷积网络的城市交通流预测模型。该模型根据城市路网构造含有局部道路关系的空间邻居子图和全局道路关系的相似邻居子图,经图注意网络分别对其邻接矩阵进行动态加权得到两种动态道路权重矩阵,然后利用图卷积神经网络提取这两种动态矩阵的空间特征。为提取交通流数据的时间特征,模型利用加入注意力机制的时间卷积网络提取数据中的多重潜在时间信息,得到交通流数据的局部和远程时间依赖关系。最后利用时空融合层将时间特征与空间特征进行串联聚合得到高维时空特征,并通过线性层实现多步预测。实验结果表明,与当前主流预测模型相比,基于时空融合卷积网络的城市交通流预测模型具有更准确的预测性能。2)为提高时空融合卷积网络的性能,提出一种基于粒子群的时空融合卷积网络参数优化算法。该算法通过改变网络参数取值优化时空融合卷积网络的性能,找到使网络性能达到最优的参数值,提高其预测准确度。实验结果表明,优化后的时空融合卷积网络比优化前的预测误差更小,且训练时收敛速度更快。3)提出一种基于路网状态信息的动态路径规划算法。该算法将基于时空融合卷积网络的城市交通流预测模型应用于城市动态路径规划中,以最短出行时间为目标,以预测得到的道路综合行驶时间为其时空拥挤系数,使用以行驶角度为限定的优化A*算法实现车辆行驶过程中的动态路径规划,以得到全局最优行驶路径。该算法根据当前车辆所处的位置预测进入下一路口前的城市路网状态信息,使用通过历史数据分析所得的动态路网状态信息的网络模型判断此时是否需要更新道路时空拥挤系数矩阵,如果更新则重新规划路线。实验结果表明,与当前主流路径规划算法相比,基于路网状态信息的动态路径规划算法能得到行驶时间更短的路径,且算法运行效率更高。
曹浩彤[6]（2020）在《网络虚拟化环境下虚拟网络映射算法研究》文中提出在可预见的未来,各种各样新颖的网络服务和应用将会兴起。传统的互联网因为其自身的僵化问题而无法满足这些新兴网络服务的需求。为了有效解决互联网僵化问题,学术界和工业界引进了网络虚拟化技术。在网络虚拟化技术研究中,有一个重要的技术问题需要解决,即如何将多个异构虚拟网络服务高效地映射到整个底层物理网络中。这个问题在学术界被称为虚拟网络映射问题。因为虚拟网络映射存在多个维度的资源约束,所以虚拟网络映射问题被证明是一个NP难问题。本文首先对网络虚拟化技术和虚拟网络映射问题及算法进行了综述,包括网络虚拟化技术的起源、相关技术和商业模型等。紧接着,本文对虚拟网络映射问题从底层物理网络、虚拟网络需求、映射函数、映射目标、性能指标等方面进行了详细建模。在对国内外现有的虚拟网络映射算法进行了简要综述之后,本文将现有的虚拟网络映射算法依据优化策略的不同分为三类:精确解算法类、启发式算法类和元启发算法类。本文讨论了现有的精确解算法和元启发虚拟网络映射算法的优势和劣势,找到其存在的问题和研究瓶颈。因为精确解算法和元启发算法存在高计算复杂度的缺陷,而启发式算法能够在多项式时间内完成虚拟网络映射方案的计算,所以,启发式算法有很大的研究价值和应用价值。此外,未来的虚拟网络服务需求是不可预见的、动态的和多变的。因此,每个虚拟网络服务需求需要在尽可能短的时间内完成部署和实现。基于上述研究背景,本文重点研究启发式虚拟网络映射算法。根据不同的映射目标,本文提出了四个启发式算法。本文提出的四个启发式算法的创新点集中在如下四个方面:首先,针对现有的启发式虚拟网络映射算法只考虑单一节点拓扑属性和局部网络资源而导致低虚拟网络映射成功率的缺陷,本文提出了一种基于多网络拓扑属性和全局网络资源的启发式算法。本启发式算法考虑的拓扑属性有:节点度、节点链路强度、节点间距离、节点亲密度、链路强度和链路干扰。本启发式算法考虑的全局网络资源有:节点容量和链路带宽。通过量化这些拓扑属性和资源并采用谷歌网页排序的方法,本启发式算法能够求出稳定的节点排序值。现有的虚拟网络映射研究表明节点排序值越高,该节点的映射能力就越强。因此,本文提出的启发式算法能够更好地选出映射能力强的节点并协调虚拟网络映射。仿真结果表明本文提出的启发式算法比之前的启发式算法提高了虚拟网络映射的映射成功率、收益支出比、节点容量利用率和链路带宽利用率。其次,针对大部分启发式算法只注重提高虚拟网络映射成功率而忽略降低底层物理网络的能耗,以及学术界提出的节能算法只考虑了在局部单一底层网络下完成虚拟网络映射的缺陷,本文提出了一种能够在多个分布式底层物理网络完成虚拟网络映射并节约底层物理网络能耗的启发式算法。通过对底层物理网络元件和不同地域的电价进行分析建模,本文首先建立了合理的虚拟网络映射能耗模型。之后,本文提出了多底层物理网络的节能算法。本文提出的多底层网络节能算法不仅量化了网络拓扑属性和能耗相关属性,也采用了网络元件整合的方法。本节能算法旨在确保虚拟网络映射成功率的同时,能够最小化虚拟网络映射的能耗。仿真结果表明本文提出的节能算法与现有的节能算法相比,不仅能够在多分布底层物理网络下完成虚拟网络映射,还能够节约虚拟网络映射的能耗。紧接着,针对现有启发式虚拟网络映射算法都是静态,只满足资源需求且无法灵活调整初始映射结果,而导致不能满足虚拟网络Qo S性能指标的缺陷,本文提出了一种能够动态地调整已映射虚拟网络元件的位置和优化初始映射结果的虚拟网络映射算法。本动态算法由两个子算法组成:多拓扑属性和全局网络资源子算法和动态网络元件调整子算法。当完成某一个虚拟网络的初步映射,本算法将会检查该虚拟网络的映射结果。如果该虚拟网络某一个元件的Qo S指标没有达到要求,本算法将会执行动态调整直至该虚拟网络所有的资源和Qo S需求都被满足。仿真结果表明本动态调整虚拟网络映射算法与现有的动态不可调整启发式算法相比,既提高了长期虚拟网络映射成功率和底层物理网络资源利用率,又满足了虚拟网络服务的Qo S性能指标。最后,如何对不同拓扑结构和资源需求的虚拟网络做出个性化且高效的映射是一个值得研究的问题。目前存在的虚拟网络映射算法采用的都是“一对所有”模式来映射所有虚拟网络服务需求。这样的映射算法将会导致低效网络映射质量和低底层物理网络资源利用率。本文创新性地提出了一种面向个性化虚拟网络的启发式映射算法。当任意用户提出一个虚拟网络服务需求,本算法首先采用分类子算法对该虚拟网络需求进行分类。分类子算法能够将该虚拟网络分为时延优先类或者资源需求优先类或者一般类。在完成该虚拟网络的分类之后,本算法将调用合适的映射子算法对该虚拟网络需求进行高效的映射和资源分配。仿真结果表明本文提出的面向个性化虚拟网络映射算法与现有的启发式算法相比,既提高了长期虚拟网络映射成功率,又提高了底层物理网络资源利用率。
张焘[7]（2020）在《时变网络流分析与调度方法研究》文中提出为了支撑爆炸式增长的终端用户以及满足日益增长的业务需求,信息网络正沿着动态化、差异化、多样化以及异构融合化等方向不断演变,网络的时变特性尤为凸显。例如,拓扑变化导致中低轨卫星网络、深空探测网络、社交网络、车联网、物联网等网络的拓扑具有时变特征,网络承载业务变化导致地面互联网、数据中心网络的节点与链路可用资源动态变化。目前,典型信息网络如移动互联网与天地一体化信息网络均为时变网络。然而,时变网络的建模、分析与设计方法尚不完善。由于时变多维资源的精准表征较为困难,现有组网技术多将时变网络看作分时段的静态网络,忽略了不同时段网络资源之间的关联性、忽略了多维网络资源的关联关系与时间属性,造成时变网络资源利用率低、业务服务质量（Qo S,Quality of Service）难保障。因此,如何精准表征时变网络多维资源的时变性与关联性、如何设计时变网络高效的性能分析方法、如何构建时变网络多维资源的高效调度方法是提升网络资源利用率和保障多种类业务需求的关键。本文重点研究时变网络流分析与调度方法,通过拓展时变图理论,构建低复杂度、高精准度的时变网络图模型,精准刻画了时变网络多维资源及其制约关系,解决时变网络的资源表征问题;提出基于时变图的网络最大流分析方法及Qo S保障路由算法,部分解决了时变网络容量分析问题,并关联利用时变多维资源提升业务的服务质量保障能力。本文的主要研究内容及成果如下:1.针对时变网络多维资源相互制约导致的网络模型难构建以及网络最大流难求解等问题,提出了低存储复杂度的时变网络图模型―存储时间聚合图,并提出基于存储时间聚合图的时变网络单源单汇最大流分析方法。首先,针对现有时变网络图模型占用的存储资源高、表征精度低的问题,提出了低存储复杂度的时变网络图模型-存储时间聚合图,通过将多时段网络拓扑及链路资源聚合表征,降低了时变图的存储复杂度;构建节点的存储资源转移序列,刻画了节点邻接链路时序制约关系,精准表征了节点存储资源与邻接链路资源的关联性;定义了存储时间聚合图中时变路径、路径可行流、残余网络等概念,为时变网络流计算与分析提供了理论基础。其次,针对时变网络端到端最大流算法中路径选择顺序导致网络流差异化的问题,提出基于存储时间聚合图的时变网络最大流算法,通过设计存储转移序列的转移规则,避免了路径选择顺序对网络最大流的影响,通过不断寻找与修正时变网络的可行路径,求解时变网络最大流。通过理论分析,论证了存储时间聚合图的低存储复杂度特征以及时变网络最大流算法分析方法的高效性。2.针对时变网络因资源时变、多源流耦合导致网络二源二汇最大流难求解问题,提出基于存储时间聚合图的时变网络二源二汇最大流高效求解算法。首先,利用存储时间聚合图模型对多源多汇时变网络的时空多维资源进行建模。而后,针对时变网络中二源流耦合问题,提出时变二源流解耦方法,通过分析二源流在节点与链路的耦合关系,构建对偶流（和流与差流）及时间相关的流约束,将耦合的二源流问题转化为两个独立的单源单汇和流图与差流图求解问题。在此基础上,提出基于存储时间聚合图的动态联合二源流算法,通过联合求解和流图与差流图的最大流,得到二源二汇的网络最大流。仿真结果表明,所提算法可以有效求解时变网络二源二汇最大流,通过关联利用时变网络的存储资源与传输资源,提升了链路资源利用率。3.针对时变网络多维资源利用率低、资源与任务需求难匹配问题,提出基于存储时间聚合图的时变网络Qo S保障路由算法,实现时变网络序列任务的按需调度及多维资源的高效利用。首先,针对卫星网络中多观测任务传输需求,构建基于存储时间聚合图的任务需求表征模型,实现了网络多维资源与任务传输需求的联合表征。特别地,在存储时间聚合图模型中增加任务Qo S需求的表征,即增加任务源节点、服务保障汇节点、任务输入链路及服务保障链路,表征任务量大小、传输开始时刻与终止时刻,准确刻画任务Qo S需求与时变网络拓扑、链路可用时段、节点缓存之间的相互制约关系。其次,利用任务模型将序列任务流Qo S保障问题转化为时变图的单源单汇最大流问题。在此基础上,提出基于存储时间聚合图的Qo S保障多路径路由算法,通过联合利用时变最短路径搜索策略、节点缓存限制以及存储转移序列的计算规则,为每个任务构建出多条可行的路径。同时,在满足任务最大传输时延的约束下,获得最优多路传输方案,高效利用时变网络多维资源保障多任务的传输需求。仿真结果表明,所提算法可以有效提升任务完成率及时变多维资源的利用率。
杨泽宽[8]（2020）在《Top-k图中介度增量式计算方法研究》文中研究说明节点的中介度（Betweenness Centrality）是度量节点在复杂网络中重要程度的一种重要指标;计算节点中介度在社交网络分析、交通网络治理、网络安全管理等广泛应用中起着关键性作用。传统节点中介度计算方法大多数仅关注小规模和静态图,然而在实际应用中网络规模巨大且具有动态特征,因此如何在这样的网络上计算中介度受到了研究界的关注。本文研究动态图中介度和Top-k节点中介度的计算方法,包含针对动态图的节点中介度增量计算方法、针对静态图的Top-k节点近似中介度计算方法,以及针对动态图Top-k节点近似中介度计算方法。论文主要研究的内容如下:（1）动态图中节点中介度计算的增量式算法。为精确计算动态图中各节点中介度,基于经典的针对静态图的Brandes算法,提出了一种增量式算法。该算法利用增量式单源最短路径计算技术,维护中间结果,快速计算发生改变的中介度。在Email-Eu-core、Facebook和bitcoin-alpha等数据集上的实验结果验证了所提出算法的高效性;相比其他算法,所提出算法速度提升10倍左右;在不同稀疏度和不同规模的图上,所提出算法的速度比传统静态算法快2倍以上。（2）静态图中Top-k节点近似中介度获取算法。为计算静态网络中Top-k节点近似中介度,本文采用抽样自适应技术,提出了一种近似中介度计算方法。该算法将原有的单向计算枢轴的过程分为双向前后轴同时计算,减少抽样过程某些节点被高估的情况,通过保证极少部分的节点近似中介度的准确性,快速获得以近似中介度排序前Top-k节点。在 CollegeMsg、p2p-Gnutella05/06、Soc-sign-bitcoinapla 和 Wiki-Vote 五个数据集上的实验结果表明,在保证前Top-k节点近似中介度的情况下,所提出算法和其他算法相比,运算速度平均提高2.4倍以上,排序几何平均值提高数10倍以上。（3）动态图中Top-k节点近似中介度获取算法。为计算动态网络中Top-k节点近似中介度,本文采用抽样自适应技术,提出了一种在动态网络上维护Top-k节点近似中介度的算法。该算法通过维护抽样结果、实时更新前后枢轴数量和排序近似中介度,动态更新 Top-k 节点。在 CollegeMsg、p2p-Gnutella05/06、Soc-sign-bitcoinapla 和 Wiki-Vote五个数据集中实验结果表明,所提出相比其他算法运算速度平均提高10倍以上。
钟颖[9]（2020）在《基于在线地图速度数据的城市动态最短路径选择算法研究》文中进行了进一步梳理城市动态交通诱导是缓解交通拥堵的有效措施之一,出行者可根据诱导信息确定合适的出行路径、出行时间,避免不必要的出行延误。动态路径诱导的核心为动态最短路径选择,现有研究中,受地区经济发展的影响,部分地区路网速度数据完整性不足,导致路径规划结果与实际存在差异;在动态最短路径选择过程中,未充分考虑到道路交通状态的时变性。针对以上问题,本文以在线地图速度数据为基础,基于在线地图速度数据构建了GCN-LSTM-BP路段短时交通速度预测模型,基于速度预测信息对城市动态行程时间最短路径选择算法进行了研究。首先,对论文研究所需数据的获取方式进行了阐述。考虑到采用传统数据采集方式获取大规模路网速度数据存在一定局限性,本文采用在线地图速度数据替代传统速度数据,通过调用百度、高德等在线地图服务平台提供的API,获取在线地图中路网各交叉口经纬度坐标,根据相邻交叉口经纬度坐标,批量爬取不同时段路段里程及行程时间,计算路段行程速度,实现对路网速度数据的采集。其次,基于获取的在线地图速度数据构建了路段短时交通速度预测模型。从道路交通速度时空相关性出发,基于GCN网络构建了道路交通速度空间依赖关系挖掘模型,基于LSTM网络构建了道路交通速度时间依赖关系挖掘模型,采用BP神经网络对经GCN网络与LSTM网络处理后的百度地图路段速度数据以及高德地图路段速度数据进行融合,构建了基于GCN-LSTM-BP网络的路段短时交通速度预测模型,实现了对路段速度的预测。实验结果表明,相比于仅考虑速度时间特征的模型,本文提出的同时考虑时空特征的预测模型具备更好的预测效果。最后,基于速度预测信息构建了城市动态行程时间最短路径选择模型,并改进Dijkstra算法对模型进行了求解。考虑到传统Dijkstra算法在计算起讫点间最短路径时易将冗余节点纳入搜索范围,增加算法时间复杂度,本文提出了考虑时变矩形区域限制的Dijkstra算法,根据不同出发时刻起讫点间行程时间最短路径长度与欧式距离的关系,对Dijkstra算法搜索区域加以限制,以此改进Dijkstra算法,减少算法搜索时间,提升算法运行效率。根据实际路网及路网速度预测值,分别采用传统Dijkstra算法以及改进后Dijkstra算法对路网中一定数量OD对的动态行程时间最短路径进行了选择,进一步验证了算法的有效性及可靠性。
郭阳[10]（2019）在《动态复杂网络的最短路径研究》文中研究指明随着信息技术的发展,人类社会已经逐步进入到复杂网络时代,现实中的各种人际关系、道路交通、互联通信等网络都可以抽象成为复杂网络,而随着复杂网络研究的逐步深入,大量的网络特性被逐步发现,而与这些网络特性相关问题的分析和研究很多都与网络的最短路径有关,例如节点的介数、网络的平均半径、网络的信息传播、城市道路的导航、疾病的传播、人际关系之间的影响等等问题都是与网络的最短路径息息相关的。复杂网络的最短路径研究目前主要针对基于静态网络和基于动态网络2个方面进行求解,基于静态网络的最短路径研究已经具有很多经典算法,如Dijkstra算法、Floyd-Warshall算法、Bellman-Ford算法等,虽然可以准确的求得网络的最短路径,但时间复杂度高,并不适用于规模巨大的复杂网络的最短路径的求解,更不能利用其对复杂网络的特性如介数中心性、接近中心性等以最短路径为基础的网络特性进行求解。随后衍生出了一系列适合大规模复杂网络最短路径的求解方法,如限制区域搜索方法、目标引导方法、层次划分方法、基于局部区域中心点等方法对大规模复杂网络进行简化并近似求解最短路径,在基于静态网络的最短路径求解方面取得的较好的研究成果。而在现实世界中,随着网络的规模日益增大,复杂网络越来越体现出动态性、随机性等特性,为了更好地解决动态复杂网络的最短路径求解及与其相关的网络特性求解,近年来涌现出一系列的近似求解算法。具有代表性的如动态最短路径树算法、分布式算法、基于图索引结构算法、启发式算法、改进的A*算法等,但是这些算法并没有完全考虑到复杂网络的自身结构特性,计算复杂度较高。本文在已有算法的基础上,提出了改进的动态复杂网络最短路径近似算法,结合节点的度和聚集系数,重新定义了局部区域中心点的度量方法,以便更准确的获取到局部区域中心点。同时,提出了区域的中继节点概念,可以对网络动态变化中的划分区域进行有效的分裂或者融合,减少了网络局部动态变化对整体变化的影响,加速了最短路径的近似求解过程。本文通过生成不同规模的模拟网络,对提出的算法进行了实验和分析,通过对比本文提出的最短路径近似求解方法与改进前的近似求解方法,可知本文提出的方法准确程度更高;同时,通过与具有代表性的动态复杂网络最短路径近似算法的实验对比,可知本文提出的方法计算复杂度较低,同时可以取得较好的最短路径近似结果。
二、网络最短路径的动态算法（论文开题报告）
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
本文主要提出一款精简64位RISC处理器存储管理单元结构并详细分析其设计过程。在该MMU结构中,TLB采用叁个分离的TLB,TLB采用基于内容查找的相联存储器并行查找,支持粗粒度为64KB和细粒度为4KB两种页面大小,采用多级分层页表结构映射地址空间,并详细论述了四级页表转换过程,TLB结构组织等。该MMU结构将作为该处理器存储系统实现的一个重要组成部分。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
三、网络最短路径的动态算法（论文提纲范文）
（1）基于轨迹大数据的动态最优路径规划（论文提纲范文）
| 0 引言 |
| 1 构建基于有向多重加权复杂网络的交通网络模型 |
| 1.1 构建有向多重加权复杂网络 |
| 1.2 交通网络模型多重权重属性选择 |
| 1.3 基于综合赋权法的权重分配 |
| 1.3.1 基于层次分析法的主观赋权法 |
| 1.3.2 基于信息熵的客观赋权法 |
| 1.3.3 确定综合权重分配 |
| 1.4 确定路阻函数 |
| 2 基于改进Viterbi算法的最优路径规划 |
| 3 研究区域及数据集 |
| 4 实验及结果分析 |
| 5 结束语 |
（2）基于增强型Dijkstra算法的无信号灯交叉路口智能车辆调度研究（论文提纲范文）
| 0 引言 |
| 1 系统模型 |
| 2 Dijkstra算法 |
| 3 动态赋值的增强型Dijkstra算法 |
| 3.1 调度场景的建立 |
| 3.2 动态网格权值赋值原则 |
| 3.2.1 方向权值赋值原则 |
| 3.2.2 安全权值赋值原则 |
| 3.2.3 优先级权值赋值原则 |
| 3.3 增强型Dijkstra算法 |
| 4 仿真分析 |
| 4.1 仿真场景设置 |
| 4.2 调度性能分析 |
| 5 结束语 |
（3）交通路况感知下的自适应动态路径规划方法（论文提纲范文）
| 0 引言 |
| 1 相关工作 |
| 2 理论基础 |
| 2.1 动态路网下的路径规划 |
| 2.2 双向路径搜索2-Hop Cover |
| 3 基于路网层次划分的自适应动态路径规划算法 |
| 3.1 动态路网层次划分 |
| 3.2 双向扩散路径查找方法 |
| 3.3 多路并行的双向路径探测算法 |
| 4 实验结果与分析 |
| 5 结论 |
（4）无线传感网络路由和定位技术研究（论文提纲范文）
| 摘要 |
| ABSTRACT |
| 第1章 绪论 |
| 1.1 研究背景及意义 |
| 1.2 无线传感网络路由研究现状 |
| 1.2.1 无线传感网络路由特点 |
| 1.2.2 WSN拥塞控制研究现状 |
| 1.2.3 WSN能效路由研究现状 |
| 1.2.4 WSN地理位置路由研究现状 |
| 1.3 无线传感网络节点定位研究现状 |
| 1.3.1 无线传感网络节点定位 |
| 1.3.2 WSN指纹定位研究现状 |
| 1.4 本文的主要研究内容及贡献 |
| 1.5 本文的组织结构 |
| 第2章 基于地理位置的WSN拥塞控制路由 |
| 2.1 引言 |
| 2.2 基于引力竞争的拥塞控制路由 |
| 2.2.1 系统模型 |
| 2.2.2 节点的引力场描述 |
| 2.2.3 拥塞控制路由策略 |
| 2.2.4 仿真结果与分析 |
| 2.3 基于虚拟力的流量感知路由 |
| 2.3.1 系统模型 |
| 2.3.2 虚拟力流量感知路由 |
| 2.3.3 仿真结果与分析 |
| 2.4 本章小结 |
| 第3章 基于地理位置的WSN能效路由 |
| 3.1 引言 |
| 3.2 系统模型 |
| 3.3 路由评价参数 |
| 3.3.1 能量均衡度 |
| 3.3.2 单跳传输比 |
| 3.3.3 有效转发率 |
| 3.3.4 缓存队列指数 |
| 3.3.5 剩余能量因子 |
| 3.4 基于多参数融合的能效路由算法 |
| 3.4.1 路由决策过程 |
| 3.4.2 路由选择策略 |
| 3.5 仿真结果与分析 |
| 3.5.1 调整因子的影响 |
| 3.5.2 算法对比分析 |
| 3.6 本章小结 |
| 第4章 基于高斯分布的单区域节点定位 |
| 4.1 引言 |
| 4.2 定位算法基本概念 |
| 4.2.1 基本术语 |
| 4.2.2 信号传播模型 |
| 4.3 构建指纹数据库 |
| 4.3.1 指纹数据预处理 |
| 4.3.2 RSS模糊融合与分析 |
| 4.4 多维高斯分布定位算法 |
| 4.4.1 多维高斯分布模型 |
| 4.4.2 理想点与参考节点的距离偏差 |
| 4.4.3 未知节点坐标估计 |
| 4.5 仿真结果与分析 |
| 4.5.1 定位精度评价 |
| 4.5.2 仿真数据性能分析 |
| 4.5.3 真实数据集测试 |
| 4.6 本章小结 |
| 第5章 基于模糊决策的多区域节点定位 |
| 5.1 引言 |
| 5.2 知识决策理论 |
| 5.3 模糊决策定位算法 |
| 5.3.1 知识积累 |
| 5.3.2 知识融合 |
| 5.3.3 知识扩展 |
| 5.4 仿真结果与分析 |
| 5.4.1 参考节点间隔 |
| 5.4.2 锚节点比例 |
| 5.4.3 噪声标准差 |
| 5.5 本章小结 |
| 第6章 结论与展望 |
| 6.1 论文工作总结 |
| 6.2 今后工作展望 |
| 参考文献 |
| 攻读博士学位期间发表的论文及其它成果 |
| 攻读博士学位期间参加的科研工作 |
| 致谢 |
| 作者简介 |
（5）基于城市道路车流量预测的动态路径规划（论文提纲范文）
| 摘要 |
| ABSTRACT |
| 第一章 绪论 |
| 1.1 研究背景与意义 |
| 1.1.1 研究背景 |
| 1.1.2 研究意义 |
| 1.2 国内外研究现状 |
| 1.2.1 交通流预测研究现状 |
| 1.2.2 城市道路路径规划研究现状 |
| 1.2.3 现有研究存在的问题 |
| 1.3 研究内容与创新点 |
| 1.4 论文组织结构 |
| 第二章 相关技术与理论基础 |
| 2.1 交通流相关理论基础 |
| 2.2 交通流预测模型 |
| 2.2.1 时间序列预测模型 |
| 2.2.2 空间预测模型 |
| 2.2.3 组合预测模型 |
| 2.3 路径规划算法 |
| 2.4 本章小结 |
| 第三章 基于时空融合卷积网络的城市交通流预测研究 |
| 3.1 引言 |
| 3.2 城市交通流预测问题建模 |
| 3.2.1 空间邻居子图 |
| 3.2.2 相似邻居子图 |
| 3.3 时空融合卷积网络模型 |
| 3.3.1 整体框架设计 |
| 3.3.2 多头自注意力时间卷积网络 |
| 3.3.3 多图融合图卷积神经网络 |
| 3.3.4 时空融合网络 |
| 3.4 基于粒子群的时空融合卷积网络参数优化算法 |
| 3.4.1 粒子群算法 |
| 3.4.2 算法设计 |
| 3.5 实验结果及分析 |
| 3.5.1 实验设置 |
| 3.5.2 数据预处理 |
| 3.5.3 实验分析验证 |
| 3.6 本章小结 |
| 第四章 随机时变路网的动态路径规划算法研究 |
| 4.1 引言 |
| 4.2 交通流基本参数与影响因素 |
| 4.2.1 交通流基本参数 |
| 4.2.2 城市交通流外部影响因素 |
| 4.3 基于路网状态信息的动态路径规划 |
| 4.3.1 城市道路交通图 |
| 4.3.2 动态路网状态信息的网络模型 |
| 4.3.3 基于路网状态信息的动态路径规划算法设计 |
| 4.4 实验结果及分析 |
| 4.4.1 矢量地图数据 |
| 4.4.2 实验分析验证 |
| 4.5 本章小结 |
| 第五章 总结与展望 |
| 5.1 研究工作总结 |
| 5.2 未来工作展望 |
| 参考文献 |
| 缩略语 |
| 致谢 |
| 攻读学位期间取得的研究成果 |
（6）网络虚拟化环境下虚拟网络映射算法研究（论文提纲范文）
| 摘要 |
| Abstract |
| 专用术语注释表 |
| 第一章 绪论 |
| 1.1 研究背景与意义 |
| 1.2 研究内容与目标 |
| 1.3 本文的主要贡献 |
| 1.4 本文的组织架构 |
| 第二章 网络虚拟化技术及虚拟网络映射问题综述 |
| 2.1 网络虚拟化技术综述 |
| 2.1.1 虚拟化相关技术 |
| 2.1.2 商业模型 |
| 2.2 虚拟网络映射问题 |
| 2.2.1 虚拟网络映射问题模型 |
| 2.2.2 虚拟网络映射过程 |
| 2.2.3 虚拟网络映射目标 |
| 2.2.4 虚拟网络映射性能指标 |
| 2.3 虚拟网络映射算法综述和分类 |
| 2.3.1 国内外研究现状 |
| 2.3.2 虚拟网络映射算法分类 |
| 2.4 本章小结 |
| 第三章 基于多网络拓扑属性和全局网络资源的启发式算法 |
| 3.1 引言 |
| 3.2 多网络拓扑属性和全局网络资源的节点排序算法 |
| 3.2.1 网络拓扑属性和网络资源 |
| 3.2.2 节点排序方法 |
| 3.3 多网络拓扑属性和全局网络资源的启发式算法 |
| 3.3.1 直接启发式子算法 |
| 3.3.2 稳定启发式子算法 |
| 3.4 实验仿真与结果分析 |
| 3.4.1 实验环境和参数设置 |
| 3.4.2 实验结果和分析讨论 |
| 3.5 本章小结 |
| 3.5.1 算法小结 |
| 3.5.2 未来工作 |
| 第四章 基于多个底层物理网络和高能效的启发式算法 |
| 4.1 引言 |
| 4.2 多个底层物理网络下的节能映射 |
| 4.2.1 多物理网络下的虚拟网络映射 |
| 4.2.2 虚拟网络映射的能耗模型 |
| 4.3 多底层物理网络下的高能效启发式虚拟网络映射算法 |
| 4.3.1 虚拟节点映射方案 |
| 4.3.2 虚拟链路映射方案 |
| 4.4 实验仿真与结果分析 |
| 4.4.1 实验环境与参数设置 |
| 4.4.2 实验结果与分析讨论 |
| 4.5 本章小结 |
| 4.5.1 算法小结 |
| 4.5.2 未来工作 |
| 第五章 基于动态在线映射和QoS需求调整的启发式算法 |
| 5.1 引言 |
| 5.2 动态在线映射和QoS驱动调整的启发式映射算法 |
| 5.2.1 动态在线映射 |
| 5.2.2 QoS性能驱动调整 |
| 5.3 实验仿真与结果分析 |
| 5.3.1 实验环境和参数设置 |
| 5.3.2 实验结果和分析讨论 |
| 5.4 本章小结 |
| 5.4.1 算法小结 |
| 5.4.2 未来工作 |
| 第六章 基于个性化虚拟网络服务需求的启发式算法 |
| 6.1 引言 |
| 6.2 基于个性化虚拟网络服务需求的启发式映射算法 |
| 6.2.1 虚拟网络分类子算法 |
| 6.2.2 分类后的虚拟网络映射子算法 |
| 6.3 实验仿真与结果分析 |
| 6.3.1 实验环境和参数设置 |
| 6.3.2 实验结果和分析讨论 |
| 6.4 本章小结 |
| 6.4.1 算法小结 |
| 6.4.2 未来工作 |
| 第七章 总结与展望 |
| 7.1 本文总结 |
| 7.2 未来研究展望 |
| 参考文献 |
| 附录1 程序清单 |
| 附录2 攻读博士学位期间撰写的论文 |
| 附录3 攻读博士学位期间申请的专利 |
| 附录4 攻读博士学位期间参加的科研项目 |
| 致谢 |
（7）时变网络流分析与调度方法研究（论文提纲范文）
| 摘要 |
| ABSTRACT |
| 缩略语对照表 |
| 第一章 绪论 |
| 1.1 时变网络研究背景与意义 |
| 1.1.1 时变网络的研究背景与应用需求 |
| 1.1.2 时变网络与时变图理论的内在联系 |
| 1.1.3 时变网络与时变图理论的研究意义 |
| 1.2 时变网络及其关键技术的发展动态 |
| 1.2.1 典型时变网络的发展动态 |
| 1.2.2 时变网络关键技术发展趋势 |
| 1.3 时变网络流分析与调度方法研究现状及面临挑战 |
| 1.3.1 时变图模型与时变图理论研究现状 |
| 1.3.2 时变网络流分析与调度研究现状 |
| 1.3.3 时变网络流分析与调度面临的挑战 |
| 1.4 论文的主要贡献与结构安排 |
| 第二章 时变网络单源单汇最大流分析方法 |
| 2.1 引言 |
| 2.2 相关工作 |
| 2.3 存储时间聚合图模型 |
| 2.3.1 存储时间聚合图的数学描述 |
| 2.3.2 存储时间聚合图的基本定义 |
| 2.4 基于存储时间聚合图的时变网络最大流算法 |
| 2.4.1 时变网络最大流问题描述 |
| 2.4.2 时变网络最大流算法 |
| 2.4.3 算法实例分析 |
| 2.5 时变图模型及算法的分析与比较 |
| 2.5.1 时变图模型的优势分析 |
| 2.5.2 时变图模型存储复杂度对比 |
| 2.5.3 最大流算法复杂度分析与对比 |
| 2.6 本章小结 |
| 第三章 时变网络二源二汇最大流分析方法 |
| 3.1 引言 |
| 3.2 相关工作 |
| 3.3 二源二汇最大流问题的建模与转化 |
| 3.3.1 二源流问题建模 |
| 3.3.2 二源流问题的解耦与转化 |
| 3.3.3 和流图与差流图的构建 |
| 3.4 基于存储时间聚合图的二源二汇最大流算法 |
| 3.4.1 动态联合二源二汇最大流算法 |
| 3.4.2 计算和流图与差流图的最大流 |
| 3.4.3 动态调整存储转移序列 |
| 3.4.4 算法实例分析 |
| 3.4.5 算法复杂度分析 |
| 3.5 仿真结果与分析 |
| 3.5.1 仿真场景及参数设置 |
| 3.5.2 性能分析 |
| 3.6 本章小结 |
| 第四章 时变网络任务流QoS保障路由策略 |
| 4.1 引言 |
| 4.2 系统模型 |
| 4.2.1 面向多任务的卫星网络 |
| 4.2.2 卫星网络模型 |
| 4.2.3 按需的任务模型 |
| 4.3 任务流相关定义与问题建模 |
| 4.3.1 任务流相关定义 |
| 4.3.2 问题建模 |
| 4.4 基于存储时间聚合图的任务流QoS保障路由策略 |
| 4.4.1 QoS保障多路径路由算法 |
| 4.4.2 存储时间聚合图的最短路径计算 |
| 4.4.3 面向任务的路径最大流与剩余网络计算 |
| 4.4.4 算法实例分析 |
| 4.4.5 算法复杂度分析 |
| 4.5 仿真结果与分析 |
| 4.5.1 仿真场景与参数设置 |
| 4.5.2 仿真结果与分析 |
| 4.6 本章小结 |
| 第五章 总结与展望 |
| 5.1 全文内容总结 |
| 5.2 后续研究工作展望 |
| 参考文献 |
| 致谢 |
| 作者简介 |
（8）Top-k图中介度增量式计算方法研究（论文提纲范文）
| 摘要 |
| ABSTRACT |
| 第一章 绪论 |
| 1.1 研究目的与意义 |
| 1.2 国内外研究现状 |
| 1.2.1 中介度研究现状 |
| 1.2.2 动态网络下中介度研究现状 |
| 1.2.3 近似中介度研究现状 |
| 1.3 亟待解决的问题 |
| 1.4 研究思路 |
| 1.5 技术路线 |
| 1.6 论文组织结构 |
| 第二章 相关技术 |
| 2.1 图的相关定义 |
| 2.2 中介度算法 |
| 2.3 增量算法 |
| 2.3.1 增量图算法 |
| 2.3.2 增量中介度算法 |
| 2.3.3 增量近似中介度算法 |
| 2.4 近似中介度算法 |
| 2.4.1 单节点近似中介度算法 |
| 2.4.2 自适应近似中介度算法 |
| 2.4.3 抽样近似中介度算法 |
| 2.5 本章小结 |
| 第三章 动态图下节点中介度计算的增量式算法研究 |
| 3.1 引言 |
| 3.2 动态中介度算法设计 |
| 3.2.1 算法设计思路 |
| 3.2.2 枢轴删边计算 |
| 3.2.3 枢轴增边计算 |
| 3.2.4 更新中介度 |
| 3.2.5 动态节点中介度算法框架 |
| 3.3 实验分析 |
| 3.3.1 实验设置 |
| 3.3.2 实验数据集 |
| 3.3.3 实验评价指标 |
| 3.3.4 实验结果及分析 |
| 3.4 本章小结 |
| 第四章 静态图下Top-k节点中介度计算的近似算法研究 |
| 4.1 引言 |
| 4.2 Top-k节点近似中介度算法设计 |
| 4.2.1 算法设计思路 |
| 4.2.2 缩放过程 |
| 4.2.3 置信区间分析 |
| 4.2.4 枢轴选择方法 |
| 4.2.5 Top-k节点中介度算法框架 |
| 4.2.6 算法描述 |
| 4.3 实验分析 |
| 4.3.1 实验设置 |
| 4.3.2 实验数据集 |
| 4.3.3 实验评价指标 |
| 4.3.4 实验结果及分析 |
| 4.4 本章小结 |
| 第五章 动态图中Top-k节点中介度计算的近似算法研究 |
| 5.1 引言 |
| 5.2 动态Top-k节点中介度算法设计 |
| 5.2.1 算法设计思路 |
| 5.2.2 更新前后枢轴中介度 |
| 5.2.3 维护前Top-k中介度的可靠性 |
| 5.2.4 算法框架 |
| 5.3 实验分析 |
| 5.3.1 实验设置 |
| 5.3.2 实验数据集 |
| 5.3.3 实验评价指标 |
| 5.3.4 实验结果及分析 |
| 5.4 本章小结 |
| 第六章 总结与展望 |
| 6.1 工作总结 |
| 6.2 未来展望 |
| 参考文献 |
| 致谢 |
| 个人简历 |
（9）基于在线地图速度数据的城市动态最短路径选择算法研究（论文提纲范文）
| 摘要 |
| ABSTRACT |
| 第1章 绪论 |
| 1.1 研究背景与问题提出 |
| 1.1.1 研究背景 |
| 1.1.2 问题提出 |
| 1.2 研究目的与意义 |
| 1.2.1 研究目的 |
| 1.2.2 研究意义 |
| 1.3 国内外研究现状 |
| 1.3.1 短时交通预测研究现状 |
| 1.3.2 动态最短路径选择研究现状 |
| 1.4 研究内容与技术路线 |
| 1.4.1 研究内容 |
| 1.4.2 技术路线 |
| 第2章 在线地图速度数据获取 |
| 2.1 基本思路 |
| 2.2 在线地图速度数据获取 |
| 2.2.1 在线地图概述 |
| 2.2.2 交叉口经纬度坐标提取 |
| 2.2.3 路段里程与行程时间爬取 |
| 2.3 基于python的在线地图速度数据获取 |
| 2.3.1 python第三方工具 |
| 2.3.2 在线地图速度数据采集 |
| 2.4 本章小结 |
| 第3章 基于在线地图速度数据的深度网络短时速度预测 |
| 3.1 基本思路 |
| 3.2 符号说明 |
| 3.3 道路交通速度空间依赖关系挖掘 |
| 3.3.1 卷积神经网络 |
| 3.3.2 图卷积神经网络 |
| 3.3.3 基于GCN的道路交通速度空间依赖关系挖掘 |
| 3.4 道路交通速度时间依赖关系挖掘 |
| 3.4.1 循环神经网络 |
| 3.4.2 长短时记忆网络 |
| 3.4.3 基于LSTM的道路交通速度时间依赖关系挖掘 |
| 3.5 路段短时速度预测 |
| 3.5.1 BP神经网络 |
| 3.5.2 基于时空依赖性挖掘的GCN-LSTM-BP网络 |
| 3.5.3 预测效果评价指标 |
| 3.6 本章小结 |
| 第4章 基于短时交通速度预测的动态最短路径选择 |
| 4.1 基本思路 |
| 4.2 图论及路网抽象化 |
| 4.2.1 图论基础 |
| 4.2.2 路网抽象化 |
| 4.3 基于速度预测信息的动态最短路径选择模型构建 |
| 4.3.1 动态最短路径评价指标确定 |
| 4.3.2 路径行程时间分析 |
| 4.3.3 动态行程时间最短路径选择模型构建 |
| 4.3.4 算例应用 |
| 4.4 基于速度预测信息的动态最短路径选择模型求解 |
| 4.4.1 Dijkstra算法 |
| 4.4.2 考虑时变矩形区域限制的Dijkstra算法改进 |
| 4.4.3 基于改进Dijkstra算法的动态行程时间最短路径选择 |
| 4.4.4 算法性能分析 |
| 4.5 本章小结 |
| 第5章 案例应用与分析 |
| 5.1 区域路网描述 |
| 5.2 在线地图速度数据获取与分析 |
| 5.3 路网短时交通速度预测结果与分析 |
| 5.3.1 道路交通速度空间依赖关系挖掘结果与分析 |
| 5.3.2 道路交通速度时间依赖关系挖掘结果与分析 |
| 5.3.3 基于BP神经网络的短时交通速度融合预测结果与分析 |
| 5.3.4 不同模型预测结果对比分析 |
| 5.4 动态行程时间最短路径选择结果与分析 |
| 5.4.1 路段速度预测结果 |
| 5.4.2 基于传统Dijkstra算法的动态最短路径选择结果与分析 |
| 5.4.3 基于改进Dijkstra算法的动态最短路径选择结果与分析 |
| 5.4.4 最短路径搜索结果对比分析 |
| 5.5 本章小结 |
| 第6章 结论与展望 |
| 6.1 主要结论 |
| 6.2 不足与展望 |
| 致谢 |
| 参考文献 |
| 附录A |
| 附录B |
| 在学期间发表的论文和取得的学术成果 |
（10）动态复杂网络的最短路径研究（论文提纲范文）
| 摘要 |
| abstract |
| 第1章 绪论 |
| 1.1 课题背景 |
| 1.2 研究目的和意义 |
| 1.3 国内外研究现状 |
| 1.4 本文研究内容及结构 |
| 第2章 相关研究工作 |
| 2.1 复杂网络的基本理论 |
| 2.1.1 网络理论的表示方法 |
| 2.1.2 基本模型 |
| 2.2 复杂网络的最短路径相关研究 |
| 2.2.1 最短路径的经典算法 |
| 2.2.2 基于稳定区间的最短路径求解方法 |
| 2.2.3 动态复杂网络的最短路径求解方法 |
| 2.3 复杂网络的特征度量 |
| 2.3.1 基本度量 |
| 2.3.2 中心性度量 |
| 2.4 本章小结 |
| 第3章 复杂网络最短路径的预处理 |
| 3.1 复杂网络的简化 |
| 3.1.1 叶子节点的多次简化 |
| 3.1.2 叶子节点的增加、删除 |
| 3.1.3 叶子节点相关边的增加、删除 |
| 3.1.4 叶子节点的预处理算法描述 |
| 3.2 复杂网络的区域划分 |
| 3.2.1 局部区域中心节点的选择策略 |
| 3.2.2 局部中心点的处理算法描述 |
| 3.2.3 中继节点 |
| 3.2.4 复杂网络的初始化区域划分方法 |
| 3.3 本章总结 |
| 第4章 动态复杂网络最短路径的近似计算 |
| 4.1 复杂网络的动态变化及处理方式 |
| 4.1.1 局部中心点节点的变化引起的区域改变 |
| 4.1.2 中继节点的变化引起的区域变化 |
| 4.2 算法描述 |
| 4.2.1 最短路径的求解 |
| 4.2.2 中继节点的处理算法描述 |
| 4.2.3 最短路径的算法描述 |
| 4.3 复杂度分析 |
| 4.4 本章总结 |
| 第5章 实验分析 |
| 5.1 实验环境及最短路径准确性衡量方法 |
| 5.1.1 实验环境 |
| 5.1.2 复杂网络最短路径准确性衡量方法 |
| 5.2 实验对比及结果分析 |
| 5.2.1 复杂度分析 |
| 5.2.2 算法运行时的时间对比 |
| 5.2.3 动态改变时的运行时间对比 |
| 5.3 本章小结 |
| 第6章 总结与展望 |
| 6.1 总结 |
| 6.2 展望 |
| 致谢 |
| 参考文献 |
| 攻读学位期间发表的学术论文及参加科研情况 |
四、网络最短路径的动态算法（论文参考文献）
- [1]基于轨迹大数据的动态最优路径规划[J]. 张小芳,冯慧芳. 计算机与现代化, 2021(11)
- [2]基于增强型Dijkstra算法的无信号灯交叉路口智能车辆调度研究[J]. 孙宁,吴伟豪,赵风财,肖广兵. 计算机应用研究, 2022
- [3]交通路况感知下的自适应动态路径规划方法[J]. 常盟盟,袁磊,丁治明,李路通. 交通运输系统工程与信息, 2021(04)
- [4]无线传感网络路由和定位技术研究[D]. 闫江毓. 华北电力大学(北京), 2021(01)
- [5]基于城市道路车流量预测的动态路径规划[D]. 范若乔. 北京邮电大学, 2021(01)
- [6]网络虚拟化环境下虚拟网络映射算法研究[D]. 曹浩彤. 南京邮电大学, 2020(03)
- [7]时变网络流分析与调度方法研究[D]. 张焘. 西安电子科技大学, 2020
- [8]Top-k图中介度增量式计算方法研究[D]. 杨泽宽. 西北农林科技大学, 2020(02)
- [9]基于在线地图速度数据的城市动态最短路径选择算法研究[D]. 钟颖. 重庆交通大学, 2020(01)
- [10]动态复杂网络的最短路径研究[D]. 郭阳. 辽宁大学, 2019(01)