基于STPN求解随机网络最短路的仿真方法

提出了基于时延Petri网求解网络最短路的仿真方法,该方法保持了Dijkstra算法的特性,充分利用了Petri网的并发特性,可迅速而自动地求出最短路,所需计算量仅正比于最短路的长度,与路径图的复杂程度及路径图中的通路总数无关.并将该算法推广到随机网络情形,提出基于随机时延Petri网(STPN)的随机网络最短路仿真算法,可迅速而准确地找到起点与终点之间的随机网络最短路的分布函数.     

用Dijkstra算法求解最短路的矩阵方法

给出了利用权矩阵求解最短路的一种方法.该方法直接在权矩阵中进行简单计算及标记,在最终得到的矩阵中,且通过已标记元素的数值及其位置即可得到源点到其他各点的最短路长及路径.该方法操作简单,且便于在计算机上实现.     

无向网络几种中位点集的性质,结构及算法

本文应用无向网络距离矩阵、顶点边最大距离矩阵等，全面系统地研究无向网络的中位点集、一般中性点集、绝对中位点集、一般绝对中位点集等的性质、结构及算法。     

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

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

最短路问题的灵敏度分析与最短路调整

本文讨论的是无负回路的有向网络,在已知网络各节点间最短路的前提下,当网络中的个别节点、权值、弧发生变化时,变化对最短路有无影响,若有,如何利用变化前的最短路得到改变后的最短路,即：利用网络的独特优势,建立最短路问题的灵敏度分析算法。     

用极小代数方法求解最短路径问题的进一步探讨

用极小代数方法求由n个节点组成的有向连接图的最短路径公式是:A~*=sum from k=0 to n-1 (?)A~k。本文在此基础上给出了求最短路径的充要条件:A~(l+1)=A~l。举出最短运输网络实例加以说明,并和动态规划法作了比较,指出了极小代数法的优越之处。     

带有e约束的网络最短路算法

网络最短路问题有一些成熟的算法,但对于带有约束条件的网络最短路问题这些算法却显得无能为力。本文将网络最短路问题的Ｄｉｊｋｓｔｒａ算法进行了推广,得到了带约束ｅ的网络最短路算法,并将这一算法应用于解决实际问题,得到了令人满意的结果     

无向网络中心的性质,结构及算法

引进简化图等概念，给出无向网络新的分类，深入研究无向网络中心的一些基本性质、结构及算法，得到一些新的结构定量和简便算法。     

独立多约束最短路径选择

多约束最短路径问题一直以来都是通信、交通等领域最主要的问题之一,该问题是一个NP问题.在解决多约束最短路径选择中,代价函数的选择至关重要.针对相互独立的乘性多约束条件,提出一种代价函数的选取框架,并将此框架应用于两约束的最短路径选择中,实验结果表明,能够很好的发现最短路径.     

WDM网络路由计算中的平衡最短路算法

对波分复用(WDM,wavelength division multiplexing)网络中的波长路由分配问题进行了深入的研究,提出了路由预计算部分的平衡最短路(BSP,balanced shortest path)算法。这种算法可以在路由预计算的过程中考虑业务的均衡,而且时间复杂度较低。在不同的网络拓扑结构上对多种波长路由算法进行了仿真,仿真结果说明BSP可以有效地改善网络性能。     

通信网最短路径神经网络选择控制器

通信网正朝着动态无级选路的方向发展,这要求能实时计算出最佳路由。提出了两种基于神经网络的最短路由控制器用于最短路的计算,计算机仿真表明,该控制器能在很短的时间内计算出源节点到宿节点间的最短路由。     

平行四边形限制最短路径算法及其在交通网络中的应用

现有的最短路径搜索算法如D ijkstra算法或椭圆限制的D ijkstra算法等计算效率较低,有待进一步改进。作者在椭圆限制的D ijkstra算法基础上,通过对椭圆进行线性化处理和对限制用的多边形进行优选,得出一种平行四边形限制的最短路径算法,使搜索效率有了较大程度的提高,通过对各种算法的运行结果进行对比,证明了本算法的有效性和快速性。     

基于选择机制的实体间最信任路径发现方法

提出了一种基于选择机制的实体间最信任路径发现算法.该算法采用动态规划思想,同时利用乘关系特点和信息反馈,在计算信任路径过程中可过滤掉无关路径,解决了恶意实体干扰问题、信任路径数目爆炸问题以及回路问题.仿真结果显示,本算法能有效隔离恶意实体,同时具有通信量小,收敛性好的优点.     

基于前馈神经网络的交换网络路径选择控制器

首先提出了一种基于前馈网络的多模拟输入最小值选择电路,然后将该网络用于解决多级级联交换网络的最小费用路径选择问题。计算机仿真表明,此前馈神经网络总能找到全局最优。由于前馈神经网络的计算时延非常短,可以满足高速交换的需要。     

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

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

最短路问题在旅游线路优化中的应用

本文利用Floyd算法探究了最短路问题,经过Matlab实现后将其应用到旅游线路优化设计中。选取了甘肃及周边地区13个旅游景点,求得从任意景点出发到任意目的景点的最短路,以及途中必须给定两个景点的最短路问题。     

一种改进的蚁群算法求解车辆的最短路径问题

基于交通网中交通流参数关系模型,提出了新的状态转移概率计算公式,同时在信息素更新策略中引入交通流密度因子,使算法可以根据时变的路网信息求解车辆的最短路径;利用蚁群算法和遗传算法相结合的思想来避免基本蚁群算法在求解车辆最短路径时易陷入局部最优解的缺陷。实验仿真结果表明,改进后的蚁群算法较基本蚁群算法能准确快速地找到基于时间的最短路径,并能有效解决实际交通系统中的最短路径问题,具有一定的实际意义和参考价值。     

时间依赖图下的最小费用路径搜索

该文提出了一种时间依赖图下最小费用路径的高效搜索算法。已有的算法从起点开始向四周扩展以发现到达终点的路径,搜索空间较大,查询耗时。本文从以下两方面减少搜索空间:首先缩小顶点的有效时间区间避免无用的计算,并且在顶点的相应的时间区间的最小费用正确计算出来之后,再计算扩展路径的费用;然后提出一种双向搜索方法,从起点和终点同时出发向四周扩展路径直到两个搜索相遇,从而控制搜索空间在以起点、终点为圆心的两个小圆内。针对路径的时变依赖性设计了双向搜索的停止条件和路径生成方法,理论上证明了方法的正确性。最后,在大规模数据集上测试验证了方法的有效性。