Search Algorithms Flashcards
(11 cards)
What does Exhaustive Search do?
Systematically tries all possible candidates for an assignment, pruning branches based on conflicts
What are the pros and cons of the Exhaustive Search algorithm?
Easy to implement and guarantees a solution, but can be extremely slow
What does Branch and Bound do?
Systematically tries all possible candidates for an assignment, pruning branches based on conflicts AND if that branch won’t lead to a better solution
What are the improvements of Branch and Bound over Exhaustive Search?
More efficient, explores many possibilities while avoiding ones that are clearly unhelpful
Given an nxn array of integers, how can you find the widest possible bounds?
Min = Sum of minimum integer in each row
Max = Sum of maximum integer in each row
Given an nxn array of integers, how can you find a tighter bound than the widest?
Min = Sum of minimum integer in each row
Max = Sum of pos or neg diagonal
In a Branch and Bound algorithm implementation, what should you do with bound periodically?
Update it if a higher (or lower) bound is found during processing
What does Best First Branch and Bound do?
The same as Branch and Bound, except it favors the best possible assignment option first
In the case of find a worker assignment with the best happiness
What is the bookkeeping for Exhaustive Search?
int a[n]
int H[n][n]
Total: O(n) O(n^2)
In the case of find a worker assignment with the best happiness
What is the bookkeeping for Branch and Bound?
int a[n]
int H[n][n]
int max[n]
Preprocessing to build max: n^2
Increase/decrease sum, Update bound: 1
Total: Exhaustive + O(n) O(n^2) O(1)
In the case of find a worker assignment with the best happiness
What is the bookkeeping for Best First Branch and Bound?
int a[n]
int H[n][n]
int max[n]
int O[n][n]
Preprocessing to build O: n^2 * n
Total: Branch and Bound + O(n^2) O(n^3)
