基于节点合并的最短路问题新算法

提出一个解决非负权网络最短路问题的节点合并算法.该算法以将距离起始节点最近的邻居节点拉到身边的方法,与距离最近节点不断合并,重复这一动作,最终求得起始节点到其他节点的最短路距离.与Dijkstra算法相比,节点合并算法不存在节点着色操作,始终只考虑起始节点的邻居,实现步骤更加简单,整个过程可以采用向量化操作,易于理解和编程实现.数据试验表明,节点合并算法求解效率明显高于Dijkstra算法.

基于动态路网节点的Dijkstra算法路径规划研究

传统Dijkstra算法随着路网节点数目的增多，其时间复杂度成节点数目平方级增加，现有的Dijkstra改进算法无法动态改变原路网节点数目从而影响算法的计算效率。本文提出一种能够动态增加和删除路网节点的Dijkstra算法，提取原始路网模型中的边界角点、十字交叉节点、T型交叉节点以及有其他四条以上路段通过的节点，剔除这些节点之间构成的路段上的其他任务点得到一个新的优化路网模型，保留有原始路网模型的骨架结构的同时简化了路网结构，从而使时间复杂度降低，提高其运行效率。仿真表明，改进算法能够实现动态增删路网节点，在同一路网环境中，随着路网节点数目增多，传统算法耗时越来越大，而改进算法基本维持不变，验证了改进算法的可行性和有效性。

具有交通规则约束的改进Dijkstra算法

传统Dijkstra算法在路径规划时无法适用于具有交通规则约束的交通网络。为解决该问题,在以往的路网模型和算法的基础上,提出一种具有交通规则约束的改进Dijkstra算法。算法对节点新增"待选择状态"和"可再更新状态",用以解决节点具有交通规则约束的问题;同时引入祖父节点,从而生成交通网络中各节点的三元组信息,以此作为回溯依据,可以得到从初始节点到目的节点的最短路径。该算法不仅适用于具有交通规则约束的交通网络,且具有较低的复杂度。通过理论分析证明了算法的正确性,并以长春市朝阳区的实际交通网络和随机添加的交通规则约束为数据进行了实验测试,验证了算法的有效性。

基于蚁群算法的WSNs节点有障环境中部署优化研究

能量限制是无线传感器网络(WSNs)技术中一个关键问题。提出了一种通过无线信道能耗衰减模型利用Dijkstra算法和蚁群算法相结合的WSNs节点静态优化部署策略。通过该策略对两种不同的环境仿真部署验证表明:该策略能更好地优化节点在复杂二维地理环境中的静态部署,并可有效地减少网络的能耗,提高WSNs的使用寿命。

必经节点约束下的光网络最短路径算法

在实际工程应用中,Dijkstra算法是最常用的最短路径算法,但其无法适用于必经节点约束的情况。针对此问题,提出了一种改进型Dijkstra算法。首先通过必经节点排序,将路径划分为路径段。然后通过计算比较重路由成本,求出利于全局最优的局部最优路径段,从而得到目标路径。仿真结果表明:该算法与NIR算法、优化路径长度的NIR算法和全排列算法等同类算法相比,具有较高的计算精度和较低的时间复杂度;算法速度相对较快,且可以逼近甚至得出全局最优解。

经过指定的中间节点集的最短路径算法

目前研究最短路径的算法,多数只是针对从起点出发到达终点的情况。如果限制这条最短路径必须要经过某些指定的中间节点,则现有的一些算法就不再适用了。基于Dijkstra算法和贪心理论,给出了解决此类问题的方法。将相关节点集拆分成三个子集,分别求连通三个子集的局部最短路径,进而形成全局待选最短路径,通过筛选得到目标路径。通过理论分析算法的时间复杂度和实际编程实验确认了该算法的有效性。

有向非负权图中经过必经节点集最短路径算法

传统的Dijkstra算法只是针对起点和终点求解最短路径,而不能解决从起点出发,经过必经节点集,到达终点的无重复节点且无回路的最短路径问题。为此,在有向非负权图中,提出了Dijkstra算法和回溯法相结合的方法。对Dijkstra算法改进,并求解关键节点(起点,终点和必经节点)间的最短路径,进而从关键节点所构成的矩阵中采用回溯法得到目标路径。通过实际的算法实现,测试大量的有向非负权图数据,证实了算法的有效性和正确性。

基于leader-follower算法的超级节点研究

基于leader-follower算法的超级节点P2P网中,研究如何处理新进节点与各超级节点语义不匹配问题,有利于提高节点匹配效率和超级节点性能。引入通用类节点和分裂算法,将与各超级节点语义不匹配的新节点交由通用类节点管理,当管理的节点数目达到一定规模后,采用分裂算法将其分裂为若干语义相似簇,最后用合并排序算法从中选择最优节点作为超级节点。实验表明所提方法提高了节点匹配效率和超级节点性能,具有良好的可行性。

必经节点集约束型无环最短路径算法研究

基于遗传算法和Dijkstra算法,提出了解决必经点集约束型无环最短路径问题的方法.将研究问题分解为只含源点、目的节点和必经节点集的非对称旅行商问题和消除环路问题.首先利用遗传算法求解非对称旅行商问题得到最优必经点序列.但求解得到的最优必经点序列组成的路径是有环路径,为解决环路问题,设计了分段Dijkstra破环策略.通过实验分析验证了算法是有效可行的,相对于传统方法,在时间效率上有较大的提升.

基于地铁站场景的改进型Dijkstra算法疏散路径规划研究

地铁站是城市交通枢纽的重要组成部分,由于其结构和功能具有特殊性,当发生突发事件时,易造成较大的公共安全事故。及时和科学合理地制定人员疏散方案,将人员快速疏散到地上安全区域可以有效降低事件造成的损失与影响。针对城市地铁站内人员疏散路径规划问题,提出一种对疏散路径自身特性进行综合评价的方法。对疏散路径的实际长度、有效宽度及通行难易度3种特征属性进行综合评价,引入路径通行难易度的理论计算公式,用当量长度作为路径综合评价的结果。其次,为兼顾人员数量及拥挤程度在疏散时对人员路径选择的影响,提出节点拥挤度概念,将节点拥挤度作为算法搜索时路径选择的决策原则之一。最后,在标准Dijkstra算法基础上提出一种改进型Dijkstra算法计算疏散路径模型,以温州地铁奥体中心站为背景,进行具体的实例应用。研究结果表明:相比于标准Dijkstra算法模型,改进型Dijkstra算法人员疏散路径规划模型可优化安全出口使用率,均衡各安全出口人流量,提高整体人员疏散效率。研究结果可为地铁站场景人员疏散路径规划以及人流诱导提供一定的理论基础和技术支撑。

基于Dijkstra算法的电缆最短路径算法

结合国内外相关领域的设计和管理方法,建立船舶电缆节点网络模型,通过电缆最短路径算法精确规划电缆最优路径,并结合电缆节点的属性择优选定全船电舾装件规格,从设计源头控制电缆与舾装物量。

求解有向必经节点最短路径问题的算法

具有必经节点的最短路径问题有着广泛的实际应用。但是在有向图的情况下,很多算法会因为所求最优路径中的必经节点顺序与实际不符而不得不进行大量重复性计算。本文针对这种情况提出了一种求解有向图必经节点最短路径问题的算法,可以更早检验是否存在符合路径顺序要求的最短路径并进行有效求解。

网络最短路径算法的改进及实现

从节约存储空间和提高运算速度方面对Dijkstra最短路径算法进行了改进.定义新的节点类来高效存储网络的拓扑信息,节省了计算机存储空间;采用满二叉堆数据结构对节点进行排序并选取最短路径节点,大大提高算法效率.仿真例子表明,对于某些网络结构,改进算法能把传统Dijkstra算法的时间复杂度由原来的O(N2)近似降至O(N).

一种单元化制造系统有效的设计算法

在制造系统中为了满足生产能力的要求，某些类型的机床有多台，并应作为单元化制造系统（ＣＭＳ）设计时的约束。现有的设计方法不能考虑这一类约束。文中强调多台同种机床的存在，并给出了一个单元构成网络问题的模型。利用这一模型，将传统的单元构成和多台同种机床的分配问题结合在一起，给出了求解这一类问题的一种有效的启发式的“合并－分裂”算法，使得在满足机床约束条件的同时简化物流，即减少投资。

网络可靠度分析的改进最小割递推分解算法

在网络连通可靠度分析的最小割递推分解算法基础上,充分利用分解过程中获得的信息,采用合并节点以及合并并联边的方法,有效地简化了分解出来的子网,大幅度降低了算法分解出来的不交最小割和不交最小路数量,从而大幅度地减少了计算时间.3个网络实例计算分析表明,与最小割递推分解算法相比,改进最小割递推分解算法能更高效地计算得到网络系统的连通可靠度,为生命线工程网络的抗震可靠性提供了1种更加有效的分析工具.

一种用于GAF协议的优化邻居表算法

GAF协议是一种基于地理信息的无线传感器网络路由协议,由于采用多跳传输,将导致热区的产生。提出了一种优化邻居表算法,可以有效辨识GAF虚拟网格内的节点密度,从而选择密度大的网格通行,以均衡热区能耗,延长网络寿命。仿真结果验证了该算法的可行性。

车辆导航系统中最短路径算法分析

路线选择是车辆导航系统的核心功能,其实用性和效率对整个系统有着重大的影响。从车辆自导航的角度出发,针对系统运行平台PDA设备容量小且运算速度慢的特点,从节约存储空间、提高运算效率等方面对现有Dijkstra算法提出改进,并结合实际城市地图数据给予实现,试验表明,应用效果良好。

一种MAKLINK图多节点链路建模的路径规划研究

针对传统MAKLINK图规划路径线路改变时,其最优化路径易与环境约束条件冲突的问题,提出了在MAKLINK图中各链路上增加节点数目的方法,以提高系统建模的适应性和鲁棒性。设计的多节点链路通过dijkstra算法得到更为理想的次优化路径,由蚁群算法进行迭代计算获得最优化路径,实现了在保证路径适应度的前提下,提高优化路径对环境约束条件的适应性。实验结果表明,与基本MAKLINK图路径规划算法相比,多节点链路的建模路径规划算法可有效提高次优路径的建模精度,最优路径的适应度值较单节点链路减小了1.43%,具有一定的建模优势。

基于改进自适应大邻域算法的公交线网规划方法

面向城市中大规模线网规划问题,本文提出一种基于改进自适应大邻域算法的公交线网规划方法。该方法首先缩减问题规模,将大量乘客出行OD(Origin-Destination)合并获得城市公交备选站点;综合考虑线网服务客流量、公交站点覆盖率和线路服务效率等优化目标,线网长度、非直线系数、线路换乘等限制条件,分别建立以服务需求/延展换乘为主要功能的主线/支线公交线网规划模型;在OD合并结果基础上设计改进自适应大邻域算法进行问题求解,该方法含改进的8种邻域算子和自适应规则等。案例分析结果表明:本文两阶段算法整体优化效果明显,改进自适应大邻域算法领先现有其他元启发算法;邢台市实际案例计算结果表现良好,该方法能有效解决较大规模线网规划问题。

FPGA布线算法优化

现场可编程门列阵(Field Programmable Gate Array,FPGA)是通过可编程互连接的可配置逻辑块(Configurable Logic Block,CLB)矩阵构成的可编程半导体器件,在电子产品设计及电子产品生产等方面具有广泛的应用。FPGA布线算法是整个EDA系统性能的决定性因素,这里对FPGA布线的Dijkstra算法进行了优化,大大加快了布线速度。