共查询到20条相似文献,搜索用时 31 毫秒
1.
Steven Y. Susswein Thomas C. Henderson Joseph L. Zachary Chuck Hansen Paul Hinker Gary C. Marsden 《International journal of parallel programming》1991,20(6):453-473
Filtering algorithms are well accepted as a means of speeding up the solution of the consistent labeling problem (CLP). Despite the fact that path consistency does a better job of filtering than arc consistency, AC is still the preferred technique because it has a much lower time complexity. We are implementing parallel path consistency algorithms on multiprocessors and comparing their performance to the best sequential and parallel arc consistency algorithms.(1,2) (See also work by Kerethoet al.
(3) and Kasif(4)) Preliminary work has shown linear performance increases for parallelized path consistency and also shown that in many cases performance is significantly better than the theoretical worst case. These two results lead us to believe that parallel path consistency may be a superior filtering technique. Finally, we have implemented path consistency as an outer product computation and have obtained good results (e.g., linear speedup on a 64K-node Connection Machine 2). 相似文献
2.
Michael J. Swain 《International journal of parallel programming》1988,17(6):523-528
Samal and Henderson claim that any parallel algorithm for enforcing arc consistency in the worst case must have (na) sequential steps, wheren is the number of nodes, anda is the number of labels per node. We argue that Samal and Henderson's argument makes assumptions about how processors are used and give a counterexample that enforces arc consistency in a constant number of steps usingO(n[su2a22na) processors. It is possible that the lower bound holds for a polynomial number of processors; if such a lower bound were to be proven it would answer an important open question in theoretical computer science concerning the relation between the complexity classesP andNC. The strongest existing lower bound for the arc consistency problem states that it cannot be solved in polynomial log time unlessP=NC. 相似文献
3.
《Artificial Intelligence》1986,28(2):225-233
Mackworth and Freuder have analyzed the time complexity of several constraint satisfaction algorithms [5]. We present here new algorithms for arc and path consistency and show that the arc consistency algorithm is optimal in time complexity and of the same-order space complexity as the earlier algorithms. A refined solution for the path consistency problem is proposed. However, the space complexity of the path consistency algorithm makes it practicable only for small problems. These algorithms are the result of the synthesis techniques used in alice (a general constraint satisfaction system) and local consistency methods [3]. 相似文献
4.
5.
Bernard A. Nadel 《Computational Intelligence》1989,5(3):188-224
Constraint satisfaction problems are ubiquitous in artificial intelligence and many algorithms have been developed for their solution. This paper provides a unified survey of some of these, in terms of three classes: (i) tree search, (ii) arc consistency (AC), and (iii) hybrid tree search/arc consistency algorithms. It is shown that several important algorithms, when slightly rearranged, are of the latter hybrid form, but with arc consistency components that do not necessarily achieve full arc consistency at the tree nodes. Accordingly, we define several new partial AC procedures, AC1/5, AC1/4, AC1/3, and AC½, analogous to the well-known full AC algorithms which Mackworth has called AC1, AC2, and AC3. The fractional suffixes on our AC algorithms are roughly proportional to the degree of partial arc consistency they achieve. Unlike traditional versions, our AC algorithms (full and partial) are presented in a parameterized form to allow them to be embedded efficiently at the nodes of a tree search process. Algorithm complexities are compared empirically, using the n-queens problem and a new version called confused n-queens. Gaschnig's Backmarking (a tree search algorithm) and Haralick's Forward Checking (a hybrid algorithm) are found to be the most efficient. For the hybrid algorithms, we find that it pays to do little arc consistency processing at the nodes, incurring more nodes, but sufficiently reducing the work per node so as to obtain less work over the whole tree. The unified view taken here suggests several new algorithms. Preliminary results show one of these to be the best algorithm so far. 相似文献
6.
《Artificial Intelligence》1985,25(1):65-74
Constraint satisfaction problems play a central role in artificial intelligence. A class of network consistency algorithms for eliminating local inconsistencies in such problems has previously been described. We analyze the time complexity of several node, arc and path consistency algorithms and prove that arc consistency is achievable in time linear in the number of binary constraints. The Waltz filtering algorithm is a special case of the arc consistency algorithm. In the edge labelling computational vision application the constraint graph is planar and so the time complexity is linear in the number of variables. 相似文献
7.
Max Restricted Path Consistency (maxRPC) is a local consistency for binary constraints that enforces a higher order of consistency
than arc consistency. Despite the strong pruning that can be achieved, maxRPC is rarely used because existing maxRPC algorithms
suffer from overheads and redundancies as they can repeatedly perform many constraint checks without triggering any value
deletions. In this paper we propose and evaluate techniques that can boost the performance of maxRPC algorithms by eliminating
many of these overheads and redundancies. These include the combined use of two data structures to avoid many redundant constraint
checks, and the exploitation of residues to quickly verify the existence of supports. Based on these, we propose a number
of closely related maxRPC algorithms. The first one, maxRPC3, has optimal O(end
3) time complexity, displays good performance when used stand-alone, but is expensive to apply during search. The second one,
maxRPC3
rm
, has O(en
2
d
4) time complexity, but a restricted version with O(end
4) complexity can be very efficient when used during search. The other algorithms are simple modifications of maxRPC3
rm
. All algorithms have O(ed) space complexity when used stand-alone. However, maxRPC3 has O(end) space complexity when used during search, while the others retain the O(ed) complexity. Experimental results demonstrate that the resulting methods constantly outperform previous algorithms for maxRPC,
often by large margins, and constitute a viable alternative to arc consistency on some problem classes. 相似文献
8.
Computing an optimal solution to the knapsack problem is known to be NP-hard. Consequently, fast parallel algorithms for finding such a solution without using an exponential number of processors appear unlikely. An attractive alternative is to compute an approximate solution to this problem rapidly using a polynomial number of processors. In this paper, we present an efficient parallel algorithm for finding approximate solutions to the 0–1 knapsack problem. Our algorithm takes an , 0 < < 1, as a parameter and computes a solution such that the ratio of its deviation from the optimal solution is at most a fraction of the optimal solution. For a problem instance having n items, this computation uses O(n5/2/3/2) processors and requires O(log3n + log2nlog(1/)) time. The upper bound on the processor requirement of our algorithm is established by reducing it to a problem on weighted bipartite graphs. This processor complexity is a significant improvement over that of other known parallel algorithms for this problem. 相似文献
9.
Hossam ElGindy 《International journal of parallel programming》1986,15(5):389-398
Previous research on developing parallel triangulation algorithms concentrated on triangulating planar point sets.O(log3
n) running time algorithms usingO(n) processors have been developed in Refs. 1 and 2. Atallah and Goodrich(3) presented a data structure that can be viewed as a parallel analogue of the sequential plane-sweeping paradigm, which can be used to triangulate a planar point set inO(logn loglogn) time usingO(n) processors. Recently Merks(4) described an algorithm for triangulating point sets which runs inO(logn) time usingO(n) processors, and is thus optimal. In this paper we develop a parallel algorithm for triangulating simplicial point sets in arbitrary dimensions based on the idea of the sequential algorithm presented in Ref. 5. The algorithm runs inO(log2
n) time usingO(n/logn) processors. The algorithm hasO(n logn) as the product of the running time and the number of processors; i.e., an optimal speed-up. 相似文献
10.
RNA二级结构预测中动态规划的优化和有效并行 总被引:6,自引:0,他引:6
基于最小自由能模型的方法是计算生物学中RNA二级结构预测的主要方法,而计算最小自由能的动态规划算法需要O(n4)的时间,其中n是RNA序列的长度.目前有两种降低时间复杂度的策略:限制二级结构中内部环的大小不超过k,得到O(n2×k2)算法;Lyngso方法根据环的能量规则,不限制环的大小,在O(n3)的时间内获得近似最优解.通过使用额外的O(n)的空间,计算内部环中的冗余计算大为减少,从而在同样不限制环大小的情况下,在O(n3)的时间内能够获得最优解.然而,优化后的算法仍然非常耗时,通过有效的负载平衡方法,在机群系统上实现并行程序.实验结果表明,并行程序获得了很好的加速比. 相似文献
11.
L. Chen 《Algorithmica》1997,17(3):266-280
Based on Tucker's work, we present an accurate proof of the characterization of proper circular arc graphs and obtain the
first efficient parallel algorithm which not only recognizes proper circular arc graphs but also constructs proper circular
arc representations. The algorithm runs inO(log2
n) time withO(n
3) processors on a Common CRCW PRAM. The sequential algorithm can be implemented to run inO(n
2) time and is optimal if the input graph is given as an adjacency matrix, so to speak.
Portions of this paper appear in preliminary form in theProceedings of the 1989Workshop on Algorithms and Data Structures [2], and theProceedings of the 1994International Symposium on Algorithms and Computation [5]. 相似文献
12.
A planar monotone circuit (PMC) is a Boolean circuit that can be embedded in the plane and that contains only AND and OR
gates. A layered PMC is a PMC in which all input nodes are in the external face, and the gates can be assigned to layers in
such a way that every wire goes between gates in successive layers. Goldschlager, Cook and Dymond, and others have developed
NC
2
algorithms to evaluate a layered PMC when the output node is in the same face as the input nodes. These algorithms require
a large number of processors (Ω(n
6
), where n is the size of the input circuit).
In this paper we give an efficient parallel algorithm that evaluates a layered PMC of size n in time using only a linear number of processors on an EREW PRAM. Our parallel algorithm is the best possible to within a polylog
factor, and is a substantial improvement over the earlier algorithms for the problem.
Received April 18, 1994; revised April 7, 1995. 相似文献
13.
The AtMostSeqCard constraint is the conjunction of a cardinality constraint on a sequence of n variables and of n???q?+?1 constraints AtMost u on each subsequence of size q. This constraint is useful in car-sequencing and crew-rostering problems. In van Hoeve et al. (Constraints 14(2):273–292, 2009), two algorithms designed for the AmongSeq constraint were adapted to this constraint with an O(2 q n) and O(n 3) worst case time complexity, respectively. In Maher et al. (2008), another algorithm similarly adaptable to filter the AtMostSeqCard constraint with a time complexity of O(n 2) was proposed. In this paper, we introduce an algorithm for achieving arc consistency on the AtMostSeqCard constraint with an O(n) (hence optimal) worst case time complexity. Next, we show that this algorithm can be easily modified to achieve arc consistency on some extensions of this constraint. In particular, the conjunction of a set of m AtMostSeqCard constraints sharing the same scope can be filtered in O(nm). We then empirically study the efficiency of our propagator on instances of the car-sequencing and crew-rostering problems. 相似文献
14.
This paper presents several algorithms for projecting points so as to give the most uniform distribution. Givenn points in the plane and an integerb, the problem is to find an optimal angle ofb equally spaced parallel lines such that points are distributed most uniformly over buckets (regions bounded by two consecutive lines). An algorithm is known only in thetight case in which the two extreme lines are the supporting lines of the point set. The algorithm requiresO(bn2 logn) time and On2+bn) space to find an optimal solution. In this paper we improve the algorithm both in time and space, based on duality transformation. Two linear-space algorithms are presented. One runs in On2+K log n+bn) time, whereK is the number of intersections in the transformed plane.K is shown to beO(@#@ n2+bn@#@) based on a new counting scheme. The other algorithm is advantageous ifb < n. It performs a simplex range search in each slab to enumerate all the lines that intersectbucket lines, and runs in O(b0.610n1.695+K logn) time. It is also shown that the problem can be solved in polynomial time even in therelaxed case. Its one-dimensional analogue is especially related to the design of an optimal hash function for a static set of keys.This work was supported in part by a Grant in Aid for Scientific Research of the Ministry of Education, Science, and Cultures of Japan. 相似文献
15.
布尔可满足性问题(SAT)是指对于给定的布尔公式,是否存在一个可满足的真值指派.这是第1个被证明的NP完全问题,一般认为不存在多项式时间算法,除非P=NP.学者们大都研究了子句长度不超过k的SAT问题(k-SAT),从全局搜索到局部搜索,给出了大量的相对有效算法,包括随机算法和确定算法.目前,最好算法的时间复杂度不超过O((2-2/k)n),当k=3时,最好算法时间复杂度为O(1.308n).而对于更一般的与子句长度k无关的SAT问题,很少有文献涉及.引入了一类可分离SAT问题,即3-正则可分离可满足性问题(3-RSSAT),证明了3-RSSAT是NP完全问题,给出了一般SAT问题3-正则可分离性的O(1.890n)判定算法.然后,利用矩阵相乘算法的研究成果,给出了3-RSSAT问题的O(1.890n)精确算法,该算法与子句长度无关. 相似文献
16.
We study the complexity of routing a set of messages with multiple destinations (multicast routing) on an n-node square mesh under the store-and-forward model. A standard argument proves that
time is required to route n messages, where each message is generated by a distinct node and at most c messages are to be delivered to any individual node. The obvious approach of simply replicating each message into the appropriate
number of unicast (single-destination) messages and routing these independently does not yield an optimal algorithm. We provide
both randomized and deterministic algorithms for multicast routing, which use constant-size buffers at each node. The randomized
algorithm attains optimal performance, while the deterministic algorithm is slower by a factor of O( log 2
n). We also describe an optimal deterministic algorithm that, however, requires large buffers of size O(c).
A preliminary version of this paper appeared in Proceedings of the 13th Annual ACM Symposium on Parallel Algorithms and Architectures,
Crete, Greece, 2001. This work was supported, in part, by MIUR under project ALGO-NEXT. 相似文献
17.
18.
Boolean networks provide a simple and intuitive model for gene regulatory networks, but a critical defect is the time required
to learn the networks. In recent years, efficient network search algorithms have been developed for a noise-free case and
for a limited function class. In general, the conventional algorithm has the high time complexity of O(22k
mn
k+1) where m is the number of measurements, n is the number of nodes (genes), and k is the number of input parents. Here, we suggest a simple and new approach to Boolean networks, and provide a randomized
network search algorithm with average time complexity O
(mn
k+1/ (log m)(k−1)). We show the efficiency of our algorithm via computational experiments, and present optimal parameters. Additionally, we
provide tests for yeast expression data.
Editor: David Page 相似文献
19.
Efficient Graph-Theoretic Algorithms on a Linear Array with a Reconfigurable Pipelined Bus System 总被引:1,自引:0,他引:1
Amitava Datta 《The Journal of supercomputing》2002,23(2):193-211
We present efficient algorithms for solving several fundamental graph-theoretic problems on a Linear Array with a Reconfigurable Pipelined Bus System (LARPBS), one of the recently proposed models of computation based on optical buses. Our algorithms include finding connected components, minimum spanning forest, biconnected components, bridges and articulation points for an undirected graph. We compute the connected components and minimum spanning forest of a graph in O(log n) time using O(m+n) processors where m and n are the number of edges and vertices in the graph and m=O(n
2) for a dense graph. Both the processor and time complexities of these two algorithms match the complexities of algorithms on the Arbitrary and Priority CRCW PRAM models which are two of the strongest PRAM models. The algorithms for these two problems published by Li et al. [7] have been considered to be the most efficient on the LARPBS model till now. Their algorithm [7] for these two problems require O(log n) time and O(n
3/log n) processors. Hence, our algorithms have the same time complexity but require less processors. Our algorithms for computing biconnected components, bridges and articulation points of a graph run in O(log n) time on an LARPBS with O(n
2) processors. No previous algorithm was known for these latter problems on the LARPBS. 相似文献
20.
A new, parallel approach for generating Bresenham-type lines is developed. Coordinate pairs which approximate straight lines on a square grid are derived from line equations. These pairs serve as a basis for the development of four new parallel algorithms. One of the algorithms uses the fact that straight time generation is equivalent to a vector prefix sums calculation. The algorithms execute on a binary tree of processors. Each node in the tree performs a simple calculation that involves only additions and shifts. All four algorithms have time complexityO(log2
n) wheren in the form 2
m
denotes the number of points generated andn-1 is the number of processors in the tree. This compares toO(n) for Bresenham's algorithm executed on a sequential processor. Pipelining can be used to achieve a constant time per line generation as long as line length is less thann. 相似文献