Application of graphs in problem solving:

1. to model the problem
2. to model the solution process

Problem solving: search in a space of possible states.

Basic idea:

1. Decide on a representation of the states and the available actions in the domain
2. Find a sequence of actions that will transform the initial state into the target state.

Examples:

1. Store initial state into a stack / queue
2. While there are states in the stack/queue and target state is not reached
• Read a state from the stack / queue.
• Generate next states by applying relevant operators
  (not all operators are applicable for a given state)
• Test to see if the goal state is reached.
• If yes - stop
• If no - add the generated states into the stack/queue
  (do not add if the state has already been generated)
3. If the stack /queue is empty and the target state is not reached - the problem
   is not solvable with the available operators.

To get the solution: Record the sequence of applied operators.

Using a stack corresponds to depth-first search in the state space.
Using a queue corresponds to breadth-first search in the state space.

Breadth-first vs depth-first.

Exhaustive search (brute force) vs informative (constraint-based, heurististic) search.

Basic idea:

If at some state no operator is applicable or all applicable operators
result in already generated states:

• reject the currently reached state as a dead-end state,
• go back to some previous level in the state-space tree/graph
• proceed with the exploration of other paths toward the target state

Backtracking occurs in depth-first search.