Search Algorithms for Discrete Optimization Problems Ananth Grama, Anshul Gupta, George Karypis, and Vipin Kumar

Termination signaled when we find a solution whose cost is better than the best heuristic value in the open list.

Since we expand more than one node at a time, we may expand nodes that would not be expanded by a sequential algorithm.

Parallel Best-First Search

• A general schematic for parallel best-first search using a centralized strategy. The locking operation is used here to serialize queue access by various processors.

Parallel Best-First Search

• The open list is a point of contention.

• Let texp be the average time to expand a single node, and taccess be the average time to access the open list for a single-node expansion.

• If there are n nodes to be expanded by both the sequential and parallel formulations (assuming that they do an equal amount of work), then the sequential run time is given by n(taccess+ texp).

•