共查询到18条相似文献,搜索用时 125 毫秒
1.
一种新的大规模网络最短路径的近似算法 总被引:1,自引:0,他引:1
平均最短路径长度是复杂网络的一个重要特性,但是对于大规模网络的平均最短路径长度的计算是困难的.在最近的一次对中国教育网的研究中.建立了一个有2 354 934个网页和26 816 209个链接的网络.要想计算该网络的平均最短路径长度,无论是传统的Floyd、Dijkstra算法,还是基于MPI的并行算法,在现有的计算机资源下都难以实现.提出了二级网络的概念,并基于此给出了一种针对中国教育网的新算法,使得在可以接受的时间内完成平均最短路径的近似计算,经试算效果令人满意,说明这种方法对于计算大规模网络的平均最短路径是有效的. 相似文献
2.
3.
新型公交网络模型与最优出行路径算法 总被引:1,自引:0,他引:1
给出一种标号的二分图公交网络模型,在此模型基础上给出线路换乘与最优出行路径的算法,这种算法充分利用标号信息给出站点网络图的边权函数.基于站点网络图不仅能够搜索换乘线路而且能够找到最短路径.最后利用天津市部分公交系统验证了该模型及方法的有效性. 相似文献
4.
研究了结点等待费用、弧费用和弧通过时间均为离散时变函数的最短路径问题.基于动态规划原理,给出了一种标号更新算法,可在O(n3M3)时间复杂度内求出所有结点到指定终点的最小费用路径,其中n为网络结点数、M为时间间隔数. 相似文献
5.
当网络中的权值不是常数而是含参数的函数时,它可以看作是一种动态网络,用传统的算法求解这类网络的最短路径变得十分困难.为此,提出了含二次参数权的多阶段网络最短路问题,并利用Dijkstra算法思想和隐枚举方法给出了求该网络最短路的隐枚举标号算法,最后对该算法的复杂性进行了分析.理论分析与实验结果表明,尽管该算法不是多项式的,但对于一定规模的该类网络还是十分有效的. 相似文献
6.
考虑到城市公交网络的生成和演化受到城市道路交通网络结构约束的现实,利用复杂网络的最新研究分支-空间网络相关理论,构建了适于城市道路交通网络的DMG约束空间;生成了DMG空间约束下的公交站点分布规则,并基于嵌套最短路径,提出了一个城市公交网络的演化模型。以辽阳市道路和公交网络为实证对象,将模型的结果与实际统计数据结果进行了对比,发现模型的仿真结果与实际数据可以很好地吻合,表明了此模型的有效性;利用此模型对城市建设速率和城市公交建设速率的相互关系进行了分析,结果表明,当两者比值呈现2个极端时,公交线网密度都会呈现几何级数级的变化。这为进行城市建设和交通建设规划的速度问题提供了一个决策依据。同时,本模型也揭示了城市公交网络演化的一般规律,为城市公交网络演化的研究提供了一种新思路。 相似文献
7.
求解最小Steiner树的可视化试验方法 总被引:1,自引:0,他引:1
求解最小Steiner树是NP难题,在通信网络设计、交通规划等工程实际中有着广泛的应用.利用表面活性剂溶液的物化特性,将溶液的最小表面张力特性采用平行板结构转化成二维平面的最优路径,得到了最小Steiner树的可视化解.通过改变模板装置和溶液的相对运动,研发出了最短路径可视化仪,为将最小Steiner树求解应用于工程实践探索了新的方法手段. 相似文献
8.
戴显砥 《系统工程理论与实践》1984,4(3)
人们熟知的最短路线问题是根据路径的连接关系建立路径网络,而在网络上通过标号法可以方便简捷地找出最优值和最优解。实际上,非但最短路线问题可以建立网络,资源分配问题、复合系统工作可靠性问题及生产与存储问题等都是可以对实际问题建立起网络来,然后在网络上通过标号法计算出问题的最优值和最优解。这样,可以使计算程序化并变得直观而简便。 相似文献
9.
10.
利用脉冲耦合神经网络(pulse coupled neural network, PCNN)寻找最短路径是一种非确定性算法,运算的复杂度只和最短路径的长度有关,和路径图的复杂程度无关。已有的PCNN最短路径算法只考虑路径长度,而未考虑其他参数,如带宽和时延等。这里除了考虑路径长度,同时考虑实际中带宽剩余量对网络的影响,提出了一种基于带宽剩余率的最短路径算法,用带宽剩余率参数来控制神经元阈值,寻找最短路径。仿真结果表明,该算法可以寻找到全局最优解。 相似文献
11.
12.
在通信网络中,因突发事件造成通信路由节点毁坏或者中断的现象时有发生,传输的数据包不得不从中断处沿着最短的替代路径行进到数据包的接收节点,在这种情形下,哪个路由节点中断使得数据包实际行进的总路程最长呢?从通信网络管理的角度来看这是一个非常重要的问题。对该问题.以前的文献都是从确定情形(事先具有节点中断的完全信息)下进行研究的,本文从不确定情形(只有数据包行进到中断节点的邻接点时才获得该节点中断的信息)的角度重新考虑这个问题。本文首先定义了不确定情形下的最短路径关键点概念,给出了计算不确定情形下最短路径关键点的算法及其时间复杂性分析。结合实际通信网络的算例分析,比较了确定情形下最短路径关键点和不确定情形下最短路径关键点问题,指出了不确定情形下最短路径关键点问题更具有实际意义。 相似文献
13.
多分配快递轴辐网络的枢纽选址与分配优化方法 总被引:2,自引:1,他引:1
快递网络枢纽选址与分配方案的优劣直接关系到快递网络的运营成本和服务水平, 是快递企业运作的基础. 本文详细分析了多分配快递轴辐网络的节点及连接关系、径路特征与形式等网络设计要素, 并分析了快递网络设计中的相关费用和运输时间预算; 在运输时间预算约束下, 以分拣费用、运输费用、中转费用之和为目标函数, 建立了多分配轴辐式快递网络枢纽选址与分配优化模型, 并设计了基于条件最短路的模拟退火求解算法, 最后通过算例验证了模型和算法的有效性. 相似文献
14.
Anna Auguste Anghuwo 《系统工程与电子技术(英文版)》2011,22(4):691-701
The spectrum sharing problem between primary and cognitive users is mainly investigated.Since the interference for primary users and the total power for cognitive users are constrained,based on the well-known water-filling theorem,a novel one-user water-filling algorithm is proposed,and then the corresponding simulation results are given to analyze the feasibility and validity.After that this algorithm is used to solve the communication utility optimization problem subject to the power constraints in cognitive radio network.First,through the gain to noise ratio for cognitive users,a subcarrier and power allocation algorithm based on the optimal frequency partition is proposed for two cognitive users.Then the spectrum sharing algorithm is extended to multiuser conditions such that the greedy and parallel algorithms are proposed for spectrum sharing.Theory and simulation analysis show that the subcarrier and power allocation algorithms can not only protect the primary users but also effectively solve the spectrum and power allocation problem for cognitive users. 相似文献
15.
北京市公共汽车交通网络几何性质的实证研究 总被引:17,自引:0,他引:17
采用复杂网络的研究方法,针对北京市公共汽车交通建立了公交线路、公交换乘和停靠站点复杂网络,利用这3个网络的几何量讨论了北京市公交网络的几何性质。利用实际数据计算的蛄果显示存在某些线路具有中转的作用。部分停靠站点具有中枢作用;民众出行平均需乘坐17.4站并换乘1.7次。研究结果还揭示了公变网络的点权分布具有不同于其他加权网络的点权分布的性质。 相似文献
16.
基于弹复性的交通网络应急恢复阶段策略优化 总被引:2,自引:0,他引:2
重大灾难的灾后恢复一般分为应急恢复阶段和全面恢复阶段,前者面临时间、资金、资源有限等多重困难.传统交通网络灾后恢复研究缺乏结合应急恢复阶段特点的针对性研究.为此,提出一种基于弹复性的交通网络应急恢复阶段策略优化模型.首先,提出两个弹复性度量指标,分别从网络性能恢复速度和累计损失两方面度量弹复性.然后,针对应急恢复阶段,同时考虑上层系统弹复性和下层用户行为的交互,建立交通网络恢复策略双层优化模型.结合并行机调度问题算法和用户均衡配流问题算法,设计一种特殊的交互式双层算法.最后,通过案例验证了模型有效性,表明模型和算法能根据资源、资金、恢复目标、决策者偏好等因素,有效求解大规模交通网络应急恢复阶段的最优恢复策略. 相似文献
17.
Path determination is a fundamental problem of operations research.Current solutions mainly focus on the shortest and longest paths.We consider a more generalized problem;specifically,we consider the path problem with desired bounded lengths(DBL path problem).This problem has extensive applications;however,this problem is much harder,especially for large-scale problems.An effective approach to this problem is equivalent simplification.We focus on simplifying the problem in acyclic networks and creating a path length model that simplifies relationships between various path lengths.Based on this model,we design polynomial algorithms to compute the shortest,longest,second shortest,and second longest paths that traverse any arc.Furthermore,we design a polynomial algorithm for the equivalent simplification of the DBL path problem.The complexity of the algorithm is 0(m),where m is the number of arcs. 相似文献