The Problem-Solving Process: Problem Space and Search

■ Problem solving is goal-directed behavior that often involves set- ting subgoals to enable the application of operators.
■ Problem-solving operators generate a space of possible states through which the problem solver must search to find a path to the goal.

The Problem-Solving Process: Problem Space and Search

<iframe style="width:120px;height:240px;" marginwidth="0" marginheight="0" scrolling="no" frameborder="0" src="//ws-na.amazon-adsystem.com/widgets/q?ServiceVersion=20070822&OneJS=1&Operation=GetAdHtml&MarketPlace=US&source=ac&ref=tf_til&ad_type=product_link&tracking_id=healthwithham-20&marketplace=amazon&region=US&placement=B01LZ3RLPC&asins=B01LZ3RLPC&linkId=ab9f46a6d15fe26bcb1eeb7e0d60c989&show_border=false&link_opens_in_new_window=false&price_color=333333&title_color=0066c0&bg_color=ffffff">

    </iframe>

Often, problem solving is described in terms of searching a problem space, which consists of various states of the problem. A state is a representation of the prob- lem in some degree of solution. The initial situation of the problem is referred to as the start state; the situations on the way to the goal, as intermediate states; and the goal, as the goal state. Beginning from the start state, there are many ways the problem solver can choose to change the state. Sultan could reach for a stick, stand on his head, sulk, or try other approaches. Suppose he reaches for a stick. Now he has entered a new state. He can transform it into another state—for example, by letting go of the stick (thereby returning to the earlier state), reach- ing for the food with the stick, throwing the stick at the food, or reaching for the other stick. Suppose he reaches for the other stick. Again, he has created a new state. From this state, Sultan can choose to try, say, walking on the sticks, putting them together, or eating them. Suppose he chooses to put the sticks together. He can then choose to reach for the food, throw the sticks away, or separate them. If he reaches for the food and pulls it into his cage, he will achieve the goal state.
The various states that the problem solver can achieve define a problem space, also called a state space. Problem-solving operators can be thought of as ways to change one state in the problem space into another. We can think of the problem space as a maze of states and of the operators as paths for moving among them. The challenge is to find some possible sequence of operators in the problem space that leads from the start state to the goal state. Given such a characterization, solving a problem can be described as engaging in a search; that is, the problem solver must find an appropriate path through a maze of states. This conception of problem solving as a search through a state space was developed by Allen Newell and Herbert Simon, who were dominant figures in cognitive science throughout their careers, and it has become the major problem- solving approach, in both cognitive psychology and artificial intelligence.
A problem-space characterization consists of a set of states and operators for moving among the states. A good example of problem-space characteriza- tion is the eight puzzle, which consists of eight numbered, movable tiles set in a 3 3 3 frame. One cell of the frame is always empty, making it possible to move an adjacent tile into the empty cell and thereby to “move” the empty cell as well. The goal is to achieve a particular configuration of tiles, starting from a different configuration. For instance, a problem might be to transform
The possible states of this problem are represented as configurations of tiles in the eight puzzle. So, the first configuration shown is the start state, and the second is the goal state. The operators that change the states are move- ments of tiles into empty spaces. 
This search space terminology describes possible steps that the problem solver might take. It leaves two important questions that we need to answer be- fore we can explain the behavior of a particular problem solver.
First, what de- termines the operators available to the problem solver?
Second, how does the problem solver select a particular operator when there are several available?
An answer to the first question determines the search space in which the problem solver is working. An answer to the second question determines which path the problem solver takes.