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

Parallel Formulations of IDA*

• Two formulations are intuitive.

• Common Cost Bound: Each processor is given the same cost bound. Processors use parallel DFS on the tree within the cost bound. The drawback of this scheme is that there might not be enough concurrency.

• Variable Cost Bound: Each processor works on a different cost bound. The major drawback here is that a solution is not guaranteed to be optimal until all lower cost bounds have been exhausted.

• In each case, parallel DFS is the search kernel.

Parallel Best-First Search

• The core data structure is the Open list (typically implemented as a priority queue).

• Each processor locks this queue, extracts the best node, unlocks it.

• Successors of the node are generated, their heuristic functions estimated, and the nodes inserted into the open list as necessary after appropriate locking.

•