Problem Solving by Search

The solution of many problems (e.g. noughts and crosses, timetabling, chess) can be described by finding a sequence of actions that lead to a desirable goal. Each action changes the state and the aim is to find the sequence of actions and states that lead from the initial (start) state to a final (goal) state.

A well-defined problem can be described by:

• Initial state
  
  
• Operator or successor function - for any state x returns s(x), the set of states reachable from x with one action
  
  
• State space - all states reachable from initial by any sequence of actions
  
  
• Path - sequence through state space
  
  
• Path cost - function that assigns a cost to a path. Cost of a path is the sum of costs of individual actions along the path
  
  
• Goal test - test to determine if at goal state
  
  

<<<Previous Section Next>>>