宽度优先反复加宽及其启发式搜索算法研究

首先针对搜索树中深度固定且目标唯一的寻优问题，指出宽度优先反复加宽的搜索效率要比深度优先反复加深的搜索效率高，基于此，提出了基于宽度优先反复加宽的启发式搜索算法ＩＷＡ＊，算法ＩＷＡ＊是可采纳的。为了保持算法ＩＷＡ＊的搜索效率高于算法ＩＤＡ＊的搜索效率，同时又使算法ＩＷＡ＊的存贮空间复杂度减低，文中基于分层技术，提出了基于深度优先的ＩＷＡ＊算法──ＩＤＷＡ＊。算法ＩＤＷＡ＊也是一个可采纳的启发式搜索算法。     

Depth-first iterative-deepening: An optimal admissible tree search

The complexities of various search algorithms are considered in terms of time, space, and cost of solution path. It is known that breadth-first search requires too much space and depth-first search can use too much time and doesn't always find a cheapest path. A depth-first iterative-deepening algorithm is shown to be asymptotically optimal along all three dimensions for exponential tree searches. The algorithm has been used successfully in chess programs, has been effectively combined with bi-directional search, and has been applied to best-first heuristic search as well. This heuristic depth-first iterative-deepening algorithm is the only known algorithm that is capable of finding optimal solutions to randomly generated instances of the Fifteen Puzzle within practical resource limits.     

Breadth-first heuristic search

Recent work shows that the memory requirements of A* and related graph-search algorithms can be reduced substantially by only storing nodes that are on or near the search frontier, using special techniques to prevent node regeneration, and recovering the solution path by a divide-and-conquer technique. When this approach is used to solve graph-search problems with unit edge costs, we show that a breadth-first search strategy can be more memory-efficient than a best-first strategy. We also show that a breadth-first strategy allows a technique for preventing node regeneration that is easier to implement and can be applied more widely. The breadth-first heuristic search algorithms introduced in this paper include a memory-efficient implementation of breadth-first branch-and-bound search and a breadth-first iterative-deepening A* algorithm that is based on it. Computational results show that they outperform other systematic search algorithms in solving a range of challenging graph-search problems.     

Pattern Databases

The efficiency of A* searching depends on the quality of the lower bound estimates of the solution cost. Pattern databases enumerate all possible subgoals required by any solution, subject to constraints on the subgoal size. Each subgoal in the database provides a tight lower bound on the cost of achieving it. For a given state in the search space, all possible subgoals are looked up in the pattern database, with the maximum cost over all lookups being the lower bound. For sliding tile puzzles, the database enumerates all possible patterns containing N tiles and, for each one, contains a lower bound on the distance to correctly move all N tiles into their correct final location. For the 15-Puzzle, iterative-deepening A* with pattern databases(N ="8) reduces the total number of nodes searched on a standard problem set of 100 positions by over 1000‐fold.     

Enhanced iterative-deepening search

Iterative-deepening searches mimic a breadth-first node expansion with a series of depth-first searches that operate with successively extended search horizons. They have been proposed as a simple way to reduce the space complexity of best-first searches like A* from exponential to linear in the search depth. But there is more to iterative-deepening than just a reduction of storage space. As the authors show, the search efficiency can be greatly improved by exploiting previously gained node information. The information management techniques considered here owe much to their counterparts from the domain of two-player games, namely the use of fast-execution memory functions to guide the search. The authors' methods not only save node expansions, but are also faster and easier to implement than previous proposals     

Learning with continuous experts using drifting games

We consider the problem of learning to predict as well as the best in a group of experts making continuous predictions. We assume the learning algorithm has prior knowledge of the maximum number of mistakes of the best expert. We propose a new master strategy that achieves the best known performance for on-line learning with continuous experts in the mistake bounded model. Our ideas are based on drifting games, a generalization of boosting and on-line learning algorithms. We prove new lower bounds based on the drifting games framework which, though not as tight as previous bounds, have simpler proofs and do not require an enormous number of experts. We also extend previous lower bounds to show that our upper bounds are exactly tight for sufficiently many experts. A surprising consequence of our work is that continuous experts are only as powerful as experts making binary or no prediction in each round.     

Fast and Exact Warping of Time Series Using Adaptive Segmental Approximations

Similarity search is a core module of many data analysis tasks, including search by example, classification, and clustering. For time series data, Dynamic Time Warping (DTW) has been proven a very effective similarity measure, since it minimizes the effects of shifting and distortion in time. However, the quadratic cost of DTW computation to the length of the matched sequences makes its direct application on databases of long time series very expensive. We propose a technique that decomposes the sequences into a number of segments and uses cheap approximations thereof to compute fast lower bounds for their warping distances. We present several, progressively tighter bounds, relying on the existence or not of warping constraints. Finally, we develop an index and a multi-step technique that uses the proposed bounds and performs two levels of filtering to efficiently process similarity queries. A thorough experimental study suggests that our method consistently outperforms state-of-the-art methods for DTW similarity search.     

Designing tree-based barrier synchronization on 2D mesh networks

In this paper, we consider a tree-based routing scheme for supporting barrier synchronization on scalable parallel computers with a 2D mesh network. Based on the characteristics of a standard programming interface, the scheme builds a collective synchronization (CS) tree among the participating nodes using a distributed algorithm. When the routers are set up properly with the CS tree information, barrier synchronization can be accomplished very efficiently by passing simple messages. Performance evaluations show that our proposed method performs better than previous path-based approaches and is less sensitive to variations in group size and startup delay. However, our scheme has the extra overhead of building the CS tree. Thus, it is more suitable for parallel iterative computations in which the same barrier is invoked repetitively     

Improving evolutionary decision tree induction with multi‐interval discretization

Decision trees are a widely used tool for pattern recognition and data mining. Over the last 4 decades, many algorithms have been developed for the induction of decision trees. Most of the classic algorithms use a greedy, divide‐and‐conquer search method to find an optimal tree, whereas recently evolutionary methods have been used to perform a global search in the space of possible trees. To the best of our knowledge, limited research has addressed the issue of multi‐interval decision trees. In this paper, we improve our previous work on multi‐interval trees and compare our previous and current work with a classic algorithm, ie, chi‐squared automatic interaction detection, and an evolutionary algorithm, ie, evtree. The results show that the proposed method improves on our previous method both in accuracy and in speed. It also outperforms chi‐squared automatic interaction detection and performs comparably to evtree. The trees generated by our method have more nodes but are shallower than those produced by evtree.     

Intensified iterative deepening A* with application to job shop scheduling

We propose a novel, exact any-time search strategy that combines iterative deepening \(\text{ A}\) * ( \(\text{ IDA}\) *) with depth-first search and we consider the job shop scheduling problem with makespan minimization as a test bed. The combination of these search strategies is done so that limited depth-first searches are issued from some of the states distributed along the frontier reached by \(\text{ IDA}\) * in each iteration. In this way, a proper equilibrium between intensification and diversification search effort is achieved while the algorithm keeps the capability of obtaining tight lower bounds. To evaluate the proposed strategy and to compare it with other methods, we have conducted an experimental study involving a number of conventional benchmarks with instances of various sizes. The results of these experiments show that the proposed algorithm takes less time than other methods in reaching optimal solutions for small and medium-size instances, and that it is quite competitive in reaching good solutions and good lower bounds for the instances that cannot be optimally solved.     

Depth-First Branch-and-Bound versus Depth-Bounded IDA: New Results

In a real-time task an action must be executed given limited computation. One approach to limited computation is to search a tree of possible action sequences to a fixed depth and then execute an action with the lowest associated backed-up cost. The standard algorithm for such a search is Depth-First Branch-and-Bound (DFBB), also known in the Artificial Intelligence literature as Minimin with Alpha Pruning . This article shows that a depth-bounded extension of a popular iterative algorithm called IDA has a surprisingly large range of search trees on which it outperforms DFBB—something previous analytical results do not predict. We prove that the extended algorithm, which we call DIDA , is correct, is guaranteed to terminate, and is asymptotically (i.e., on its last iteration) as efficient as DFBB—assuming a consistent heuristic is used. We also prove that both algorithms are guaranteed not to decrease their accuracy with a deeper search, assuming a consistent heuristic. Because accuracy is generally correlated with decision quality, the time saved by visiting fewer states translates to deeper searches which translates to better decisions. Results from random search trees show that DIDA is most efficient when the path cost + leaf node heuristic value is distributed with low variance; as branching factor increases, the range for which DIDA is more efficient also increases. Results with Eight, Fifteen, Twenty-four, and Ninety-nine Puzzle implementations of both algorithms—all domains with low variance of path cost + leaf node heuristic value—show that DIDA significantly outperforms DFBB.     

Range query processing on single and multi GPU environments

Metric-space similarity search has proven suitable in a number of application domains such as multimedia retrieval and computational biology to name a few. These applications usually work on very large databases that are often indexed to speed-up on-line searches. To achieve efficient throughput, it is essential to exploit the intrinsic parallelism in the respective search query processing algorithms. Many strategies have been proposed in the literature to parallelize these algorithms either on shared or distributed memory multiprocessor systems. Lately, GPUs have been used to implement brute-force parallel search strategies instead of using index data structures. Indexing poses difficulties when it comes to achieve efficient exploitation of GPU resources. In this paper we propose single and multi GPU metric space techniques that efficiently exploit GPU tailored index data structures for parallel similarity search in large databases. The experimental results show that our proposal outperforms previous index-based sequential and OpenMP search strategies.     

Unsynchronized iteratively deepening parallel alpha-beta search

A parallel alpha-beta search algorithm called unsynchronized iteratively deepening parallel alpha-beta search is described. The algorithm's simple control strategy and strong performance in complicated positions make it a viable alternative to the principal variation splitting algorithm (PVSA). Processors independently carry out iteratively deepening searches on separate subsets of moves. The iterative deepening is unsynchronized, e.g. one processor may be in the middle of the fifth iteration while another is in the middle of the sixth. Narrow windows diminish the importance of backing-up a score to the root of the tree as quickly as possible (one of the principal objectives of the PVSA). Speedups measured on one, two, four, and eight chess-playing computers are reported     

Scheduling task graphs optimally with A*

Scheduling tasks onto the processors of a parallel system is a crucial part of program parallelisation. Due to the NP-hard nature of the task scheduling problem, scheduling algorithms are based on heuristics that try to produce good rather than optimal schedules. Nevertheless, in certain situations it is desirable to have optimal schedules, for example for time-critical systems or to evaluate scheduling heuristics. This paper investigates the task scheduling problem using the A* search algorithm which is a best-first state space search. The adaptation of the A* search algorithm for the task scheduling problem is referred to as the A* scheduling algorithm. The A* scheduling algorithm can produce optimal schedules in reasonable time for small to medium sized task graphs with several tens of nodes. In comparison to a previous approach, the here presented A* scheduling algorithm has a significantly reduced search space due to a much improved consistent and admissible cost function f(s) and additional pruning techniques. Experimental results show that the cost function and the various pruning techniques are very effective for the workload. Last but not least, the results show that the proposed A* scheduling algorithm significantly outperforms the previous approach.     

Decision procedures for inductive Boolean functions based on alternating automata

We show how alternating automata provide decision procedures for the equality of inductively defined Boolean functions and present applications to reasoning about parameterized families of circuits. We use alternating word automata to formalize families of linearly structured circuits and alternating tree automata to formalize families of tree structured circuits. We provide complexity bounds for deciding the equality of function (or circuit) families and show how our decision procedures can be implemented using BDDs. In comparison to previous work, our approach is simpler, has better complexity bounds, and, in the case of tree-structured families, is more general.     

基于优化迭代的博弈树算法

博弈是诸如下棋、打牌、战争等一类竞争性智能活动的通称.通过对机器博弈的研究衍生了大量实用的研究成果.分析当今国际上主流的加快博弈树搜索效率的算法,根据它们的优缺点建立一种基于优化迭代的新算法,并且通过实验数据证明算法的优势.     

Experimenting with IDA* search algorithm in heterogeneous pervasive environments

Today, mobile and smart phones are often viewed as enablers of pervasive computing systems because they provide anytime and anywhere access to information services and computational resources. However, mobile devices are inherently constrained in their computational power and battery capacity making them mere “dumb terminals” connected to a resource-rich pervasive environment. If they are ever to play a more prominent role as true elements of a pervasive environment, mobile devices must be able to embed more application logic and delegate processing requests to pervasive infrastructure. In this paper we discuss distribution and offloading of computationally intensive tasks in pervasive environments populated by mobile devices. This approach is illustrated by experimenting with a distributed version of iterative deepening A* search algorithm. In our approach, the solution space of a problem being solved is partitioned and distributed among heterogeneous mobile devices, which yields a significant increase in the time of finding an optimal solution. Distributed IDA* search algorithm does not require any coordination or communication between mobile devices, but added inter-processor communication through shared memory further increases the efficiency of the algorithm. This paper presents the results of our experiments with the algorithm and discusses a number of issues related to its implementation.     

Finite time stability conditions for non-autonomous continuous systems

Lower and upper bounds for the quadratic cost functional of linear regulators are derived. These bounds are explicitly expressed in terms of some system parameters, arc independent of the initial conditions and are rather easy to compute. The results are based on a previous work by the authors concerning the lower bound. In this paper, the upper bound established is used to improve the lower bound, both being calculated by an iterative procedure to any degree of accuracy which is dependent on the number of iterations only.     

Fundamental limits of Bayesian inference: order parameters andphase transitions for road tracking

There is a growing interest in formulating vision problems in terms of Bayesian inference and, in particular, the maximum a posteriori (MAP) estimator. In this paper, we consider the special case of detecting roads from aerial images and demonstrate that analysis of this ensemble enables us to determine fundamental bounds on the performance of the MAP estimate. We demonstrate that there is a phase transition at a critical value of the order parameter; below this phase transition, it is impossible to detect the road by any algorithm. We derive closely related order parameters which determine the time and memory complexity of search and the accuracy of the solution using the n* search strategy. Our approach can be applied to other vision problems, and we briefly summarize the results when the model uses the “wrong prior”. We comment on how our work relates to studies of the complexity of visual search and the critical behaviour in the computational cost of solving NP-complete problems     

Solving the traveling tournament problem with iterative-deepening A?

This work presents an iterative-deepening A^? (IDA^?) based approach to the traveling tournament problem (TTP). The TTP is a combinatorial optimization problem which abstracts the Major League Baseball schedule. IDA^? is able to find optimal solutions to this problem, with performance improvements coming from the incorporation of various past concepts including disjoint pattern databases, symmetry breaking, and parallelization along with new ideas of subtree skipping, forced deepening, and elite paths to help to reduce the search space. The results of this work show that an IDA^? based approach can find known optimal solutions to most TTP instances much faster than past approaches. More importantly, it has been able to optimally solve two larger instances that have been unsolved since the problem??s introduction in 2001. In addition, a new problem set called GALAXY is introduced, using a 3D space to create a challenging problem set.