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

动态网络最短路径是交通、通信等系统中的重要问题。在处理多链路权值变大时,多链路权值增大的动态最短路径算法可有效地减少单链路权值增大动态最短路径算法的冗余计算。目前,多链路权值增大的动态最短路径算法的研究较少,尚未存在有效的多链路变大的动态最短路径算法。通过对现有动态最短路径算法的深入研究,提出了一种多链路权值增大的动态最短路径算法(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)。通过一些数据的检测,验证了在机器人路径规划中,尤其是在测试数据较多的情况下,该算法可以有效提高效率。     

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

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

一种优化Dijkstra算法的研究

阐述传统最短路径算法的优缺点,提出对传统寻路问题的优化算法,旨在解决节点较多网络的最短路径问题。比较优化算法与传统算法的搜索效率,以及优化算法之间的异同,测试表明,优化后的算法在效率方面具有明显的优越性。为了验证算法的有效性,最后给出鲁东大学的一个具体应用。     

A fast algorithm for computing sparse visibility graphs

AnO(¦E¦log² n) algorithm is presented to construct the visibility graph for a collection ofn nonintersecting line segments, where ¦E¦ is the number of edges in the visibility graph. This algorithm is much faster than theO(n ²)-time andO(n ²)-space algorithms by Asanoet al., and by Welzl, on sparse visibility graphs. Thus we partially resolve an open problem raised by Welzl. Further, our algorithm uses onlyO(n) working storage.     

A new variant of the A*-algorithm which closes a node at most once

We describe a new variant of the well-known A^*-algorithm which computes a shortest path from a start-nodes to a goal-nodeg in a state-graph. Two important features of the new algorithm are: (1) It closes a node only when a shortest path to that node is found; in particular, a node is closed at most once. (2) It combines an under-estimator together with an over-estimator to improve the efficiency of the search. If _K is the set of nodes closed by the new algorithm, then , where _* and _D are the sets of nodes closed by the A^*-algorithm and Dijkstra's shortest-path algorithm, respectively. The new algorithm can be considered to be a generalization of the A^*-algorithm in that it coincides with the A^*-algorithm when the under-estimator satisfies the triangle inequality.An earlier version of this paper appeared in Proc. Int. Computer Conf. '88, Artificial Intelligence: Theory and Applications, Dec. 1988, Hongkong.     

Solving shortest paths efficiently on nearly acyclic directed graphs

Shortest path problems can be solved very efficiently when a directed graph is nearly acyclic. Earlier results defined a graph decomposition, now called the 1-dominator set, which consists of a unique collection of acyclic structures with each single acyclic structure dominated by a single associated trigger vertex. In this framework, a specialised shortest path algorithm only spends delete-min operations on trigger vertices, thereby making the computation of shortest paths through non-trigger vertices easier. A previously presented algorithm computed the 1-dominator set in O(mn) worst-case time, which allowed it to be integrated as part of an O(mn+nrlogr) time all-pairs algorithm. Here m and n respectively denote the number of edges and vertices in the graph, while r denotes the number of trigger vertices. A new algorithm presented in this paper computes the 1-dominator set in just O(m) time. This can be integrated as part of the O(m+rlogr) time spent solving single-source, improving on the value of r obtained by the earlier tree-decomposition single-source algorithm. In addition, a new bidirectional form of 1-dominator set is presented, which further improves the value of r by defining acyclic structures in both directions over edges in the graph. The bidirectional 1-dominator set can similarly be computed in O(m) time and included as part of the O(m+rlogr) time spent computing single-source. This paper also presents a new all-pairs algorithm under the more general framework where r is defined as the size of any predetermined feedback vertex set of the graph, improving the previous all-pairs time complexity from O(mn+nr²) to O(mn+r³).     

一种考虑障碍物的ad hoc网络分簇算法

现有的很多ad hoc网络分簇算法都没有考虑实际的物理环境因素,如地球表面的各种障碍物。而障碍物既阻碍节点移动,又限制无线传输,对分簇结果影响很大,可能会导致簇的尺寸过小,簇的数目较多,从而引入大量的通信和计算开销。结合Voronoi图,在最小ID启发式算法的基础上,提出一种考虑障碍物的分簇算法。通过设置备用节点,可以解决障碍物环境下ad hoc网络的连接性问题。最后通过实例仿真对该算法和最小ID算法进行性能比较和评价。     

A Branch-Checking Algorithm for All-Pairs Shortest Paths

We formulate and study an algorithm for all-pairs shortest paths in a network with $n $ nodes and $m $ arcs of positive length. Using the dynamic programming principle of optimality of subpaths the algorithm avoids redundant updates of distance labels. A shortest $v$--$w$ path, say $\langle v, r_{1} , r_{2} , \ldots , r_{k } = w \rangle$ with $k $ arcs ($k \geq 1$), is only then combined with an arc $(w,t) \in A$ to update the distance label of pair $v$--$t$, if $(w,t) $ is present on the shortest $r_{\ell } $--$ t$ path for each node $r_{\ell}$ $(\ell=k- 1 , k- 2, \ldots, 1) $. The algorithm extracts shortest paths in order of length from a data structure and builds two shortest path trees per node, an extra effort of $O(n^{2})$. This way it can execute efficiently only the aforementioned distance updates, by picking the arcs $(w,t)$ out of these trees. The time complexity order per distance update and path extraction is similar as in other algorithms. An implementation with a data structure of heaps is possible, but a bucket-type data structure may be more appropriate. The implied number of distance updates does not exceed $nm_{0}$ ($m_{0}$ being the total number of shortest path arcs), but is frequently much lower. In extreme cases the new algorithm applies $O(n^{2})$ distance updates, whereas known algorithms require $\Omega( n ^{3})$ updates. The algorithm is especially suited for undirected graphs; here the construction of one tree per node is sufficient and the computation times halve.     

A Branch-Checking Algorithm for All-Pairs Shortest Paths

We formulate and study an algorithm for all-pairs shortest paths in a network with $n $ nodes and $m $ arcs of positive length. Using the dynamic programming principle of optimality of subpaths the algorithm avoids redundant updates of distance labels. A shortest $v$--$w$ path, say $\langle v, r_{1} , r_{2} , \ldots , r_{k } = w \rangle$ with $k $ arcs ($k \geq 1$), is only then combined with an arc $(w,t) \in A$ to update the distance label of pair $v$--$t$, if $(w,t) $ is present on the shortest $r_{\ell } $--$ t$ path for each node $r_{\ell}$ $(\ell=k- 1 , k- 2, \ldots, 1) $. The algorithm extracts shortest paths in order of length from a data structure and builds two shortest path trees per node, an extra effort of $O(n^{2})$. This way it can execute efficiently only the aforementioned distance updates, by picking the arcs $(w,t)$ out of these trees. The time complexity order per distance update and path extraction is similar as in other algorithms. An implementation with a data structure of heaps is possible, but a bucket-type data structure may be more appropriate. The implied number of distance updates does not exceed $nm_{0}$ ($m_{0}$ being the total number of shortest path arcs), but is frequently much lower. In extreme cases the new algorithm applies $O(n^{2})$ distance updates, whereas known algorithms require $\Omega( n ^{3})$ updates. The algorithm is especially suited for undirected graphs; here the construction of one tree per node is sufficient and the computation times halve.     

基于遗传算法的曲面最短路径求解

对曲面上两点间最短路径的求解是一个应用非常广泛,但理论求解困难的问题。遗传算法是一种新型的、较成熟的全局随机搜索算法,具有优良的性态。该文将遗传算法引入到曲面最短路径寻优的问题中。首先在离散化的模拟数字高程上依据起点和终点,以实数编码产生一系列初始群体,定义相应的适应度函数,然后对群体进行复制、交叉和变异等操作,求解出一条曲面上两点间的最短路径。在文章的最后给出了一个数值仿真实例来了证明该算法的有效性和实用性。     

求解多段图问题的并行动态规划算法

多段图问题是一类特殊的单源最短路径问题。在串行动态规划算法的两种实现方法的基础上,根据图中顶点的编号,提出两种在集群环境下进行任务分割的并行化求解方法,并使用MPI进行实现。实验结果表明,所提出的算法具有较高的加速比和较低的通信复杂度、时间复杂度。算法不限于某种结构的集群,通用性强。