Minds and Computers : An Introduction to the Philosophy of Artificial Intelligence

Figure 7.3
Generation tree.

---

An arrow leading from a node represents a possible application of a rule
to the state at that node – the resultant output state of that rule appli-
cation is at the node the arrow leads to. So the root node has three arrows
leading from it as there are three possible ways to apply the rule to it. We
will call these arrows branches, in keeping with the tree metaphor.
Some of the branches in Figure 7.3 lead to terminal nodes. A node
counts as terminal if there are no arrows leading from it (i.e. if there
is a terminal state at the node). Terminal nodes are the leaves, or tips,
of our tree.
The first iteration of the system is represented by the first level of
the generation tree after the root node. Figure 7.3 gives the complete
generation tree for the first two iterations and a partial tree for the
third iteration.
The first iteration has three nodes, two of which are terminal.
In total, the first iteration contains two s – the two at the only non-
terminal node. We know that there will be three ways of applying the
rule to each  so there will be six branches leading from the first iter-
ation. In other words, there will be six nodes at the second iteration
(as shown in the example).
Exercise 7.5
(a) The third iteration of the tree in Figure 7.3 is incomplete.
Use the reasoning in the above paragraph to determine
how many nodes there should be at the third iteration.
(b) How many of these nodes will be terminal?
(c) Find a large sheet of paper or a whiteboard and draw up a
complete generation tree for [BIN] down to the fourth
iteration.
Given a generation tree, we can read derivations straight o
ff it by
simply following a branch from the node we are interested in back up
to the root node. For example, here is a derivation of the state ‘11’ in
[BIN] as read o
ff the leftmost branch of the tree in Figure 7.3.
1.

initial state
2.



 ø



 ø
3.
1


 ø



 
4.
11


 1



 ø
So there is a general procedure for finding derivations in a formal
system: simply complete the entire generation tree for the system, find
the state you require a derivation for and read the derivation o
ff the tree.
66
  

---

Unfortunately, as you would have seen if you attempted Exercise
7.5(c), generation trees can get very complicated very quickly. Many
systems, including [BIN], su
ffer from exponential explosion –
branches proliferate exponentially as we iterate.
What’s worse is that, as you may have realised, some branches
just go on for ever – they go infinite. This means that the procedure
of drawing up the generation tree is not e
ffective for systems
whose trees have infinite branches. We will investigate the rami-
fications of this further when we discuss search procedures in
Chapter 11.