Search: Summary
Discrete optimization problem
In general, NP-Hard
- Need to resort to heuristic search
- In practice, search is relatively fast (~100 vars in ~10 min):
- Decomposability
- Sufficient statistics
-
In some cases, we can reduce the search problem to an easy optimization problem