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
