|
|
|
|
Problem Set #2:
Guidelines
- Reading: Chapter 4 (Setion 4.5 Optional)
- Due: Oct. 15th at the beginning of class
- Problem sets have to be typed, hard copy, and legible.
Problem
Consider the problem of searching for a solution for the Rubik's cube.
- Describe a representation of Rubik's Cube as a state-space search problem. Specifically outline the problem state, transitions, start state and end state.
- Define an admissible heuristic for performing an informed search over the problem space. Clearly state why your heuristic is admissible. Are you able to tell whether your heuristic is also consistent (see page 99)?
- What search algorithm would you use to solve Rubik's cube? Explain precisely why your algorithm would outperform other choices as well as any potential downsides to using such an algorithm.
- Would you apply your search algorithm using forward search, backward search, or bi-directional search? Explain your choice precisely.
Precise answers are those that consider completeness, optimality, time complexity, space complexity, and other factors.
|