检索结果-内蒙古大学图书馆

19th Annual International Conference on Computational Science (ICCS)

作者： Carneiro, Tiago Melab, Nouredine INRIA Lille Nord Europe Lille France Univ Lille CNRS CRIStAL Lille France

ISBN: (纸本)9783030227340;9783030227333

Parallel tree search algorithms offer viable solutions to problems in different areas, such as operations research, machine learning and artificial intelligence. This class of algorithms is highly compute-intensive, irregular and usually relies on context-specific data structures and hand-made code optimizations. Therefore, C and C++ are the languages often employed, due to their low-level features and performance. In this work, we investigate the use of Chapel high-productivity language for the design and implementation of distributed tree search algorithms for solving combinatorial problems. The experimental results show that Chapel is a suitable language for this purpose, both in terms of performance and productivity. Despite the use of high-level features, the distributed tree search in Chapel is on average 16% slower and reaches up to 85% of the scalability observed for its MPI+OpenMP counterpart.

关键词： tree search algorithms High productivity PGAS Chapel MPI plus OpenMP

来源：评论

学校读者我要写书评

暂无评论

Partial Board tree search 5th

Partial Board Tree Search

引用

5th International Conference on Man-Machine Interactions (ICMMI)

作者： Perlinski, Robert Czestochowa Tech Univ Inst Comp & Informat Sci Czestochowa Poland

ISBN: (纸本)9783319677927;9783319677910

In this article, a new approach to solving selected two-person perfect information zero-sum games is proposed. This new approach involves dividing game board into smaller parts called partial boards. Every such partial board has an associated "border state" which is an information structure vital to the game solving process. Using partial boards, it is possible to generate partial board game trees. Such structures are sufficient for the purpose of searching complete game trees- in effect. The possibility of making different board divisions allows an entire partial board game tree to be stored in computer memory. As a result, tree search algorithms based on partial board game trees work very fast. This approach can be applied only for specific games. Examples of such games are Atari-Go, Hex, and Gomoku. Experimental results relating to the solving of the Atari-Go game are presented here.

关键词： tree search algorithms Solving games Computer Go

来源：评论

学校读者我要写书评

暂无评论

Recherches arborescentes anytime pour l'optimisation combinatoire: Anytime tree search for combinatorial optimization

Recherches arborescentes anytime pour l'optimisation combina...

引用

作者： Libralesso, Luc Université Grenoble Alpes

学位级别：博士

Les recherches arborescentes sont utilisées dans un grand nombre d'applications (MIP, CP, SAT, metaheuristiques avec Ant Colony Optimization et GRASP) et également dans des communautés IA/planning. Toutes ces techniques présentent des bases communes et de nombreuses techniques peuvent être transférées d'une communauté à une autre. Les résultats préliminaires indiquent que ces techniques sont très performantes comparé aux metaheuristiques généralement utilisés en recherche opé*** ces travaux, nous dressons un état de l'art et une classification de différentes techniques de recherche arborescente que l'on retrouve dans les metaheuristiques, dans les méthodes exactes et en IA/*** développons un framework générique qui permet l'élaboration rapide d'algorithmes de recherche ***, nous utilisons ces techniques pour proposer des méthodes compétitives avec les metaheuristiques généralement utilisées en recherche opérationnelle. Nous présentons de nouvelles méthodes de recherche arborescente pour plusieurs problèmes d'optimisation combinatoire ainsi que de nouvelles meilleures solutions connues. tree search algorithms are used in a large variety of applications (MIP, CP, SAT, metaheuristics with Ant Colony Optimization and GRASP) and also in AI/planning communities. All of these techniques present similar components and many of those components can be transferred from one community to another. Preliminary results indicate that anytime tree search techniques are competitive compared to commonly used metaheuristics in operations *** this work, we detail a state of the art and a classification of the different tree search techniques that one can find in metaheuristics, exact methods and AI/planning. Then, we present a generic framework that allows the rapid prototyping of tree search algorithms. Finally, we use this framework to develop anytime tree search algorithms that are competitive with the commonly-used metaheuristics in opera

关键词： Recherches arborescentes Metaheuristiques Optimisation combinatoire tree search algorithms Metaheuristics Combinatorial optimization 004

来源：评论

学校读者我要写书评

暂无评论

New algorithms and Methods to Estimate Maximum-Likelihood Phylogenies: Assessing the Performance of PhyML 3.0

引用

SYSTEMATIC BIOLOGY 2010年第3期59卷 307-321页

作者： Guindon, Stephane Dufayard, Jean-Francois Lefort, Vincent Anisimova, Maria Hordijk, Wim Gascuel, Olivier Univ Montpellier CNRS LIRMM F-34392 Montpellier 5 France Univ Auckland Dept Stat Auckland 1142 New Zealand ETH Inst Computat Sci CH-8092 Zurich Switzerland Swiss Inst Bioinformat CH-1015 Lausanne Switzerland Univ Oxford Dept Stat Oxford OX1 3TG England

PhyML is a phylogeny software based on the maximum-likelihood principle. Early PhyML versions used a fast algorithm performing nearest neighbor interchanges to improve a reasonable starting tree topology. Since the original publication (Guindon S., Gascuel O. 2003. A simple, fast and accurate algorithm to estimate large phylogenies by maximum likelihood. Syst. Biol. 52:696-704), PhyML has been widely used (> 2500 citations in ISI Web of Science) because of its simplicity and a fair compromise between accuracy and speed. In the meantime, research around PhyML has continued, and this article describes the new algorithms and methods implemented in the program. First, we introduce a new algorithm to search the tree space with user-defined intensity using subtree pruning and regrafting topological moves. The parsimony criterion is used here to filter out the least promising topology modifications with respect to the likelihood function. The analysis of a large collection of real nucleotide and amino acid data sets of various sizes demonstrates the good performance of this method. Second, we describe a new test to assess the support of the data for internal branches of a phylogeny. This approach extends the recently proposed approximate likelihood-ratio test and relies on a nonparametric, Shimodaira-Hasegawa-like procedure. A detailed analysis of real alignments sheds light on the links between this new approach and the more classical nonparametric bootstrap method. Overall, our tests show that the last version (3.0) of PhyML is fast, accurate, stable, and ready to use. A Web server and binary files are available from http://***/phyml/.

关键词： Bootstrap analysis branch testing LRT and aLRT maximum likelihood NNI phylogenetic software SPR tree search algorithms

来源：评论

学校读者我要写书评

暂无评论

Column generation approach for disassembly line balancing

Column generation approach for disassembly line balancing

引用

8th IFAC Conference on Manufacturing Modelling, Management and Control (MIM)

作者： Duta, L. Caciula, I. Patic, P. C. Valahia Univ Targoviste Fac Elect Engn Targoviste Romania

Disassembly line balancing is a multi-objective problem which was found out to be NP-complete. Its exponential time complexity limits its application to small size instances. To overcome this problem, a heuristic methodology composed of two-stages is proposed. In the first phase, a mixed integer linear model is formulated so as to integrate the disassembly task allocation constraints. In the second phase, a tree search algorithm is applied to find the optimal schedule that balances the disassembly line. Column generation benchmark results show a good performance of the algorithm for large size instances. (C) 2016, IFAC (International Federation of Automatic Control) Hosting by Elsevier Ltd. All right reserved.

关键词： disassembly line balancing mixed integer programming tree search algorithms

来源：评论

学校读者我要写书评

暂无评论

Coherent and non-coherent data detection algorithms in massive MIMO

Coherent and non-coherent data detection algorithms in massi...

引用

作者： Haider Ali Jasim Alshamary University of Iowa

学位级别：博士

Over the past few years there has been an extensive growth in data traffic consumption devices. Billions of mobile data devices are connected to the global wireless network. Customers demand revived services and up-to-date developed applications, like real-time video and games. These applications require reliable and high data rate wireless communication with high throughput network. One way to meet these requirements is by increasing the number of transmit and/or receive antennas of the wireless communication systems. Massive multiple-input multiple-output (MIMO) has emerged as a promising candidate technology for the next generation (5G) wireless communication. Massive MIMO increases the spatial multiplexing gain and the data rate by adding an excessive number of antennas to the base station (BS) terminals of wireless communication systems. However, building efficient algorithms able to decode a coherently or non-coherently large flow of transmitted signal with low complexity is a big challenge in massive MIMO. In this dissertation, we propose novel approaches to achieve optimal performance for joint channel estimation and signal detection for massive MIMO systems. The dissertation consists of three parts depending on the number of users at the receiver side. In the first part, we introduce a probabilistic approach to solve the problem of coherent signal detection using the optimized Markov Chain Monte Carlo (MCMC) technique. Two factors contribute to the speed of finding the optimal solution by the MCMC detector: The probability of encountering the optimal solution when the Markov chain converges to the stationary distribution, and the mixing time of the MCMC detector. First, we compute the optimal value of the "temperature'' parameter such that the MC encounters the optimal solution in a polynomially small probability. Second, we study the mixing time of the underlying Markov chain of the proposed MCMC detector. We assume the channel state information is known i

关键词： Coherent and non-coherent detection Generalized ration test Joint channel estimation and data detection Massive MIMO tree search algorithms

来源：评论

学校读者我要写书评

暂无评论

Distance-based phylogenetic inference from typing data: a unifying view

引用

BRIEFINGS IN BIOINFORMATICS 2021年第3期22卷 000-000页

作者： Vaz, Catia Nascimento, Marta Carrico, Joao A. Rocher, Tatiana Francisco, Alexandre P. Inst Politecn Lisboa Inst Super Engn Lisboa Lisbon Portugal INESC ID Lisbon Portugal Univ Lisbon Inst Super Tecn Lisbon Portugal Univ Lisbon Inst Microbiol Fac Med Lisbon Portugal Univ Lisbon Inst Med Mol Lisbon Portugal

Typing methods are widely used in the surveillance of infectious diseases, outbreaks investigation and studies of the natural history of an infection. Moreover, their use is becoming standard, in particular with the introduction of high-throughput sequencing. On the other hand, the data being generated are massive and many algorithms have been proposed for a phylogenetic analysis of typing data, addressing both correctness and scalability issues. Most of the distance-based algorithms for inferring phylogenetic trees follow the closest pair joining scheme. This is one of the approaches used in hierarchical clustering. Moreover, although phylogenetic inference algorithms may seem rather different, the main difference among them resides on how one defines cluster proximity and on which optimization criterion is used. Both cluster proximity and optimization criteria rely often on a model of evolution. In this work, we review, and we provide a unified view of these algorithms. This is an important step not only to better understand such algorithms but also to identify possible computational bottlenecks and improvements, important to deal with large data sets.

关键词： phylogenetic inference clustering methods tree search algorithms

来源：评论

学校读者我要写书评

暂无评论

Constraint satisfaction algorithms

引用

Computational Intelligence 1989年第3期5卷 188-224页

作者： Nadel, Bernard A. Computer Science Department Wayne State University Detroit Michigan 48202 United States

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. Copyright © 1989, Wiley Blackwell. All rights reserved

关键词： arc consistency algorithms Backjumping Backmarking Backtracking constraint satisfaction problem Forward Checking. network consistency algorithms tree search algorithms

来源：评论

学校读者我要写书评

暂无评论

HYBRID algorithms FOR THE CONSTRAINT SATISFACTION PROBLEM

引用

Computational Intelligence 1993年第3期9卷

作者： Patrick Prosser Department of Computer Science University of Strathclyde Livingstone Tower Glasgow Gl 1XH Scotland e-mail: pat@cs.strath.ac.uk

It might be said that there are five basic tree search algorithms for the constraint satisfaction problem (csp), namely, naive backtracking (BT), backjumping (BJ), conflict-directed backjumping (CBJ), backmarking (BM), and forward checking (FC). In broad terms, BT, BJ, and CBJ describe different styles of backward move (backtracking), whereas BT, BM, and FC describe different styles of forward move (labeling of variables). This paper presents an approach that allows base algorithms to be combined, giving us new hybrids. The base algorithms are described explicitly, in terms of a forward move and a backward move. It is then shown that the forward move of one algorithm may be combined with the backward move of another, giving a new hybrid. In total, four hybrids are presented: backmarking with backjumping (BMJ), backmarking with conflict-directed backjumping (BM-CBJ), forward checking with backjumping (FC-BJ), and forward checking with conflict-directed backjumping (FC-CBJ). The performances of the nine algorithms (BT, BJ, CBJ, BM, BMJ, BM-CBJ, FC, FC-BJ, FC-CBJ) are compared empirically, using 450 instances of the ZEBRA problem, and it is shown that FC-CBJ is by far the best of the algorithms examined.

关键词： constraint satisfaction problem tree search algorithms backtracking backjumping backmarking forward checking

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：