Multiprocessing of Combinatorial Search Problems

Abstract

This chapter presents three paradigms of representations for combinatorial search problems. Depending on the functions of the nonterminal nodes in the graphical representation, a search problem can be represented as an AND-tree, an OR-tree, and an AND/OR graph. This classification facilitates the design of unique computer architectures for supporting efficient evaluation of combinatorial search problems. For each representation, we develop theoretical bounds, efficient algorithms, and functional requirements of multiprocessing architectures, and illustrate these results by examples.