多链路权值增大的动态最短路径算法

动态网络最短路径是交通、通信等系统中的重要问题。在处理多链路权值变大时,多链路权值增大的动态最短路径算法可有效地减少单链路权值增大动态最短路径算法的冗余计算。目前,多链路权值增大的动态最短路径算法的研究较少,尚未存在有效的多链路变大的动态最短路径算法。通过对现有动态最短路径算法的深入研究,提出了一种多链路权值增大的动态最短路径算法(DSPT-MLI)。算法复杂度分析和仿真结果显示,DSPT-MLI算法具有更少的节点更新次数和更高的时间效率。     

GIS时变权值网络最短路径算法研究

最短路径分析是GIS网络分析的基础。传统的最短路径算法中,比较经典的算法是Dijkstra算法。由于地理信息系统中的数据具有不确定性、数据量庞大等特点,因此采用传统的Dijkstra算法进行最短路径分析就不适应。为此本文分析了传统网络中的最短路径算法-Dijkstra算法在时变权值网络结构中的局限性,给出了一种适应于时变权值网络的最短路径算法,并且利用改进的邻接表作为存储结构对算法进行了优化。     

改进Dijkstra算法在GIS导航应用中最短路径搜索研究

研究GIS在电子导航系统应用中的最短路径搜索效率问题。在电子导航系统中对最短路径的搜索效率要求很高。随着城市发展交通线路剧增,传统的基于Dijkstra算法的GIS导航系统不能适应日益复杂的交通线路,存在最短路径搜索效率过低的问题。考虑到GIS空间分布的特性,提出了改进的Dijkstra算法用以解决GIS导航中的最短路径搜索问题。改进算法不仅避免了传统Dijkstra算法逐个节点遍历搜索,而且根据方向优先特性缩小搜索范围,大大减少了搜索工作量,并通过改变搜索节点存储的数据结构提高了最短路径的搜索效率。实验表明,这种改进算法较之传统算法能够有效提高最短路径的搜索效率,满足了电子导航系统对最短路径搜索效率的要求,取得了满意的结果。     

GIS-T中途经多地点后返回的最短路径搜索算法

在交通运输过程中，用户经常需要搜索经过多个无序地点后返回起点的最短路径。为此，首先在GIS-T中原有空间数据的基础上，动态地建立了一个两点间最短路径信息库；然后，给出了一个不依赖搜索图、结合路线特点的算法，实现了对所需的最短路径的搜索。     

DW最短路径算法及在逻辑图自动布线中的应用

提出了基于Dijkstra最短路径算法的动态权值最短路径算法，并对该算法提出了优化措施。基于优化的最短路径算法，在芯片分析软件中实现了逻辑图中的两点间自动布线的功能，并在此基础上实现了拖动元件过程中的重布线功能。该算法能够在尽量减少布线交叉和转角的基础上减少布线长度，使得逻辑图清晰易读，提高了芯片反向工程后端电路分析的效率。     

前N条最短路径在网络中的应用

在Dijkstra算法基础上,提出基于双向搜索的前N条最短路径算法,给出了相应的数据结构和算法实现,同时针对网络的动态性,对静态算法作了适当的改进。     

二维权值路径在软件项目管理中的应用

针对以往的软件项目规划过程将时间、成本和资源单独进行评估的局限,将二维权值路径引入到软件项目管理中来.目的就是要研究如何在尽可能低的成本下充分分配关键资源,以缓解在软件项目开发过程中出现的资源争用问题.     

基于区域限定模型的最短路径算法研究

研究地理信息系统中最短路径问题,提高最短路径的搜索速率。针对地理信息系统GIS中最短路径是根据路径权值最小原则选取的,需要逐个遍历系统中所有路径,传统的Di jkstra算法逐个比较所有路径的权值计算量大,不能快速找出最短路径的问题。提出一种基于区域限定模型的算法选取最短路径,采用区域限定模型减少参与计算的路径信息数目,并在此基础上使用启发式搜索策略快速找到最短路径,这样就避免了对系统中所有路径信息遍历带来的计算量大、搜索速率不高的问题。实验证明,改进方法能够快速将最短路径搜索出来,满足地理信息系统实时性的要求,取得了满意的结果。     

机器人路径规划中的双向Dijkstra二叉树算法

在分析现有路径规划和碰撞检测方法的基础上,提出了一种新的机器人路径规划方法：双向Dijkstra二叉树算法。在机器人路径规划中应用传统的Dijkstra算法时间复杂度是O(n¬¬¬¬2),应用该文提出的算法进行路径规划的时间复杂度为O(nlog2n)。通过一些数据的检测,验证了在机器人路径规划中,尤其是在测试数据较多的情况下,该算法可以有效提高效率。     

双向半序网在两点间最优路径算法中的应用

最优路径搜索是地理信息系统重要的网络分析功能,也是其他网络分析功能的基础。该文在分析最优路径算法的基础上,针对特定两点间的最优路径问题,提出一种双向最优半序网结构,通过双向搜索构建该种双向最优半序网,可快速解得指定两点间所有满足最优条件的路径,并给出相应算法。结合计算实例分析并评价了该算法的运行效率。     

Finding the k Shortest Paths in Parallel

A concurrent-read exclusive-write PRAM algorithm is developed to find the k shortest paths between pairs of vertices in an edge-weighted directed graph. Repetitions of vertices along the paths are allowed. The algorithm computes an implicit representation of the k shortest paths to a given destination vertex from every vertex of a graph with n vertices and m edges, using O(m+nk log ² k) work and O( log^3k log ^*k+ log n( log log k+ log ^*n)) time, assuming that a shortest path tree rooted at the destination is pre-computed. The paths themselves can be extracted from the implicit representation in O( log k + log n) time, and O(n log n +L) work, where L is the total length of the output. Received July 2, 1997; revised June 18, 1998.     

一种求解关键路径的新算法

通过定义节点编码图概念,提出一种不需要拓扑排序的求解关键路径的新算法。该算法扩充图的邻接表的存储结构,使图的存储与算法求解过程共享同一存储空间。从图的源节点开始,用加权取极大运算规则,广度优先递归对图中所有节点进行编码。编码图生成后,利用反向搜索求出从源点到汇点的所有关键路径及长度。该算法比现有算法更简单直观,所需的存储空间更小,算法时间复杂度降低到O(n+e),优于现有算法的O(n2)。     

基于BiLSTM模型的漏洞检测

随着计算机技术应用的不断深化,软件的数量和需求不断增加,开发难度不断升级。代码复用以及代码本身的复杂度,使得软件中不可避免地引入了大量漏洞。这些漏洞隐藏在海量代码中很难被发现,但一旦被人利用,将导致不可挽回的经济损失。为了及时发现软件漏洞,首先从源代码中提取方法体,形成方法集;为方法集中的每个方法构建抽象语法树,借助抽象语法树抽取方法中的语句,形成语句集;替换语句集中程序员自定义的变量名、方法名及字符串,并为每条语句分配一个独立的节点编号,形成节点集。其次,运用数据流和控制流分析提取节点间的数据依赖和控制依赖关系。然后,将从方法体中提取的节点集、节点间的数据依赖关系以及控制依赖关系组合成方法对应的特征表示,并运用one-hot编码进一步将其处理为特征矩阵。最后,为每个矩阵贴上是否含有漏洞的标签以生成训练样本,并利用神经网络训练出相应的漏洞分类模型。为了更好地学习序列的上下文信息,选取了双向长短时记忆网络(Bidirectional Long Short-Term Memory Networks,BiLSTM)神经网络,并在其上增加了Attention层,以进一步提升模型性能。实验中,漏洞检测结果的精确率和召回率分别达到了95.3%和93.5%,证实了所提方法能够较为准确地检测到代码中的安全漏洞。     

A Fully Dynamic Approximation Scheme for Shortest Paths in Planar Graphs

In this paper we give a fully dynamic approximation scheme for maintaining all-pairs shortest paths in planar networks. Given an error parameter such that , our algorithm maintains approximate all-pairs shortest paths in an undirected planar graph G with nonnegative edge lengths. The approximate paths are guaranteed to be accurate to within a 1+ factor. The time bounds for both query and update for our algorithm is O( ^-1 n ^2/3 log ² n log D) , where n is the number of nodes in G and D is the sum of its edge lengths. The time bound for the queries is worst case, while that for the additions is amortized. Our approximation algorithm is based upon a novel technique for approximately representing all-pairs shortest paths among a selected subset of the nodes by a sparse substitute graph. Received January 1995; revised February 1997.     

Maintaining Longest Paths Incrementally

Modeling and programming tools for neighborhood search often support invariants, i.e., data structures specified declaratively and automatically maintained incrementally under changes. This paper considers invariants for longest paths in directed acyclic graphs, a fundamental abstraction for many applications. It presents bounded incremental algorithms for arc insertion and deletion which run in O( + || log||) time and O() time respectively, where || and are measures of the change in the input and output. The paper also shows how to generalize the algorithm to various classes of multiple insertions/deletions encountered in scheduling applications. Preliminary experimental results show that the algorithms behave well in practice.     

绣花缝针轨迹问题

运用几何计算和图论理论提出了一个绣花缝针轨迹自动生成算法：先对轮廓走向进行定义，通过轮廓铅垂方向的局部极值点的分割线将图案从上向下进行分割，采用交点的特征值比较彻底地解决了分割时的重点问题，将图案区域准确地划分成缝针能一次完成的若干个节点，在此基础上根据节点的邻接关系建立节点的邻接“图”，通过图论中半哈密尔顿路径或深度遍历方法找到节点的遍历(缝制)序列和每个节点的缝制方向，最后可对设定的起点、终点和缝针间隔的条件自动提供缝针的走向轨迹。     

基于最短路径的道路网络k近邻查询处理

针对基于空间道路网络的k近部查询处理,提出了分布式移动对象更新策略以有效减少服务器计算代价,利用基于内存的空间道路网络部接矩阵、最短路径矩阵结构和移动对象哈希表索引分别对道路网络无向图与移动对象进行存储管理。提出了基于最短路径度量的网络扩展搜索(SPNE)算法,以通过裁剪网络搜索空间来减少k近部查询搜索代价。实验表明,SPNE算法的性能优于传统的NE和MKNN等k近邻查询处理算法。     

结合密集神经网络与长短时记忆模型的中文识别

文本图像识别是计算机视觉领域一项重要任务,而其中的中文识别因种类繁多、结构复杂以及类间相近等特点很具挑战性.为改善这一问题,使用文本行端到端的识别模型.首次提出利用密集卷积神经网络（DenseNet）提取文本图像底层特征,同时避免手工设计、统计图像特征的繁琐;将整行图像特征直接送入双向长短时记忆模型（BLSTM）进行局部相关性分析,减少字符定位分割这一步骤;最后采用时域连接模型（CTC）解码获得识别的文本信息.实验表明所提出的模型可以高效的进行图像文本行的识别,并对图像的多种形变具有较好的鲁棒性.     

公交网络下的一种费用限制最小时态路径查询索引

私人交通网络下的最短路径查询主要考虑路径长度、行驶时间等因素,而公共交通网络下的路径查询需要考虑路径上相邻的边的时间顺序约束以及路径的费用.研究了公共交通网络下3种查询：给定起点、终点、时间区间和费用上限,查找在时间区间内不超过费用上限的最早到达路径、最晚出发路径和最短耗时路径.首先给出一种Dijkstra变种算法Dijk-CCMTP,在此基础上给出3类查询的查询算法.然后提出一种高效的索引结构ACCTL（approximate cost constrained time labelling）.ACCTL采用Dijk-CCMTP对图中的每个顶点预先计算部分从该顶点出发的和到达该顶点的基本路径.对于任意从起点s到终点d的查询,可以采用类似数据库表连接的方式从ACCTL中连接从a出发的和到达d的路径生成近似解,避免遍历原图搜索路径.ACCTL建立索引的时间复杂度是O（|V|·△_max·|E|·（log|E|+△_max））,其中,|V|表示顶点数,|E|表示边数,△_max表示顶点的最大度数.实验验证ACCTL索引支持的查询速度比Dijkstra的变种算法的查询速度快2~3个数量级,并分析了影响建立索引时间和空间大小的因素.     

注水法求解迷宫最优路径

根据灌溉系统的工作原理,提出注水法算法应用于求解迷宫最优路径问题.设定迷宫为一个灌溉系统,水从迷宫的入口注入,通过迷宫的通路水从迷宫的出口流出.从入口注入的水沿通路流向各个方向,在通路的各个位置记忆水流到达的时间.当迷宫出口有水流到达时,从出口到入口根据记录在通路上的时间逐步减小的原则逆向寻找入口就可找到迷宫的所有最优路径.该算法的空间复杂度和时间复杂度同迷宫的规模成线性关系.实验结果显示该算法是一种求解迷宫问题的有效算法.