Parallel & Distributed Search Flashcards
Explain the divide and conquer search algorithm
The divide and conquer methodology partitions problems into sub problems and solves the sub problems. It then combines these solutions into the final solution. It is done by using an AND tree and recursion.
How can one parallelise divide and conquer search algorithm?
There are 2 methods: Centralised multiprocessor & Distributed divide-and-conquer
Centralised Multiprocessor:
- uses a single shared stack of sub problems which can become a bottleneck as the number of processes increase
- if using a cluster of machines we have to use message passing to distribute sub problems
- store original and final solution on 1 process
- downside is that it takes a while before all processes are busy and it takes a while to combine the results
Distributed divide-and-conquer:
- both the original and final solution are distributed among memories of the processes
- benefit -> problem size that can be solved increases with the increases of the number of processes
- challenge -> keeping the work load balanced
Explain the backtrack search algorithm
This algorithm uses Depth First Search with recursion. An OR tree is used and backtrack occurs when a node has no children (dead end) or all nodes children have been explored.
What is the worst case in backtrack search?
Average branching factor = b
Search depth = k
Worst case = (b^(k+1) - b)/(b - 1) + 1 = theta(b^k)
How can one parallelise the backtrack search algorithm?
Two options:
1. Give each process a subtree
- if p < b^k (no. of subtrees) : process 0 searches to a depth where there are enough subtrees for each process
- disadvantage: tree is off balance
2. Allocate many subtrees per process
- search to a deeper level and the cyclically allocate subtrees to processes
Explain the branch and bound search algorithm
It is a variant of backtrack search that takes the estimated optimality of partial solutions into account in order to avoid considering solutions(moves) that cannot be optimal. Uses an OR tree. Usually pursues a breadth first search of state space tree.
How can one parallelise branch and bound search algorithm?
Two options:
1. Single priority queue:
- contention for accessing shared queue
- problem size does not scale with number of processors
2. Multiple priority queues:
- occasionally send unexpired problems to other processes, to share work at start up and to promote distribution of sub problems with good lower bounds and reduce amount of wasted work
- trade-off between amount of wasted work and cost of sending messages
Explain the Search Game Tree algorithm
Based on an exhaustive search, such as the minimax algorithm which is a form of DFS which considers a series of possible moves to a certain depth and then estimates the result at the depth using a heuristic function. Uses and AND/OR tree.
How can one parallelise alpha-beta pruning (the Search Game Tree algorithm)?
By assigning different subtrees to different processes.
HOWEVER alpha beta pruning is not as effective for a parallel implementation as a sequential implementation of minimax due to the changing of alpha beta values leading to independent processes needing to send updated values to other processes in order to prune a non-optimal moves.
What are some enhancements that can made to alpha-beta pruning?
Aspiration Search: estimates the value at the root node and use this to choose a smaller window than negative infinity to positive infinity -> pruning happens earlier on the search
Iterative Deepening: starts with a shallow search. Uses (d - 1)-ply search results to order the nodes for d-ply search
