Deterministic parallel backtrack search

The backtrack search problem involves visiting all the nodes of an arbitrary binary tree given a pointer to its root subject to the constraint that the children of a node are revealed only after their parent is visited. We present a fast, deterministic backtrack search algorithm for a p-processor COMMON CRCW-PRAM, which visits any n-node tree of height h in time O((n/p+h)(logloglogp)²). This upper bound compares favourably with a natural Ω(n/p+h) lower bound for this problem. Our approach embodies novel, efficient techniques for dynamically assigning tree-nodes to processors to ensure that the work is shared equitably among them.     

Efficient data structures for backtrack search SAT solvers

The implementation of efficient Propositional Satisfiability (SAT) solvers entails the utilization of highly efficient data structures, as illustrated by most of the recent state-of-the-art SAT solvers. However, it is in general hard to compare existing data structures, since different solvers are often characterized by fairly different algorithmic organizations and techniques, and by different search strategies and heuristics. This paper aims the evaluation of data structures for backtrack search SAT solvers, under a common unbiased SAT framework. In addition, advantages and drawbacks of each existing data structure are identified. Finally, new data structures are proposed, that are competitive with the most efficient data structures currently available, and that may be preferable for the next generation SAT solvers.     

Efficient data structures for backtrack search SAT solvers

The implementation of efficient Propositional Satisfiability (SAT) solvers entails the utilization of highly efficient data structures, as illustrated by most of the recent state-of-the-art SAT solvers. However, it is in general hard to compare existing data structures, since different solvers are often characterized by fairly different algorithmic organizations and techniques, and by different search strategies and heuristics. This paper aims the evaluation of data structures for backtrack search SAT solvers, under a common unbiased SAT framework. In addition, advantages and drawbacks of each existing data structure are identified. Finally, new data structures are proposed, that are competitive with the most efficient data structures currently available, and that may be preferable for the next generation SAT solvers.     

Improved speedup bounds for parallel alpha-Beta search

In this paper we investigate the ``mandatory-work-first' approach to parallel alpha-beta search first proposed by Akl, Barnard, and Doran. This approach is based on a version of alpha-beta search without deep cutoffs and a two-stage evaluation process, the second stage of which is often pruned. Our analysis shows that for best-first ordering on the lookahead tree, this approach provides greater speedup than the Palphabeta tree-splitting technique, and that for worst-first ordering, mandatory work first provides only slightly worse speedup than Palphabeta.     

Branch-and-bound and backtrack search on mesh-connected arrays of processors

In this paper we investigate the parallel complexity of backtrack and branch-and-bound search on the mesh-connected array. We present an (dN/logdN) lower bound for the time needed by arandomized algorithm to perform backtrack and branch-and-bound search of a tree of depthd on the N × N mesh, even when the depth of the tree is known in advance. The lower bound also holds for algorithms that are allowed to move tree-nodes and create multiple copies of the same tree-node.For the upper bounds we givedeterministic algorithms that are within a factor of 0(log^3/2 N) from our lower bound. Our algorithms do not make any assumption on the shape of the tree to be searched, do not know the depth of the tree in advance, and do not move tree-nodes nor create multiple copies of the same node.The best previously known algorithm for backtrack search on the mesh was randomized and required (dN/ logN) time. Our algorithm for branch-and-bound is the first algorithm that performs branch-and-bound search on a sparse network. Both the lower and the upper bounds extend to meshes of higher dimensions.Part of this work was done while the authors were at Harvard University.     

Improved monarch butterfly optimization for unconstrained global search and neural network training

This work is a seminal attempt to address the drawbacks of the recently proposed monarch butterfly optimization (MBO) algorithm. This algorithm suffers from premature convergence, which makes it less suitable for solving real-world problems. The position updating of MBO is modified to involve previous solutions in addition to the best solution obtained thus far. To prove the efficiency of the Improved MBO (IMBO), a set of 23 well-known test functions is employed. The statistical results show that IMBO benefits from high local optima avoidance and fast convergence speed which helps this algorithm to outperform basic MBO and another recent variant of this algorithm called greedy strategy and self-adaptive crossover operator MBO (GCMBO). The results of the proposed algorithm are compared with nine other approaches in the literature for verification. The comparative analysis shows that IMBO provides very competitive results and tends to outperform current algorithms. To demonstrate the applicability of IMBO at solving challenging practical problems, it is also employed to train neural networks as well. The IMBO-based trainer is tested on 15 popular classification datasets obtained from the University of California at Irvine (UCI) Machine Learning Repository. The results are compared to a variety of techniques in the literature including the original MBO and GCMBO. It is observed that IMBO improves the learning of neural networks significantly, proving the merits of this algorithm for solving challenging problems.     

基于蝶型网络模型的量子网络编码*

针对量子网络传输率低,信道利用率不高的问题,将经典网络编码的思想引入量子网络。基于蝶形网络模型,利用网络编码的思想,从经典信息和未知量子态两方面实现在量子网络上的最大流传输。而且在所提出的方案中,所有的信道都是量子信道,创新性的提出利用量子态作为“寄存器”实现经典信息的传递,有效的提高该方案的安全性。     

Optimal search for rationals

We present a Θ(log₂M)-time algorithm that determines an unknown rational number x in by asking at most 2log₂M+O(1) queries of the form “Is x?y?”.     

Optimal search strategies for speech understanding control

This paper describes two algorithms for finding the optimal interpretation of an unknown utterance in a continuous speech understanding system. These methods guarantee that the first complete interpretation found will be the best scoring interpretation possible. Moreover, unlike other optimal strategies, they do not make finite-state assumptions about the nature of the grammar for the language being recognized. One of the methods, the density method, is especially interesting because it is not an instance of the ‘optimal’ $\text{A1}$ algorithm of Hart, Nilsson, and Raphael, and appears to be superior to it in the domains in which it is applicable. The other method, the shortfall method, is an instance of the $\text{A1}$ algorithm using a particular heuristic function. Proofs of the guaranteed discovery of the best interpretation and some empirical comparisons of the methods are given. The relationship of these methods to strategies used in existing speech understanding systems is also discussed. Although presented in the speech context, the algorithms are applicable to a general class of optimization and heuristic search problems.     

Optimal parallel algorithms for constructing and maintaining a balancedm-way search tree

We present parallel algorithms for constructing and maintaining balancedm-way search trees. These parallel algorithms have time complexity O(1) for ann processors configuration. The formal correctness of the algorithms is given in detail.     

基于QDP的蝶形量子网络编码方案

当前已有的蝶形量子网络方案多数只能完成量子态经公共信道进行交叉传输,并且为实现蝶形网络的量子态无损传输,通常需要消耗纠缠资源。结合量子直接传态方案中态传输的方法,提出一种在蝶形网络中传输任意已知单量子态的网络编码方案。利用处于基态的单粒子作为量子寄存器,实现每个接收节点均能同时接收到来自全部发送节点发送的不同量子态。整个通信过程不需要使用纠缠资源和测量操作,仅通过各节点执行相关酉操作即可完成通信。并且将该方案扩展至采用多种形式的量子态作为寄存器以及发送节点和接收节点个数更多的情况。     

Optimal resource assignment to maximize multistate network reliability for a computer network

Computer network is a major tool to transmit data in our modern society. How to evaluate and enhance network reliability is thus an important issue for organizations, especially to maximize network reliability. A computer network is a multistate network in which each edge has several possible capacities with a probability distribution and may fail. The multistate network reliability is the probability that the maximal flow is no less than a given demand. From the standpoint of quality management, a further problem is to reassign the existing resources for maximizing multistate network reliability without changing the network topology. Hence, this paper focuses on the resource assignment problem to propose an efficient approach based on the simple genetic algorithm. In which, a resource assignment is represented as a chromosome and the corresponding multistate network reliability is the fitness value of the chromosome. The experimental results show that the proposed algorithm can derive the optimal resource assignment in a reasonable time.     

Optimal multiway search trees for variable size keys

Summary This paper considers the construction of optimal search trees for a sequence of n keys of varying sizes, under various cost measures. Constructing optimal search cost multiway trees is NP-hard, although it can be done in pseudo-polynomial time O ³ and space O ², where L is the page size limit. An optimal space multiway search tree is obtained in O ³ time and O ² space, while an optimal height tree in O(n ² log² n) time and O(n) space both having additionally minimal root sizes. The monotonicity principle does not hold for the above cases. Finding optimal search cost weak B-trees is NP-hard, but a weak B-tree of height 2 and minimal root size can be constructed in O(n log n) time. In addition, if its root is restricted to contain M keys then a different algorithm is applied, having time complexity O(nM log n). The latter solves a problem posed by McCreight.     

A flabellate overlay network for multi-attribute search

Peer-to-peer (P2P) technology provides a popular way of distributing resources, sharing, and locating in a large-scale distributed environment. However, most of the current existing P2P systems only support queries over a single resource attribute, such as file name. The current multiple resource attribute search methods often encounter high maintenance cost and lack of resilience to the highly dynamic environment of P2P networks. In this paper, we propose a Flabellate overlAy Network (FAN), a scalable and structured underlying P2P overlay supporting resource queries over multi-dimensional attributes. In FAN, the resources are mapped into a multi-dimensional Cartesian space based on the consistent hash values of the resource attributes. The mapping space is divided into non-overlapping and continuous subspaces based on the peer’s distance. This paper presents strategies for managing the extended adjacent subspaces, which is crucial to network maintenance and resource search in FAN. The algorithms of a basic resource search and range query over FAN are also presented in this paper. To alleviate the load of the hot nodes, a virtual replica network (VRN) consisting of the nodes with the same replicates is proposed for replicating popular resources adaptively. The queries can be forwarded from the heavily loaded nodes to the lightly loaded ones through VRN. Theoretical analysis and experimental results show that FAN has a higher routing efficiency and lower network maintenance cost over the existing multi-attribute search methods. Also, VRN efficiently balances the network load and reduces the querying delay in FAN while invoking a relatively low overhead.     

A Tabu search approach for designing a non-hierarchical video-on-demand network architecture

In this paper, we present a tabu search to design a non-hierarchical and decentralized video-on-demand (VOD) network architecture. To optimize the VOD network resource, we consider optimization of both video server locations and storage allocation subject to the tradeoffs among installation cost for video servers, program storage cost, and transmission (or communication) cost. In applying a tabu search technique to the problem, neighborhood structure and search strategy are elaborated to improve solution quality and to reduce computation time. We report the results of the computational experiments to demonstrate the performance of the proposed tabu search. A comparative study shows that our algorithm is promising.     

Optimal scheduling of compute-intensive tasks on a network ofworkstations

In a network of high performance workstations, many workstations are underutilized by their owners. The problem of using these idle cycles for solving computationally intensive tasks by executing a large task on many workstations has been addressed before and algorithms with O(N²) time and O(N) space for choosing the optimal subset of workstations out of N workstations were presented. We improve these algorithms to reduce the running time to O(N log N), while keeping the space requirement the same. The proposed algorithms are particularly useful for SPMD parallelism where computation is the same for all workstations and the data space is partitioned between the workstations