基于优化的Floyed算法前r条最短路径的实现

最短路径的算法应用在很多领域,基本的Floyed算法是解决任意两点之间的最短路径,在实际应用中会要求给出前r条最短路径,以便决策,从中选择一条最佳的路径,文章在分析Floyed算法的基础上,给出改进算法,求解前r条最短路径,并且优化了Floyed算法的时间代价,使其对稀疏图的效率更高。     

求解最短路径问题的DNA动态规划算法

最短路径问题是一个组合优化问题,许多交通运输、工程、管理等实际问题可转化为最短路径问题进行求解。文中利用DNA计算的并行计算模式,给出一个求解最短路径问题的DNA动态规划算法,该算法最多需要7n-11个生物操作。     

生枝-剪枝算法在专用道设置问题中的应用

专用道设置问题中,将运输任务限定为一个,从而将问题转化为带约束条件的动态最短路径问题。针对该问题的实际特点,设计了生枝-剪枝算法。该算法的核心思想是:穷举所有从起点开始的行驶路径(生枝过程),然后利用剪枝规则剪除不符要求的分枝,最后在抵达终点的行驶路径中经过比较选出最优路径。     

基于最少边的最短路径扰动

提出一种最少边扰动算法，以解决如何在扰动最少边的前提下，以最小代价来使得一条特定的目标路径成为最短路径的问题。该算法基于最少边的最短路径扰动模型，通过引入每条边的权重扰动上限约束，提出了最少扰动边数-最小扰动成本的双目标混合整数规划问题，从而实现操纵网络节点间的最短路径。与以往的最小代价扰动算法相比，该方法降低了扰动的复杂性和扰动网络被察觉的风险。实验表明，最优解使扰动边数减少了约27%，具有更好的性能。     

加工中的最优切割方式

就工业生产中如何安排加工次序的组合优化问题,建立了一个数学模型,将问题转化为求一种分层网络的最短路径。结合问题的特点对求最短路径的Dijkstra标号法进行了改进,得到了一个新算法,该算法能快速求出这种分层网络中的最短路径。     

三维最短路径算法在山间修路问题中的应用

针对交通工程中山间修路问题,建立了三维最短路径模型,并将三维最短路径问题转化为图论最短路径问题,提出了一种三维最短路径算法。结果表明,三维最短路径算法可有效地解决山间修路中出现的问题。     

计算最短路径树Dijkstra算法的改进

针对用于网络寻径表刷新的OSPF路由选择协议中使用的计算最短路径树的Dijkstra算法在网络应用中的不足，提出了一种改进算法，用以计算边和节点上都有代价的图的最短路径树，以更全面刻画网络状态，找到更合理的最短路径树，通过对同一个网络自治系统最短路径树的计算，比较了改进Dijkstra算法和Dijkstra算法的差别，结果表明改进Dijkstra算法能够更加全面地刻画网络状态，找出的最短路径树更为合理。     

常用最短路径算法分析与比较

用于解决最短路径问题的算法被称做最短路径算法。最短路径算法在各种应用中有着广泛的用途。常用的路径算法有Dijkstra算法、Bellman-Ford算法、SPFA算法和DAG图算法,本文对这些算法进行了分析比较。     

最短路径算法在多阶段决策中的应用

介绍了最短路径算法的研究发展.针对多阶段决策问题,给出了利用最短路径算法的求解思路和实例,即图结点表示状态、弧表示状态之间的先后关系.针对套汇问题,指出了其与一般最短路径问题的本质差异：求解路径上权值乘积的最大值.并基于Floyd算法框架,提出了最大获利的套汇算法,算法计算结果优于以往文献.     

Groebner基理论在最短路径问题中的应用

在最短路径问题中，若连通图中相邻节点对xi和xj间的路径径为aij，则节点之间的关系可用多项式xi-xj-aij描述，把所有的这种多项式以终点所表示的项为首项归纳和排序得到集 F，若存在最短路径供选择，则F生成理想的Groebner基为{1}，因此，求节点xm则xk的最短路径，可用多项式xk-xm对F中的无素约化，所得到的一个常数就是这条可达路径的长度；若有多条路径可供选择，则每条路径对应一个常数，所有些常数中的最小数就是最短路径的长度。     

具有多条最短路径的最短路问题

尽管Dijkstra算法是解决正权单源点最短路问题公认的最好算法,但它仅能求得从源点到指定点的一条最短路径,为了给出从源点到指定点的所有最短路径,通过改进临时标号过程,得到了修正的Dijkstra算法.修正后的算法得到的不再是最短路径树,而是最短路径图.相对于原算法,修正后的算法不仅更加简便,而且应用Yen算法能够按照边数由少到多的顺序罗列出所有的最短路径.     

A*算法改进及其在动态最短路径问题中的应用

动态最短路径搜索算法是智能交通系统技术应用的关键问题之一．为了解决这一问题,提出以一致性原则动态形式为基础的动态A*算法(dynamic A* algorithm,DA* algorithm)并证明了在两节点间动态下界满足一致性原则动态形式前提下,该算法能够求解满足先进先出原则的动态网络中两节点间最短路径问题．在以广州市交通路网为基础的动态网络上对DA*算法进行试验．试验结果表明,Dijkstra算法的和A*算法的平均计算时间分别是DA*算法的6．55和1．43倍．     

基于N 条最短路径的成品油管道优化设计

采用了赋权有向图来表示成品油管道工艺方案优化设计问题,若干个泵站位置候选点对应图的顶 点,两顶点间管段的总费用现值对应弧的权值,通过循环调用Dijkstra算法,求解出了前N 条最短路径作为最优和 次优方案,以备多方案比选。该方法既兼顾了工程实际的要求,又可以给出最优、次优工艺方案。实际算例表明该 方法切实可行。所提出的方法可以推广应用到其它油气管道工艺方案优化设计或其它工程应用。     

基于开关函数求广义最短通路的新算法

在分析现有求解最短通路的多种算法的基础上,给出了一种求广义最短通路的算法的理论依据.只需通过简单的环和运算求取图中的所有回路,然后选择要求的两顶点之间的任意一条通路,再进行一次环和运算,就可以求出图中任意两点间的最短通路长度.用实例验证了这种算法的正确性.与传统算法相比,该算法不仅可以求出一类广义最短通路,还可以获得相应的通路标识,而且减少了计算量.     

基于k短路径算法的多目标最短路径算法

为满意地解决多目标最短路径问题,提出基于循环搜索第k短路径,构造新集合做交集的多项式算法。该算法是在每一轮的k短路搜索完以后,通过交集产生多目标最短路径或备选路径。当有多条备选路径时再用Vague集投影和距离的决策方法,根据评价值的大小对候选方案进行排序,从而选取最佳方案。     

机器人避障模型简

研究了机器人在存在12个不同形状、不同大小障碍物的平面区域内避障的最短路径及最短时间路径问题.结合图论中的Dijsktra算法,获得了机器人避障的最佳路线;并对最佳路线进行了平滑处理,分别建立了问题一、二的非线性规划优化模型;利用Maple软件和Lingo软件编程,求出了最短路径、最短时间路径及切点的坐标.     

最短路问题的Floyd算法的若干讨论

对不含负回路的网络中所有顶点对之间的最短路问题,通常采用Floyd算法.对此算法进行了讨论,并对Floyd算法的计算过程作了一点改进.改进后的算法对阶数不太大的网络进行较简单的计算就能得出所有顶点对之间的最短路.     

求解捷径问题的矩阵表作业法

依据树的逐步生成原理,仿照矩阵运算,提出了求解捷径问题的生成树算法。可以在表上进行演算,一次运算,能得到所有节点相对于始点的最短路径与路程。与公认的求解捷径问题的最有效方法－标号法相比更有规则、更有秩序,更适合复杂网络图的求解。     

结合NAT穿透的应用层组播方案的设计

针对流媒体直播系统的数据传输,设计了一个应用层组播方案,结合NAT穿透技术构建和维护支持不同种类局域网通信的组播树。该方案的核心内容是提出了一个改进的目的驱动最短路径算法,使用网络传输延迟作为度量值构建低代价最短路径树,可以使从源节点到目的节点的传输延迟最小,并且尽可能减少带宽消耗。组播树维护策略能有效的重构组播拓扑结构,增强组播树的健壮性。