Problem Solving and Search

Many problems can be viewed as search

  • A search space consists of states and operators: it is a graph
  • A search tree represents a particular exploration of search space

General Search Algorithm

NODES <‐ InitialState
  LOOP DO
  IF NODES is empty THEN RETURN failure.
  Node <‐ Get a node from NODES
  IF GoalTest(Node) THEN RETURN Node.
  NODES <- Merge( ExpandNode(Node), NODES )
END DO
  • Depth‐first, breadth‐first and uniform‐cost searches are uninformed.
  • In informed search there is an estimate(heuristic) available of the cost(distance) from each state (city) to the goal

Using Heuristics

  • Uniform-cost tells us to go to X because 1 < 200
  • If h(X) >> h(Y), we may choose Y over X, e.g. h(X)=100, h(Y)=1