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).
