Combinatorial Search Flashcards
Combinatorial Algorithms
perform computations on discrete structure
Combinatorial Search
Finding one or more optimal or suboptimal solutions in a defined problem space
Trees
- Root of problem to be solved
- Each node represents a sub problem
AND - Tree
A solution to every subproblem is required
OR - Tree
A solution to any of the subproblems is required
Divide and Conquer
- partition problem into subproblems
- solve the subproblems
- combine solutions to subproblems
- AND - Tree
- Recursive
Centralised Multiprocessor
- One shared stack
- Effective workload balancing mechanism
- Stack can become bottleneck as a number of processors increase
Distributed Divide and Conquer
Subproblems must be distributed
Original problem and final solution
- stored on a single processor.
o three phases, limited speedup - or distributed
o maximum problem increase with number of processors
o challenge to keep workloads balanced
Backtrack Search
- Depth First Search
- Recursive Algorithm
- OR-Tree
o A node has no children
o all node’s childrenn have been explored
Backtrack Search Strategy
- Identify the longest incomplete word
o Look for a word of that length
o No word found - backtrack - Otherwise find longest incomplete word that has at least one letter
o Look for a word of that length
o No word found - backtrack - Recurse until solution found or all possibilities have been attempted
Backtrack Search - Time Complexity
- Suppose
o The average branching factor is b
o Tree searched to depth k - Examine
o Nodes in the worst case (exponential time)
1 + b + b^2 + … + b^k = (b^(k+1) - b) / (b - 1) +1 = 0(b^k)
o Amount of memory
0(b^k)
Parallel Backtrack
Option 1
* Give each process a subtree
* Works when p = b^k because each process has equal work
* Otherwise, Search to a level m where b^m > p
* Each process explores its share of subtrees at m
* Increasing m
* More subtress
* More balances workload
* Increases # redundanct computations
Option 2
* Make sequential search fo deeper
* Cyclic allocation of subtrees
Branch and Bound
- Variant of backtrack search
- Takes advantage of information about optimality of partial solutions to avoid considering solutions that cannot be optimal
- OR - Tree
Branch and Bound Methodology
- Could solve puzzle by pursuing breadth-first search of state
space tree - We want to examine as few nodes as possible
- Can speed up search if we associate with each node an estimate of minimum number of tile moves needed to solve puzzle, given moves made so far
Manhattan Distance
Best-first search: search from node that has the smallest value for a function such as
the Manhattan distance
Parallel Branch and Bound
- Conflicting Goals
- Want to maximise ratio of local to non-local memory references
- Want to ensure processors searching worthwhile portions of state space tree
Single priority queue
- not a good idea
- communication overhead too great
- accessing queue is a performance
bottleneck - problem size does not scale with
number of processors
Multiple Priority Queue
- Each process maintains separate priority
queue of unexamined subproblems - Each process retrieves subproblem with
smallest lower bound to continue search - Occasionally processes send unexamined
subproblems to other processes
Searching Game Trees
- Based on exhaustive search
- Minimax Algorithm
- A form of DFS
- Player 1(2) wnats to maximise (minimise) value of node
- AND/OR Tree
Complexity of Minimax
- branching factor b
- Depth d
- Examine b x d leaves
- Exponential time in depeth of search
- Space required = linear in depth of search
Alpha Beta Pruning
- Typically a deeper search = higher play quality
- Allows deeper searches
- As soon as alpha > beta we can prune
- Beta is the worst value of the child if minimising
- Alpha is the best value of the child if maximising
Serial Improvements to Minimax
Aspiration Search
* Pruning window (v-e, v+e) instead of (-infinity, +infinity)
* Pruning iincreases as window shrinks
Iterative deepening
* Ply = level of game tree
* Iterate deeper and depper until time expired
* Use (d-1) - ply search to prepare for d-ply search
* Use results to order nodes for d-ply search
* Use return value for d-ply aspiration search
Parallel alpha beta search
- Perform move generation in parallel and position evaluation
- Search the tree in parallel
- Parallel
- Aspiration Search
- Distributed Tree Search
- Processes examine independent subtrees in parallel
- Overheads
- Search overhead - duplicate work
- Communication overhead
- Parallel Aspiration Search
- Multiple windows, one per process
Distributed Tree Search
- Processes control groups of processors
- Process 0 assigned root node, control other processes
- Type 1 nodes
- All processors search leftmost child
- on return - processes assigned children breadth-first
- Type 2 or 3 nodes
- Processes assigned children breadth-first
- On completion - parent process may reassign its processors to children processes still busy
