Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

Parallel Algorithms for Combinatorial Search Problems

Yanjun Zhang

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-89-543
November 1989

http://www.eecs.berkeley.edu/Pubs/TechRpts/1989/CSD-89-543.pdf

This thesis is a theoretical study of parallel algorithms for combinatorial search problems. In this thesis we present parallel algorithms for backtrack search, branch-and-bound computation and game-tree search.

Our model of parallel computation is a network of processors communicating via messages. Our primary interest in a parallel algorithm is its speed-up over the sequential ones. Our goal is to design parallel algorithms that achieve a speed-up proportional to the number of processors used.

We first study backtrack search that enumerates all solutions to a combinatorial problem. We propose a simple randomized method for parallelizing sequential backtrack search algorithms for solving enumeration problems. We show that, uniformly on all instances, this method is likely to achieve a nearly best possible speed-up.

We then study the branch-and-bound method for solving combinatorial optimization problems. We present a randomized method called Local Best-First Search for parallelizing sequential branch-and-bound algorithms. We show that, uniformly on all instances, the execution time of this method is unlikely to exceed a certain inherent lower bound by more than a constant factor.

In the rest of this thesis we study the problem of evaluation of game trees in parallel. We present a class of parallel algorithms that parallelize the "left-to-right" algorithm for evaluating AND/OR trees and the Alpha-Beta pruning algorithm for evaluating MIN/MAX trees. We prove that the algorithm achieves a linear speed-up over the left-to-right algorithm on uniform AND/OR trees when the number of processors used is close to the height of the input tree. We conjecture that the same conclusion holds for the speed-up of the algorithm over the Alpha-Beta pruning algorithm.

Advisor: Richard M. Karp


BibTeX citation:

@phdthesis{Zhang:CSD-89-543,
    Author = {Zhang, Yanjun},
    Title = {Parallel Algorithms for Combinatorial Search Problems},
    School = {EECS Department, University of California, Berkeley},
    Year = {1989},
    Month = {Nov},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1989/5909.html},
    Number = {UCB/CSD-89-543},
    Abstract = {This thesis is a theoretical study of parallel algorithms for combinatorial search problems. In this thesis we present parallel algorithms for backtrack search, branch-and-bound computation and game-tree search. <p>Our model of parallel computation is a network of processors communicating via messages. Our primary interest in a parallel algorithm is its speed-up over the sequential ones. Our goal is to design parallel algorithms that achieve a speed-up proportional to the number of processors used. <p>We first study backtrack search that enumerates all solutions to a combinatorial problem. We propose a simple randomized method for parallelizing sequential backtrack search algorithms for solving enumeration problems. We show that, uniformly on all instances, this method is likely to achieve a nearly best possible speed-up. <p>We then study the branch-and-bound method for solving combinatorial optimization problems. We present a randomized method called Local Best-First Search for parallelizing sequential branch-and-bound algorithms. We show that, uniformly on all instances, the execution time of this method is unlikely to exceed a certain inherent lower bound by more than a constant factor. <p>In the rest of this thesis we study the problem of evaluation of game trees in parallel. We present a class of parallel algorithms that parallelize the "left-to-right" algorithm for evaluating AND/OR trees and the Alpha-Beta pruning algorithm for evaluating MIN/MAX trees. We prove that the algorithm achieves a linear speed-up over the left-to-right algorithm on uniform AND/OR trees when the number of processors used is close to the height of the input tree. We conjecture that the same conclusion holds for the speed-up of the algorithm over the Alpha-Beta pruning algorithm.}
}

EndNote citation:

%0 Thesis
%A Zhang, Yanjun
%T Parallel Algorithms for Combinatorial Search Problems
%I EECS Department, University of California, Berkeley
%D 1989
%@ UCB/CSD-89-543
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/1989/5909.html
%F Zhang:CSD-89-543