A bidirectional shortest-path algorithm with good average-case behavior

The two-terminal shortest-path problem asks for the shortest directed path from a specified nodes to a specified noded in a complete directed graphG onn nodes, where each edge has a nonnegative length. We show that if the length of each edge is chosen independently from the exponential distribution, and adjacency lists at each node are sorted by length, then a priority-queue implementation of Dijkstra's unidirectional search algorithm has the expected running time (n logn). We present a bidirectional search algorithm that has expected running time (n logn). These results are generalized to apply to a wide class of edge-length distributions, and to sparse graphs. If adjacency lists are not sorted, bidirectional search has the expected running time (an) on graphs of average degreea, as compared with (an) for unidirectional search.     

最短路径路由算法的扩展

本文主要从QoS度量的可乘性、最小性两个方面对最短路径路由算法进行扩展,从而找出了最可靠、最宽的路径.并通过MATLAB6.1进行了实例仿真.     

一种实用的所有点对之间最短路径并行算法

针对有向图中每对顶点之间的最短路径问题,在基于扩充了路径矩阵的串行Floyd算法上,提出了二维网格结构上的并行算法。选用的任务划分方法为二维均匀块分配方法。该并行算法已经在NOW上的MPI平台上实现,理论分析和数值实验表明它具有较高的扩展性和并行效率。     

智能交通中的高效最短路径搜索算法

文章针对智能交通系统中最短路径问题,提出了一种基于预处理剪枝的最短路径快速搜索算法。该算法在Dijkstra算法的基础上,利用预处理结果进行剪枝。实验证明,与传统算法相比,在保证最优解的情况下,使用该算法平均可使搜索空间平均降低94.8%,计算速度提高26倍。     

A satisfiability algorithm and average-case hardness for formulas over the full binary basis

We present a moderately exponential time algorithm for the satisfiability of Boolean formulas over the full binary basis. For formulas of size at most cn, our algorithm runs in time ${2^{(1-\mu_{c})n}}$ for some constant μ _c  > 0. As a byproduct of the running time analysis of our algorithm, we obtain strong average-case hardness of affine extractors for linear-sized formulas over the full binary basis.     

一种基于最短路径介数的重要节点发现算法

网络中重要节点的发现是研究网络特性的重要方面之一,在复杂网络、系统科学、社会网分析和互联网搜索等领域中具有广泛的应用价值。为提高全网范围内重要节点发现的效率和有效性,提出了一种基于最短路径介数及节点中心接近度的重要节点发现算法,通过最短路径介数的方法确定全网内的重要节点,利用中心接近度分析重要节点的重要性。测试结果表明,与同类的系统比较起来,该方法具有比较好的性能。     

An algorithm for shortest-path motion in three dimensions

We describe a fully polynomial approximation scheme for the problem of finding the shortest distance between two points in three-dimensional space in the presence of polyhedral obstacles. The fastest algorithm known for the exact solution of this problem is doubly exponential.     

游戏引擎最短路径搜索优化遗传算法设计

为满足游戏地图中最短路径搜索求解, 提出了一种优化的自适应遗传算法。该算法采用与游戏地图中节点数和弧段数相关联的节点复杂度算子, 结合种群的整体情况和进化潜力来设定自适应遗传算法的交叉率和变异率。实验表明, 该算法避免了搜索结果陷入局部最优解, 确保最短路径的搜索成功率及提高搜索速度, 在游戏引擎设计中具有一定的实用价值。     

基于计算机视觉的人流量双向统计

提出了一种采用视频监控系统对人行通道口进行双向人流量计数的方法。首先建立发色模型与头部形状模型,采用形态学运算提取人的头部目标,然后跟踪目标建立人头目标移动链,依据目标链位置信息判别行人的进出方向,最后设置感兴趣的检测区域,并对通过该检测区域的行人计数。实验结果表明,该方法能实时有效地统计通道口处双向人流量。     

A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs

We give a linear time and space algorithm for analyzing trees in planar graphs. The algorithm can be used to analyze the sensitivity of a minimum spanning tree to changes in edge costs, to find its replacement edges, and to verify its minimality. It can also be used to analyze the sensitivity of a single-source shortest-path tree to changes in edge costs, and to analyze the sensitivity of a minimum-cost network flow. The algorithm is simple and practical. It uses the properties of a planar embedding, combined with a heap-ordered queue data structure.This research was partially supported by Office of Naval Research Grant N00014-87-K-0467 and National Science Foundation Grant CCR-8610181.This research was done while the author was at the Department of Computer Science, Princeton University, Princeton, NJ 08544, USA.This research was done while the author was at the Department of Computer Science, Stanford University, Stanford, CA 94305, USA.     

Research on navigation of bidirectional A* algorithm based on ant colony algorithm

To overcome the lengthy search time, massive space occupation, and overlong planned path of the traditional A* algorithm, this paper integrates the bidirectional search with the intelligent ant colony algorithm to obtain the heuristic function selection factor, and uses the factor to improve the evaluation function of the algorithm. The simulation results show that the improved algorithm achieved better dynamic navigation than the traditional A* algorithm both in search time and distance, featuring shorter path searching time and the algorithm running time. Therefore, the result of this research has effectively reduced the search time and enhanced the dynamic search.

     

A bi-objective approach for shortest-path network interdiction

In the literature, solution approaches to the shortest-path network interdiction problem have been developed for optimizing a single figure-of-merit of the network configuration when considering limited amount of resources available to interdict network links. This paper presents a newly developed evolutionary algorithm that allows approximating the optimal Pareto set of network interdiction strategies when considering bi-objective shortest path problems. Thus, the paper considers the concurrent optimization of two objectives: (1) maximization of shortest-path length and (2) minimization of interdiction strategy cost. Also, the paper considers the transformation of the first objective into the minimization of the most reliable path reliability. To solve these multi-objective optimization problems, an evolutionary algorithm has been developed. This algorithm is based on Monte Carlo simulation, to generate potential network interdiction strategies, graph theory to analyze strategies’ shortest path or most reliable path and, an evolutionary search driven by the probability that a link will appear in the optimal Pareto set. Examples for different sizes of networks and network behavior are used throughout the paper to illustrate and validate the approach.     

A reversible data hiding algorithm based on bidirectional difference expansion

Multimedia Tools and Applications - After the extraction of hidden data, reversible data hiding (RDH) algorithms are able to completely recover the original image without any error. For the past...     

自适应双向菌群优化算法

提出了自适应双向菌群优化算法,应用聚类思想将趋化步长进行自适应调整,提高算法的局部搜索能力,引入双向游动机制,提高了算法的搜索效率和速度。针对10个复杂Benchmark函数进行了数值优化实验,其结果表明,在所有测试函数中,该算法在搜索能力和稳定性等方面优于其他典型算法的比率达到60%～90%,验证了算法的有效性。     

A discrete-time recurrent neural network for shortest-path routing

Presents a discrete-time recurrent neural network, with a fixed step parameter, for solving the shortest path problem. The proposed discrete-time recurrent neural network with a simple architecture is proven to be globally convergent to exact optimal solutions and is suitable for hardware implementation. Furthermore, an improved network with a larger step size independent of the problem size is proposed to increase its convergence rate. The performance and operating characteristics of the proposed neural network are demonstrated by means of simulation results.     

改进的双向SIFT特征匹配算法

以基于图像序列摄像机自标定为基础,针对尺度不变特征转换SIFT算法误匹配率高且运行效率低的问题,提出一种改进的双向SIFT特征匹配算法。在去除误匹配方面,首先采用双向匹配消除部分误匹配点对,然后结合视差梯度约束算法和随机抽样一致性RANSAC算法提纯匹配点对;在提高运行速度方面,首先在初匹配中采用K邻近算法,其次调整视差梯度约束迭代条件,都通过减少迭代次数来降低算法耗时。实验表明,改进后的算法在去除了大部分误匹配的基础上,保留了足够的匹配点对以用于摄像机空间位置和姿态的自动标定,且相较SIFT算法在运行速度上有了较大的改进。     

Lange and Wiehagen's pattern language learning algorithm: An average-case analysis with respect to its total learning time

The present paper deals with the best-case, worst-case and average-case behavior of Lange and Wiehagen's (1991) pattern language learning algorithm with respect to its total learning time. Pattern languages have been introduced by Angluin (1980) and are defined as follows: Let be any non-empty finite alphabet containing at least two elements. Furthermore, let be an infinite set of variables such that . Patterns are non-empty strings over . L(π), the language generated by pattern π, is the set of strings which can be obtained by substituting non-null strings from for the variables of the pattern π. Lange and Wiehagen's (1991) algorithm learns the class of all pattern languages in the limit from text. We analyze this algorithm with respect to its total learning time behavior, i.e., the overall time taken by the algorithm until convergence. For every pattern π containing k different variables it is shown that the total learning time is in the best-case and unbounded in the worst-case. Furthermore, we estimate the expectation of the total learning time. In particular, it is shown that Lange and Wiehagen's algorithm possesses an expected total learning time of with respect to the uniform distribution. This revised version was published online in June 2006 with corrections to the Cover Date.