Page 93 - Deep Learning

76 Creativity

Initial state

Goal

Figure 3.3. Heuristic search solves a problem by finding a path through the space of
possible actions that leads from the initial state to the goal state.

outcomes, inside the head. in their theory, presented in their monumental
1972 volume on Human Problem Solving, a problem solver’s mental represen-
tation of a problem has three main components: First, the initial problem state
is, approximately, the perception of the situation at hand. Second, there is a set
of operators which in their effects on the problem representation mimic the
effects of physical actions on the material problem situation. The operators
enable the problem solver to simulate in the mind’s eye the effects of actions.
Third, there is the goal, the problem solver’s concept of what it means to solve
the problem. The set of possibilities defined by the initial state, the operators
and the goal defines the problem space, the space of possible solutions that the
person is considering. 46
to solve a problem is to identify a path through the problem space that
leads from the initial problem state to the goal state. This can be done by apply-
ing an operator, evaluate the outcome, apply another operator and so on; this
process is called search. it can be visualized as in Figure 3.3.
The key difficulty is that search, like generate-and-test, is subject to com-
binatorial explosion. even when the number of relevant operators is modest,
the number of possible paths is astronomical. For most problems, a problem
solver can only explore a small proportion of the possible paths before running
out of cognitive capacity, time or some other resource.
How, then, do problem solvers succeed? Newell and Simon’s answer is based
on three central concepts: heuristics, look-ahead and evaluation functions.
even if a problem is unfamiliar and requires a creative response, it is unlikely
to be completely and utterly unfamiliar. (if it is, we are unlikely to make much
progress: How would we begin to build a time travel machine?) We can always
bring some prior knowledge to bear on the ever-branching alternatives and