共查询到20条相似文献,搜索用时 15 毫秒
1.
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. 相似文献
2.
盛红岩 《数字社区&智能家居》2007,(18)
本文主要从QoS度量的可乘性、最小性两个方面对最短路径路由算法进行扩展,从而找出了最可靠、最宽的路径.并通过MATLAB6.1进行了实例仿真. 相似文献
3.
4.
5.
文章针对智能交通系统中最短路径问题,提出了一种基于预处理剪枝的最短路径快速搜索算法。该算法在Dijkstra算法的基础上,利用预处理结果进行剪枝。实验证明,与传统算法相比,在保证最优解的情况下,使用该算法平均可使搜索空间平均降低94.8%,计算速度提高26倍。 相似文献
6.
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. 相似文献
7.
网络中重要节点的发现是研究网络特性的重要方面之一,在复杂网络、系统科学、社会网分析和互联网搜索等领域中具有广泛的应用价值。为提高全网范围内重要节点发现的效率和有效性,提出了一种基于最短路径介数及节点中心接近度的重要节点发现算法,通过最短路径介数的方法确定全网内的重要节点,利用中心接近度分析重要节点的重要性。测试结果表明,与同类的系统比较起来,该方法具有比较好的性能。 相似文献
8.
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. 相似文献
9.
10.
基于计算机视觉的人流量双向统计 总被引:1,自引:0,他引:1
提出了一种采用视频监控系统对人行通道口进行双向人流量计数的方法。首先建立发色模型与头部形状模型,采用形态学运算提取人的头部目标,然后跟踪目标建立人头目标移动链,依据目标链位置信息判别行人的进出方向,最后设置感兴趣的检测区域,并对通过该检测区域的行人计数。实验结果表明,该方法能实时有效地统计通道口处双向人流量。 相似文献
11.
12.
A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs 总被引:1,自引:0,他引:1
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. 相似文献
13.
14.
Chen Yu-qiang Guo Jian-lan Yang Huaide Wang Zheng-qin Liu Hong-ling 《The Journal of supercomputing》2021,77(2):1958-1975
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.
相似文献15.
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. 相似文献
16.
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... 相似文献
17.
18.
Youshen Xia Jun Wang 《Automatic Control, IEEE Transactions on》2000,45(11):2129-2134
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. 相似文献
19.
以基于图像序列摄像机自标定为基础,针对尺度不变特征转换SIFT算法误匹配率高且运行效率低的问题,提出一种改进的双向SIFT特征匹配算法。在去除误匹配方面,首先采用双向匹配消除部分误匹配点对,然后结合视差梯度约束算法和随机抽样一致性RANSAC算法提纯匹配点对;在提高运行速度方面,首先在初匹配中采用K邻近算法,其次调整视差梯度约束迭代条件,都通过减少迭代次数来降低算法耗时。实验表明,改进后的算法在去除了大部分误匹配的基础上,保留了足够的匹配点对以用于摄像机空间位置和姿态的自动标定,且相较SIFT算法在运行速度上有了较大的改进。 相似文献
20.
Thomas Zeugmann 《Annals of Mathematics and Artificial Intelligence》1998,23(1-2):117-145
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. 相似文献