|
Back to practice exercises.
1: Background Reading
2: Learning Goals
- Define/read/write/trace/debug different search algorithms
- Implement pruning
3: Directed Questions
- In branch and bound (B&B), how is the upper bound (UB) calculated? [solution]
- How is the lower bound (LB) calculated for a path? [solution]
- With B&B, when do we prune a path? [solution]
4: Exercise: Branch and Bound Search
Consider the search problem represented in the following figure, where a is the start node and there are
goal nodes at f and j. For each node, the heuristic cost is indicated on the node, and for each
arc, the arc cost is indicated along the arc. Neighbors are ordered according to the f function.
- What is the UB when only the start node has been explored? [solution]
- Which goal node is found first by B&B? [solution]
- What is the UB immediately after the first goal node is found? [solution]
- Is the second goal found by B&B? [solution]
5: Learning Goals Revisited
- Define/read/write/trace/debug different search algorithms
- Implement pruning
|
