Minds and Computers : An Introduction to the Philosophy of Artificial Intelligence
Download 1.05 Mb. Pdf ko'rish
|
document (2)
- Bu sahifa navigatsiya:
- Exercise 7.5
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. Download 1.05 Mb. Do'stlaringiz bilan baham: |
Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling
ma'muriyatiga murojaat qiling