Problem Solving as Search

Some Basic Questions Concerning Problem Solving

Is the problem solved by executing a sequence of steps which ideally bring one closer to the solution?
Is the consequence of an action predictable? Is there an adversary (another agent who can constrain the possible steps)?
Is the solution the way a goal is reached or the nature of the goal itself (what's found at the end)?
Is it important to know more than one way to reach the goal?
Is it important that the goal is reached in the most efficient way?
Is it important that the solution is found quickly?
Is there a way to estimate the "distance" to the goal?
How easy is it to reconsider and try a completely different set of steps?

Problem state: a particular configuration of the objects that are relevant for a problem
Figuring out how to represent the problem states is no simple matter.
State space: the space of all possible problem states
Normally only a partial state space is considered.
Initial states, goal states
State space search: search through the space of problem states for a goal state
Search trees: nodes are states (or paths), links are one-step transitions from one state to a successor state
Expanding a node (extending a state/path)
Testing for goal states (nodes)
The queue of untried states (paths); adding new states (paths) to the queue
Branching factor of the search: average number of successor states each state has
Depth of the search: how far down the tree is extended during the search

Last updated: 16 January 1996
URL: http://www.indiana.edu/~gasser/Q351/search1.html
Comments: gasser@salsa.indiana.edu
Copyright 1996, The Trustees of Indiana University