首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 15 毫秒
1.
This is the first of two papers presenting and evaluating the power of a new framework for combinatorial optimization in graphical models, based on AND/OR search spaces. We introduce a new generation of depth-first Branch-and-Bound algorithms that explore the AND/OR search tree using static and dynamic variable orderings. The virtue of the AND/OR representation of the search space is that its size may be far smaller than that of a traditional OR representation, which can translate into significant time savings for search algorithms. The focus of this paper is on linear space search which explores the AND/OR search tree. In the second paper we explore memory intensive AND/OR search algorithms. In conjunction with the AND/OR search space we investigate the power of the mini-bucket heuristics in both static and dynamic setups. We focus on two most common optimization problems in graphical models: finding the Most Probable Explanation in Bayesian networks and solving Weighted CSPs. In extensive empirical evaluations we demonstrate that the new AND/OR Branch-and-Bound approach improves considerably over the traditional OR search strategy and show how various variable ordering schemes impact the performance of the AND/OR search scheme.  相似文献   

2.
While volunteer computing, as a restricted model of parallel computing, has proved itself to be a successful paradigm of scientific computing with excellent benefit on cost efficiency and public outreach, many problems it solves are intrinsically highly parallel. However, many efficient algorithms, including backtracking search, take the form of a tree search on an extremely uneven tree that cannot be easily parallelized efficiently in the volunteer computing paradigm. We explore in this article how to perform such searches efficiently on volunteer computing projects. We propose a parallel tree search scheme, and we describe two examples of its real-world implementation, Harmonious Tree and Odd Weird Search, both carried out at the volunteer computing project yoyo@home. To confirm the observed efficiency of our scheme, we perform a mathematical analysis, which proves that, under reasonable assumption that agrees with experimental observation, our scheme is only a constant multiplicative factor away from perfect parallelism. Details on improving the overall performance are also discussed.  相似文献   

3.
Branch-and-bound algorithms are organized and intelligently structured searches of solutions in a combinatorially large problem space. In this paper, we propose an approximate stochastic model of branch-and-bound algorithms with a best-first search. We have estimated the average memory space required and have predicted the average number of subproblems expanded before the process terminates. Both measures are exponentials of sublinear exponent. In addition, we have also compared the number of subproblems expanded in a best-first search to that expanded in a depth-first search. Depth-first search has been found to have computational complexity comparable to best-first search when the lower-bound function is very accurate or very inaccurate; otherwise, best-fit search is usually better. The results obtained are useful in studying the efficient evaluation of branch-and-bound algorithms in a virtual memory environment. They also confirm that approximations are very effective in reducing the total number of iterations.  相似文献   

4.
Parallel Formulations of Decision-Tree Classification Algorithms   总被引:5,自引:0,他引:5  
Classification decision tree algorithms are used extensively for data mining in many domains such as retail target marketing, fraud detection, etc. Highly parallel algorithms for constructing classification decision trees are desirable for dealing with large data sets in reasonable amount of time. Algorithms for building classification decision trees have a natural concurrency, but are difficult to parallelize due to the inherent dynamic nature of the computation. In this paper, we present parallel formulations of classification decision tree learning algorithm based on induction. We describe two basic parallel formulations. One is based on Synchronous Tree Construction Approach and the other is based on Partitioned Tree Construction Approach. We discuss the advantages and disadvantages of using these methods and propose a hybrid method that employs the good features of these methods. We also provide the analysis of the cost of computation and communication of the proposed hybrid method. Moreover, experimental results on an IBM SP-2 demonstrate excellent speedups and scalability.  相似文献   

5.
在基于宏块划分的视频编码算法中,运动估计阶段因为其庞大的计算量占用了绝大多数的编码时间.特别是在对高清视频进行编码时,运动估计已经成为提升编码性能的最大瓶颈.本文通过对全搜索运动估计算法进行基于像素的并行化修改和优化,使用SSE指令调用CPU的SIMD单元同时对当前宏块与参考宏块的多个像素进行SAD运算,对运动估计进行了并行化的实现.在相同的硬件环境以及保证编码质量的前提下,相对于传统的全搜索CPU运算获得了2倍以上的编码性能提升.  相似文献   

6.
《Artificial Intelligence》2007,171(2-3):73-106
The paper introduces an AND/OR search space perspective for graphical models that include probabilistic networks (directed or undirected) and constraint networks. In contrast to the traditional (OR) search space view, the AND/OR search tree displays some of the independencies present in the graphical model explicitly and may sometimes reduce the search space exponentially. Indeed, most algorithmic advances in search-based constraint processing and probabilistic inference can be viewed as searching an AND/OR search tree or graph. Familiar parameters such as the depth of a spanning tree, treewidth and pathwidth are shown to play a key role in characterizing the effect of AND/OR search graphs vs. the traditional OR search graphs. We compare memory intensive AND/OR graph search with inference methods, and place various existing algorithms within the AND/OR search space.  相似文献   

7.
基于与或树的柔性BOM结构及其产品配置算法   总被引:4,自引:0,他引:4  
刘裕  麦家健  李磊 《计算机工程》2005,31(21):189-191
形式化定义和描述了一种基于与或树的产品结构及其相关特性,基于该结构的BOM设计具有更好的产品配置柔性。在此基础上,还提出了一种面向任务的产品配置算法,能使产品的结构配置适应企业的特定生产任务要求。  相似文献   

8.
Establishing an appropriate semantic overlay on peer-to-peer (P2P) networks to obtain both semantic ability and scalability is a challenge. Current DHT-based P2P networks are limited in their ability to support a semantic search. This paper proposes the distributed suffix tree (DST) overlay as the intermediate layer between the DHT overlay and the semantic overlay to support the search of a keyword sequence. Its time cost is sublinear with the length of the keyword sequence. Analysis and experiments show that the DST-based search is fast, load-balanced, and useful in realizing an accurate content search on P2P networks.  相似文献   

9.
由于当前的基于DHT的P2P系统在语言搜索方面都有很大的限制,因此建立一种恰当的既具有语言能力又有伸缩性的语言覆盖P2P网络是一种挑战.文中提出一种介于DHT和支持关键字序列查找的语言覆盖之间的中间层DST覆盖网,通过DHT获取并返回给DST覆盖网相应的处理和索引数组,由DST实现关键字序列查找.分析表明它的时间复杂度与关键字序列的长度成线性关系,实验证明在P2P网络上使用基于DST的搜索获得一个确切的文本的查找具有快速性、负载平衡和可用性.  相似文献   

10.
本文提出一种用于区域表达的数据结构——数字搜索树(DST)及其线性化编码(LDST)。给出了在正方形区域图象最坏情况下的数据压缩公式,公式表明在图象分辨率较高时用LDST可使数据得到有效的压缩。最后,本文还给出了LDST与线性四叉树之间的转换算法及时间复杂度分析。  相似文献   

11.
一种启发式与/或优先约束任务调度算法   总被引:2,自引:1,他引:2  
系统描述了与或网模型及与或优先约束任务调度的可行性判定算法.以顶点覆盖问题为基础,证明与或优先约束任务调度最小完成时间问题是NP完全的.提出一种启发式调度算法,解决与或优先约束任务调度最小完成时间问题.仿真结果表明,该算法在降低算法复杂度的同时较其它相关算法具有更好的调度性能,从而证明在实时优先约束任务调度中引入图优化的理论是解决优先约束任务调度问题的一个有效途径.  相似文献   

12.
Power-aware scheduling for AND/OR graphs in real-time systems   总被引:2,自引:0,他引:2  
Power aware computing has become popular, recently and many techniques have been proposed to manage processor energy consumption for traditional real-time applications. In this paper, we are concerned mainly with the AND/OR model of real-time applications that have different execution paths consisting of different tasks. The contribution of this paper is twofold. First, we propose a greedy slack stealing algorithm to deal with applications represented by AND/OR graphs and prove its correctness in terms of meeting the timing constraints. Then, using statistical information about the applications, we propose a few variations of speculative scheduling algorithms that intend to save energy by reducing the number of speed changes (and, thus, the overhead) while ensuring that the application meets its timing constraints. Some practical issues are also considered, such as shared memory access contention and idle energy consumption. The performance of the algorithms is analyzed with respect to processor energy savings. The results surprisingly show that the greedy slack stealing scheme is better than some speculative schemes and that the greedy scheme is good enough when a reasonable minimal speed exists in the system or when there are only a few (four to six) voltage/speed levels.  相似文献   

13.
14.
B. Heise  M. Kuhn 《Computing》1996,56(3):237-258
An efficient parallel algorithm for solving linear and nonlinear exterior boundary value problems arising, e.g., in magnetostatics is presented. It is based upon the domaindecomposition-(DD)-coupling of Finite Element and Galerkin Boundary Element Methods which results in a unified variational formulation. In this way, e.g., magnetic field problems in an unbounded domain with Sommerfeld's radiation condition can be modelled correctly. The problem of a nonsymmetric system matrix due to Galerkin-BEM is overcome by transforming it into a symmetric but indefinite matrix and applying Bramble/Pasciak's CG for indefinite systems. For preconditioning, the main ideas of recent DD research are being applied. Test computations on a multiprocessor system were performed for two problems of practical interest including a nonlinear example.  相似文献   

15.
蒙特卡罗树搜索(Monte Carlo Tree Search,MCTS)在低维离散控制任务中取得了巨大的成功.然而,在现实生活中许多任务需要在连续动作空间进行行动规划.由于连续行动空间涉及的行动集过大,蒙特卡罗树搜索很难在有限的时间内从中筛选出最佳的行动.作为蒙特卡罗树搜索的一个变种,KR-UCT(Kernel Re...  相似文献   

16.
基于最低最小公共祖先(SLCA)的XML关键字搜索语义,提出一种使用XML结构摘要(summary)对关键字进行索引的方法XKSS.XKSS索引方法通过避免重复存储大量XML树上的含义相同的节点,大幅度降低了索引的空间耗费,并提高了查询性能.基于XKSS建立的索引,提出一个算法SSB-SLCA来计算SLCA节点.实验表明,基于XKSS的关键字搜索方法能够更高效地寻找关键字的SLCA.  相似文献   

17.
In this paper, we propose a practical and efficient method for finding the globally optimal solution to the problem of determining the pose of an object. We present a framework that allows us to use point-to-point, point-to-line, and point-to-plane correspondences for solving various types of pose and registration problems involving euclidean (or similarity) transformations. Traditional methods such as the iterative closest point algorithm or bundle adjustment methods for camera pose may get trapped in local minima due to the nonconvexity of the corresponding optimization problem. Our approach of solving the mathematical optimization problems guarantees global optimality. The optimization scheme is based on ideas from global optimization theory, in particular convex underestimators in combination with branch-and-bound methods. We provide a provably optimal algorithm and demonstrate good performance on both synthetic and real data. We also give examples of where traditional methods fail due to the local minima problem.  相似文献   

18.
一个基于移动Agent的搜索引擎的并行处理架构   总被引:3,自引:0,他引:3  
杨庆  翟玉庆 《计算机工程》2003,29(2):155-157
主要提出一个基于移动 Agent的Internet信息搜索引擎架构-WPSE(Web Parallel Search Engine)系统架构。该结构不仅模仿人的智能检索过程,而且提供了一个并行处理的环境。这对于实时检索多个站点信息是相当重要的。实验显示,相比较于数个串行移动 Agents模型,并行移动 Agent检索模型能够显著提高搜索效率。  相似文献   

19.
This paper describes the design of the Abstract Library for Parallel Search (ALPS), a framework for implementing scalable, parallel algorithms based on tree search. ALPS is specifically designed to support data-intensive algorithms, in which large amounts of data are required to describe each node in the search tree. Implementing such algorithms in a scalable manner is challenging both because of data storage requirements and communication overhead. ALPS incorporates a number of new ideas to address this challenge. The paper also describes the design of two other libraries forming a hierarchy built on top of ALPS. The first is the Branch, Constrain, and Price Software (BiCePS) library, a framework that supports the implementation of parallel branch and bound algorithms in which the bounds are obtained by solving some sort of relaxation, usually Lagrangian. In this layer, the notion of global data objects associated with the variables and constraints is introduced. These global objects provide a connection between the various subproblems in the search tree, but they pose further difficulties for designing scalable algorithms. The other library is the BiCePS linear integer solver (BLIS), a concretization of BiCePS, in which linear programming is used to obtain bounds in each search tree node.  相似文献   

20.
Although lexicographic (lex) variants of greedy algorithms are often P -complete, NC -algorithms are known for the following lex-search problems: lexicographic depth-first search (lex-dfs) for dags [12], [17], lexicographic breadth-first search (lex-bfs) for digraphs [12], [17], and lexicographic topological-first search (lex-tfs) for dags [12]. For the all-sources version of the problem for dense digraphs, the lex-dfs (lex-bfs, lex-tfs) in [12] is (within a log factor of) work-optimal with respect to the all-sources sequential solution that performs a dfs (bfs, tfs) from every vertex. By contrast, to solve the single-source lexicographic version on inputs of size n , all known NC -algorithms perform work that is at least an n factor away from the work performed by their sequential counterparts. We present parallel algorithms that solve the single-source version of these lex-search problems in O(log  2 n) time using M(n) processors on the EREW PRAM. (M(n) denotes the number of processors required to multiply two n\times n integer matrices in O(log  n) time and has O(n 2.376 ) as tightest currently known bound.) They all offer a polynomial improvement in work-efficiency over that of their corresponding best previously known and close the gap between the requirements of the best known parallel algorithms for the lex and the nonlex versions of the problems. Key to the efficiency of these algorithms is the novel idea of a lex-splitting tree and lex-conquer subgraphs of a dag G from source s . These structures provide a divide-and-conquer skeleton from which NC -algorithms for several lexicographic search problems emerge, in particular, an algorithm that places in the class NC the lex-dfs for reducible flow graphs—an interesting class of graphs which arise naturally in connection with code optimization and data flow analysis [4], [19]. A notable aspect of these algorithms is that they solve the lex-search problem instance at hand by efficiently transforming solutions of appropriate instances of (nonlex) path problems. This renders them potentially capable of transferring significant algorithmic advances—such as Driscoll et al.'s [14] single-source shortest paths algorithm and Ullman and Yannakakis' [34] transitive closure algorithm—from fundamental (nonlex) path problems to lex-search problems. Received January 9, 1994, and in revised form November 1997. Online publication July 20, 2001.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号