高效实现最短路径问题

本文通过对Dijkstra最短路径搜索算法的分析,从数据存储结构方面对此问题进行了探讨,并提出了一种数据文件结构,最后给出了相关的测试数据。     

最短路径问题的一种高效实现

本文通过时Dijkstra最短路径搜索算法的分析,从数据存储结构方面对此问题进行了探讨,并提出了一种数据文件结构,实验证明该实现具有较高的效率.     

最短路径重构算法

研究了在Ｎ个顶点的图中，仅给出了所有顶点对之间最短路径距离矩阵，而计算任两顶点间最短路径问题。这种算法因没有利用原始图中有关边的信息，被称为重构算法。本研究取得了如下成果：①在单一的顶点对之间最短路径重构的时间复杂度为Ｏ（ｎｌｏｇｎ）；②在所有顶点对之间的最短路径重构的时间复杂度为Ｏ（ｎ＾３）；③在带有ｎ／ｌｏｇｎ个处理器的独占读写并行随机访问器上，单一顶点对之间的最短路径重构时间复杂度为Ｏ（（ｌ     

基于Dijkstra算法的一种最短路径优化算法

详细介绍了经典的Dijkstra算法，举例说明了该算法的实现方法以及该算法的缺点：即需要网络结点数平方级的内存；同时详细说明了一种基于Dijkstra算法的优化算法——邻接结点算法，该算法充分利用了网络拓扑信息中的弧段的连接关系，避免了使用含有大量无穷值的关联矩阵，使之更适合带有拐向限制设置的最短路径算法和大量结点的实际数据。实践证明。该算法可以节约大量的内存，对于结点数比较大的网络，或带有大量拐向限制设置的网络，具有较好的适用性。     

MapReduce求解物流配送单源最短路径研究

针对物流配送路线优化,提出了将配送路线问题分解成若干可并行操作的子问题的云计算模式。详细论述了基于标色法的MapReduce广度优先算法并行化模型、节点数据结构、算法流程和伪代码程序,并通过将该算法应用于快递公司的实际配送,验证了该算法的可行性。     

图的最短路径和传递闭包的并行算法

1.图的最短路径 给定一赋权有向图G=(V,E),假设G中没有带负权圈的顶点,Floyd给出了一个计算G的所有顶点对v_i,v_j之间最短路径算法。在该算法中,用带权邻接矩阵cosT表示图,并规定cosT(i,j)=∞若(i,j)不属于E和cosT(i,j)=0,i,j=0,…,n-1,该算法的设计思想是按下面的递推规则依次产生矩阵序列A~0,…,A~(n-1),其中A~(n-1)即是G的所有顶点对之间最短路径的长度。     

单源点最短路径的一种新算法

本文介绍的求单源点最短路径算法是基于图的搜索思想,采用了优先队列技术,符合一般人们寻找最短路径的习惯,比经典方法容易理解,运算速度也较快。     

基于多核平台并行K-Medoids算法研究

分析K-Medoids算法的内在并行性,设计一个适合多核平台的并行算法,并利用OpenMP进行实验。实验结果表明,并行算法对多核环境有很好的适应性,在双核及四核计算机上均获得了较好的加速比与运行效率。     

单源点最短路径动态优化算法

设计了最短路径时间复杂度取决于边数e和点数n的动态优化算法。采用了独特的动态PV集合链,改进了当前求得的最短路径向量D的存储结构,用PV集合链对向量D进行动态管理,使其时间开销为e+(n-1)×(n-2)/2+3n。当n>4时,SPD OA算法的性能明显优于Dijkstra算法,呈现出良好的动态优化特性。最后对动态优化算法与Dijkstra算法用理论公式得出的数据进行了时间性能比较。     

时序最短路径算法

最短路径是指网络中两结点间阻碍强度最小的一条路径。传统的最短路径是在静态网络上进行研究的,然而现实生活中很多网络是动态的、有时序性的,因此传统的最短路径算法并不能用于解决所有最短路径问题。为了寻找时序网络上的最短路径,在Dijkstra算法思想基础上,提出一种时序最短路径的精确算法。文中利用严格的数学推导证明了本算法的可行性,并通过对构建的网络做实证分析验证了算法的正确性。     

多核CPU/GPU平台下的集合求交算法

提出一个多核CPU/GPU混合平台下的集合求交算法.针对CPU端求交问题,利用对数据空间局部性和中序求交的思想,给出内向求交算法和Baeza-Yates改进算法,算法速度分别提升0.79倍和1.25倍.在GPU端,提出有效搜索区间思想,通过计算GPU中每个Block在其余列表上的有效搜索区间来缩小搜索范围,进而提升求交速度,速度平均提升40％.在混合平台采用时间隐藏技术将数据预处理和输入输出操作隐藏在GPU计算过程中,结果显示系统平均速度可提升85％.     

基于H.264实时编码的多核并行算法

针对H.264多核实时编码架构,根据编码模块的数据依赖关系,提出基于相邻宏块的并行算法,融合Slice级、宏块行级和相邻宏块级并行算法,实现多粒度并行编码算法,加大了数据并行深度。实验结果表明,该并行编码算法在图像质量几乎不变的情况下能有效提高并行加速比。     

路径节点驱动的低代价最短路径树算法

Dijkstra算法是一个优秀的最短路径求解算法,同时也产生一棵最短路径树SPT(shortest path tree);该算法在网络计算与优化中得到了广泛的应用.为了对最短路径树进行代价优化,提出了路径节点驱动的思想.基于这种思想设计了路径节点驱动的最低代价最短路径树算法LCSPT(least-cost shortest path tree algorithm).通过LCSPT算法一个正计算节点能够最大化与当前最短路径树中的路径共享,因而进一步优化SPT树代价性能,生成高性能的SPT树.作为算法的重要组成部分,使用数学归纳法证明了算法的正确性;从理论上分析了LCSPT算法的代价性能,以及和同类算法相比如何取得最小代价性能;同时,对其时间复杂度和空间复杂度进行了分析.最后通过3个仿真实验验证了该算法在构建SPT时的正确性和其最小代价最短路径树特性.     

基于异构多核处理器的H.264并行编码算法

H.264视频编码标准计算复杂度较高,难以完成高清视频的实时编码。为此,提出异构多核DM6467平台的H.264并行编码算法。综合DM6467内部各个硬件加速引擎的依赖关系和存储器特点,设计宏块级并行编码算法,通过分析多slice模式流水线的特点,以及数字信号处理器和ARM双核任务分配,提出合并流水线、核间负载均衡的优化方案。实验结果表明,优化后的编码器效率提高18%,能实现在DM6467平台上1080P的实时编码。     

多核处理器大规模并行系统中的任务分配问题及算法

对基于多核处理器的大规模并行系统中的任务分配问题进行了分析讨论,在此基础上建立了任务分配模型,并提出一种基于迭代的任务分配算法,该算法分为两轮操作,分别完成进程到处理节点和进程内线程到处理器核的分配,每轮操作经过带回溯的多次迭代处理,最终得到任务关系图的划分.实验数据表明该算法能在较短时间内求得近优解,并且当线程个数增大时,算法的求解时间远小于遗传算法.     

基于多核处理器的网络内容并行还原系统

研究现有网络信息内容还原系统实现原理及各种改进策略。根据现有网络信息内容还原系统未充分利用运算资源以及当前多核处理器高度普及的现状,提出基于多核处理器的网络信息内容并行还原系统,将高流量数据包分流到多个处理进程,利用多核处理器的运算资源,从而达到在不添加额外硬件资源的情况下提高处理能力的目的。实验结果表明,该系统可以有效提高网络信息内容还原系统的处理流量。     

适合复杂网络分析的最短路径近似算法

基于互联网抽取的社会网络往往具有较大的规模,这对社会网络分析算法的性能提出了更高的要求.许多网络性质的度量都依赖于最短路径信息,社会网络等现实网络往往表现出"无标度"等复杂网络特征,这些特征指示了现实网络中最短路径的分布规律.基于现实网络的拓扑特征,提出了一种适合于复杂网络的最短路径近似算法,利用通过局部中心节点的一条路径近似最短路径,该算法能够方便地用于需要最短路径信息的社会网络性质的估算,为复杂网络的近似分析提供了一种新的思路.在各种生成网络与现实网络上的实验结果表明,该算法在复杂网络上能够大幅降低计算复杂性并保持较高的近似准确性.     

单源最短路问题高效算法探究

单源最短路问题是算法研究中由来已久的一个问题,在算法领域早期已经得到了较好的解决,但是在应用计算机语言实现的过程中往往不够优化．导致较高的时间复杂度和空间复杂度。从原始的迪杰斯特拉算法入手,进行透彻分析,在算法思想和实现方式上提出一种全面优化的算法方案,并给出了核心代码。实现过程中使用了堆的数据结构,并在具体的实现过程中进行灵活的优化。经过理论的算法复杂度分析,以及实际的数据测试,都证明全新优化后地单源最短路算法计算耗时非常少,空间复杂度也得到很大程度的降低．应用价值更强。     

Termination Detection for Parallel Shortest Path Algorithms

Shortest path computation is required by a large number of applications such as VLSI, transportation, and communication networks. These applications, which are often very complex and have sparse networks, generally use parallel labeling shortest path algorithms. Such algorithms, when implemented on a distributed memory machine, require termination detection methods; these methods consist of some type of synchronization among all processors. Because global synchronization can be costly, it is assumed that the best termination detection methods synchronize as infrequently as possible. The frequency, however, can significantly impact the idle time of parallel labeling shortest path algorithms. In this paper we analyze the impact of this frequency on the performance, in particular the idle time, and identify when low versus high frequency detection is best. The analysis and results indicate that when the size of the subnetwork assigned to processor is small enough so that the computation time is less than or equal to the communication time within an iteration, high frequency termination detection methods should be used. Otherwise, low frequency methods should be used.     

基于多核处理器的并行编程模型

为解决传统编程模型与并行架构间存在的矛盾,针对多媒体和网络应用程序的特点,提出一种基于多核处理器的并行编程模型,该模型采用节点化的并行程序描述方式,将并行编译器划分到多个核上运行。实验结果表明,这种新的并行编程模型能有效提高程序的执行效率。