1.4 Formulating Search Problems

• All search problems can be cast into the following general form:
  1. Starting State
     E.g.
     • starting city for a route
     • a jumbled Rubik's cube

  2. Goal State (or a test for goal state)
     E.g.
     • destination city
     • the solved Rubik's cube

  3. The permissible operators
     E.g.
     • go to city X
     • rotate subcube1, rotate subcube2, ...

• A state is a data structure which captures all relevant information about the problem.
  E.g.
  • a partial route
  • the orientation of all subcubes of Rubik's cube