Assignment 2: Search
Due 11:59pmEDT Tuesday, 13 September 2022
Please turn in a PDF through Gradescope.
You'll need to access Gradescope through Brightspace the first time (to register you for the course in Gradescope.)
Gradescope is pretty self-explanatory,
ITaP provides these instructions.
Make sure that you mark the start/end of each question in Gradescope. Assignments will be graded based on what you mark as the start/end of each question.
Please typeset your answers (LaTex/Word/OpenOffice/etc.)
1. Search Strategies
Given the following state/event/cost graph, where X is the initial state, and Y1, Y2, and Y3 are solution states:
- Draw the first three levels of the corresponding search tree, starting at xxx. You may limit each node to four branches, if there are more just indicate there are more.
- What is the branching factor b, solution depth d, and maximum tree depth m?
- Complete the following table, giving the actual costs and solution found for a sample run of the algorithm rather than in terms of b, d, and m. If different from the worst-case costs or expectations of completeness/optimality, briefly explain why.
| Time (steps) | Space (nodes) | Solution found? | Optimal solution found? |
|---|
| Depth-First Search | | | | |
|---|
| Breadth-First Search | | | | |
|---|
| Iterative Depth-First Search | | | | |
|---|
| Uniform Cost Search | | | | |
|---|
| Dynamic Programming | | | | |
|---|
| Greedy Search | | | | |
|---|
| A* Search | | | | |
|---|
| Hill-climbing search | | | | |
|---|
What assumptions did you have to make to compute the above?
2. Heuristic Search
Give a situation where a heuristic search would likely be better than approaches guaranteed to give an optimal solution. Explain why it would be better. Your explanation should cover at least:
- Relative quality of the solution
- Costs of obtaining the solution
- Expected/typical case vs. worst case
- Why real-world constraints make the heuristic search a better choice
3. Locally optimal search
Give a situation where locally optimal search would likely be better than globally optimal approaches. Explain why it would be better. Your explanation should cover at least:
- What are the benefits of locally optimal search for your situation?
- Could you have situations where locally optimal search would be really bad? If so, how could you mitigate this?
- Does your situation give cases where you couldn't use a globally optimal search? If so, explain.
4. Continuous search
One way to solve a continuous search problem is to discretize the problem and use a state-based (discrete) search such as A*. But this isn't necessarily the best way.
- Come up with a problem (other than the one in the book) where there is a significantly better solution than discretizing/search (for the solution, you are welcome to use something from the book.) Explain why your solution is better for that problem.
-
Is there a situation where discretizing/search would completely fail, by giving a result that is far from optimal? If so, would the approach you describe in part 1 do better? Explain.
5. Search Problems
You have been asked to develop an AI advising assistant to help undergraduates plan their course schedules. The goal is to select courses so that a student completes their degree. Assume there are certain constraints, such as taking at most five classes per semester. Model this as a planning/search problem.
- Give three examples of states in your planning model.
- What would constitute an action in your planning?
- Construct an sample of the graph showing states and state transitions. You should have at least five states. Label costs, and describe briefly how you determine the costs.
- Give estimates for the search tree size (branching factor, etc.) as you've defined the problem.
- Would a depth-first search be complete for your problem? What about breadth-first?
- What would constitute an optimal solution?
- Name a search strategy that would find an optimal cost solution, and one that would be efficient in finding a solution. Which would be more appropriate and why?
- Would an informed cost strategy (e.g., greedy or A* search) be appropriate for your problem? Briefly explain.
