一种基于移动IPv6路由寻址的最短路径优化算法

移动IPv6的路由寻址是一个最短路径优化问题,最著名的两种最短路径算法是迪杰斯特拉(Dijkstra)算法和弗洛伊德(Floyd)算法,这两种算法的时间复杂度都是O(n3).本文通过对这两种经典算法的研究与分析,提出一种求最短路径的优化算法.该算法的时间复杂度是O(e*n),在连通图中,该算法能够比Floyd算法少近50%的迭代次数,在非连通图中e<相似文献   

低代价最短路径树快速算法的时间复杂度研究

低代价最短路径树是一种广泛使用的多播树,它能够在保证传送时延最小的同时尽量降低带宽消耗.快速低代价最短路径树算法FLSPT是在DDSP算法的基础上,通过改进节点的搜索过程,该算法构造的最短路径树与DDSP算法构造的树具有相同的性能,但其时间复杂度低于DDSP,其时间复杂度为O(nlog n e).FLSPT是利用Fibonacci堆来选择图中未计算点的最小值来计算时间复杂度的.通过对FLSPT的程序和Fibonacci堆的分析发现,用O(log(n!) e)来表示FLSPT算法的时间复杂度比文献[6]中分析的O(nlog(n) e)更能体现FLSPT算法高效率.     

不可达顶点剪枝算法及其在最短路径中的应用

[k]步可达性查询用于回答图[G]中从顶点[u]到达顶点[v]最多[k]步是否存在路径,但其多用于无权图的可达性研究。针对加权图,在图中构建了最早到达、逆向最早到达和最晚到达等三个索引,并应用这三个索引实现对不可达顶点的快速剪枝,从而有效地缩减了加权图的规模。运用该方法建立索引并剪枝顶点的时间复杂度与空间复杂度分别为[O(n+e)]和[O(n)],这里[n]和[e]分别为图中顶点的数目和边的数目。该方法可以与Dijkstra算法、Floyd算法和A*算法等多种传统算法相结合,并应用于最短路径求解,从而提高传统算法计算性能。最后以物流配送网络为例进行了实验验证,实验结果表明提出的方法可以正确并高效地对不必要计算的顶点进行剪枝,从而加快了最短路径求解速度,验证了提出方法的有效性。     

一种新的Kth最短路径搜索算法

借助于“背离”路径的概念,论文在2nd最短路径搜索算法的基础上提出了一种新的Kth最短路径搜索算法,并将其应用至实际环境中。通过K-1次2nd最短路径搜索算法的迭代,该算法可以求出网络中任意两个给定节点之间的Kth最短路径,2nd最短路径搜索算法在计算上具有简单性,因而也同样具有简洁、快速的特点。     

多维代价图模型上最优路径查询问题的研究

近年来,图数据模型被广泛地用于刻画现实世界中各种各样的实体间的复杂关系.最短路径查询是图研究领域中一类非常重要的查询并有着广泛的应用.然而,目前大多数关于最短路径的查询都是定义在单代价(权重)图模型下的.现实世界中,基于单一代价所选择的最短路径并不明智,比如路程最短的路径需要花费极高的费用.该文中,作者介绍了多维代价图模型的概念,并给出了多维代价图模型下基于函数的最优路径的定义.现有的计算最短路径的方法都利用了最短路径的子路径最优的性质:最短路径上的任意两点间的子路径是这两点的最短路径.因此,在计算最短路径的过程中,对访问过的每个顶点,只需保留起点到该点的最短路径即可.不幸的是,多维代价图模型下,当评分函数是非线性的时候,子路径最优的性质并不成立.因此,目前的方法均不能应用于多维代价图模型下基于函数的最优路径查询问题.该文给出了一个best-first search分支界限法并给出3种优化策略.进一步,给出了一个顶点过滤算法,该算法能从图中过滤掉大部分不属于最优路径的顶点.最后,用真实数据集上的实验验证了算法的有效性.     

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

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

一种计算因特网AS拓扑的最短路径的快速算法

最短路径是因特网AS(autonomous system)拓扑的一个重要特征,AS间的路由路径一般是AS之间的最短路径.因特网服务提供商之间复杂的商业关系导致AS之间存在复杂的路由关系,从而影响AS路由路径的选择,因此在计算AS拓扑中最短路径时需要考虑AS间的路由关系.提出了一种计算AS拓扑中最短路径的算法,算法基于无向图的宽度优先最短路径算法,时间复杂度为O(nm),这里n和m分别为拓扑图中节点和边的个数.通过实验发现,与现有的计算AS拓扑最短路径的时间复杂度为O(n3)的算法相比,该算法在实现同样精确度的前提下大幅缩短了计算时间.     

基于加权标识S-图的最短路径研究

为解决智能交通系统中交通运输网络分析和最短路径问题,提出加权标识S-图最短路径算法。根据Petri网基本原理和加权S-图的特点,给出交通网络加权S-图的网模型。阐述加权标识S-图最短路径的基本原理、求解加权标识S-图的最短路径定理及证明。通过交通运输网络示例和实验对算法进行验证,对比分析算法性能。结果表明,加权标识S-图最短路径算法能够更有效地求解交通网络最短路径。     

求解区间图K-连接最短路径问题的在线算法

针对含有n个区间的区间图K-连接最短路径(K-SP)问题,提出一种求解区间图K-SP问题的在线算法。分析区间图及其最短路径问题的特有性质,利用改进的动态规划算法和贪心算法,优化在线算法的时间复杂度。理论分析结果表明,该算法的时间复杂度为O(nK+nlgn),与目前已知最优的离线算法复杂度相同。     

寻找图中两顶点间最长路径的算法设计

在"图"这种数据结构中,求解任意两顶点之间最长路径算法,有着广泛的理论和应用背景,而其求解算法却研究较少,没有像求解最短路径算法那样有成熟的算法(Dijkstra算法和Floyd算法[1])和广泛的影响.讨论并实现了一种查找图中任意两顶点间带权路径长度中最长路径的算法.使用该算法可以回答图中任意两个顶点之间的最长路径长度及任意两顶点间存在的不同路径的数目.     

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

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

Path Clearance

In military scenarios, agents (i.e., troops of soldiers, convoys, and unmanned vehicles) may often have to traverse environments with only a limited intelligence about the locations of adversaries. We study a particular instance of this problem that we refer to as path clearance problem. In path clearance, an agent has to navigate to its goal as quickly as possible without being detected by an adversary. When picking a path to follow, the agent does not know the precise locations of adversaries. Instead, it has a list of their possible locations, each associated with the probability of containing an adversary. Any of these locations can be sensed by either the agent itself at a distance close enough (provided the agent has a capability of long-range sensing) or by one of the scouts (if they are available). If no adversary is present at a sensed location, the agent can then safely traverse through it. Otherwise, the agent has to take a detour.     

Path Sensitization

For different delay models,the concept of sensitization can be very different.Traditonal concepts of sensitization cannot precisely describe circuit behavior when the input vectors change very fast.Using Boolean process aporoach,this paper presents a new definition of sensitization for arbitrary input waveforms.By this new concept it is found that if the inputs of a combinational circuit can change at any time,and each gate‘s delay varies within an interval (bounded gate delay model),then every path,which is not necessarily a single topological path,is sensitizable.From the experimental results it can be seen that,all nonsensitizable paths for traditional concepts actually can propagate transitions along them for some input waveforms.However,specified time between input transitions(STBIT) and minimum permissible pulse width(ε）are two major factors to make some paths non-sensitizable.     

基于路径索引与编码模式的路径连接

在各种XML查询语言中普遍采用路径表达式来表示对象间的嵌套和引用关系，路径表达式的求解是查询处理中的一个关键问题．本文提出一种基于路径索引与编码模式的路径连接方法，利用路径索引能够以与路径长度成比例的时间求出对象的后代或祖先的目标集，利用编码模式则可以用常数时间确定对象之间的祖先一后代关系．实验结果表明，本文提出的方法具有较高的效率，当对大量对象进行连接以及当路径的长度、路径上结点的出度或入度较大时，本文提出的方法明显优干自顶向下或自底向上遍历的方法。     

Path Summaries and Path Partitioning in Modern XML Databases

XML path summaries are compact structures representing all the simple parent-child paths of an XML document. Such paths have also been used in many works as a basis for partitioning the document’s content in a persistent store, under the form of path indices or path tables. We revisit the notions of path summaries and path-driven storage model in the context of current-day XML databases. This context is characterized by complex queries, typically expressed in an XQuery subset, and by the presence of efficient encoding techniques such as structural node identifiers. We review a path summary’s many uses for query optimization, and given them a common basis, namely relevant paths. We discuss summary-based tree pattern minimization and present some efficient summary-based minimization heuristics. We consider relevant path computation and provide a time- and memory-efficient computation algorithm. We combine the principle of path partitioning with the presence of structural identifiers in a simple path-partitioned storage model, which allows for selective data access and efficient query plans. This model improves the efficiency of twig query processing up to two orders of magnitude over the similar tag-partitioned indexing model. We have implemented the path-partitioned storage model and path summaries in the XQueC compressed database prototype [8]. We present an experimental evaluation of a path summary’s practical feasibility and of tree pattern matching in a path-partitioned store.     

K-Order Surrounding Roadmaps Path Planner for Robot Path Planning

Probabilistic roadmaps are commonly used in robot path planning. Most sampling-based path planners often produce poor-quality roadmaps as they focus on improving the speed of constructing roadmaps without paying much attention to the quality. Poor-quality roadmaps can cause problems such as poor-quality paths, time-consuming path searching and failures in the searching. This paper presents a K-order surrounding roadmap (KSR) path planner which constructs a roadmap in an incremental manner. The planner creates a tree while answering a query, selects the part of the tree according to quality measures and adds the part to an existing roadmap which is obtained in the same way when answering the previous queries. The KSR path planner is able to construct high-quality roadmaps in terms of good coverage, high connectivity, provision of alternative paths and small size. Comparison between the KSR path planner and Reconfigurable Random Forest (RRF), an existing incremental path planner, as well as traditional probabilistic roadmap (PRM) path planner shows that the roadmaps constructed using the KSR path planner have higher quality that those that are built by the other planners.     

路径表达式的构造方法及路径测试

软件测试是软件设计中一个重要阶段,也是保证软件可靠性的重要手段。路径测试是软件测试中一种重要方法,而测试的关键是确定路径数目和设计测试用例。程序路径表达式是路径测试中路径的一种表示方法。本文讨论了利用程序图进行路径测试中的路径表达式的构造方法。     

路径测试中基本路径集的自动生成

路径测试是一种重要的白盒测试技术，具有较高的故障覆盖率。基本路径集覆盖了程序中所有语句和分支，该文测试了基本路径集中的路径，在测试资源有限的情况下得到较好的测试效果，并提出了基于图的深度优先搜索的基本路径集的生成方法，该算法采用的生成子路径的方法可以有效地减少路径生成过程中的搜索过程，提高路径生成的效率。 关键词：     

Path Coordinates in a 3D Path Following Problem

Two approaches to 3D path coordinates used when solving a path following problem for aerial vehicles are proposed. The first approach lies in reducing the problem to a two-dimensional case by projection. The second approach is based on introducing an adaptive frame at the target point. The choice of the adaptive frame determines the complexity of the algorithm of the control synthesis. It is shown that the parallel transport frame, or the Bishop frame, is most convenient.