# 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