Page images

Problem statement

Given: a generator of the set {x};

a test of the predicate P defined on elements of {x}; Find: an element of {x} that satisfies P(x).

[blocks in formation]

To show y is a solution if and only if y = {x} and P(y).
Notation: → a means that process π produces a;

a/ẞ means that a is on line labeled ß.

Test has associated with it a predicate P on one variable, such that:

test →→ a/+ if and only if P(a) and a/input;

test → a/- if and only if

P(a) and a/input.

Generate has associated with it a set {x} such that:

· generate → a/element only if a Є {x};

a E {x} implies there exists a time when generate → a/element. Working backward from the flow line labeled solution, we get: 1. y/solution if and only if test → y/+.

2. test→y/+ if and only if P(y) and y/input.

Now we need only show that y/input if and only if y = {x}.

3. y/input if and only if generate → y/element.

4. generate →→→y/element only if y = {x}.

Now we need only show that y E {x} implies generate →y/element; however, the best we can do is:

5. y E {x} implies there exists a time when generate →→ y/element.

Figure 10.4. Generate-and-test method.

on the needs of the rest of the processing. The input can be passed through on one condition and nothing done on the other, in which case test acts as a filter or gate. The input can be passed through in both cases, but on different output lines, in which case test acts as a binary switch.

The set associated with a generator and the predicate associated with a test are not inputs. Rather, they are constructs in terms of which the behavior of the process can be described. This is done in Fig. 10.4 by listing a set of propositions for each process. The single arrow (→) indi

cates production of an output, and the slash (/) indicates that a data item is on the line with the given label. Thus the first proposition under test says that test produces an item on its + output line if and only if that item was input and also satisfies the associated predicate. For any particular generator the associated set must be fully specified, but clearly that specification can be shared in particular ways between the structure of the generator and some actual inputs; for example, a generator could take an integer as input and produce the integers greater than the input, or it could have no input at all and simply generate the positive integers. The same situation holds for test or any other process: its associated constructs must be fully specified, but that specification can be shared in different ways between the structure of the process and some of its inputs. Sometimes we will put the associated construct on the flow diegram, as we have in Fig. 10.4, to show the connection between the processes in the flow diagram and the constructs used in the statement of the problem. We use dotted lines to show that these are not really inputs, although inputs could exist that partially specify them.

We have provided a sketch of a justification that the procedure of the method actually solves the problem. In substance the proof is trivial. To carry it through in detail requires formalization of both the procedure and the language for giving the problem statements and the properties known to hold if a process is executed [6]. The handling of time is a bit fussy and requires more formal apparatus than is worthwhile to present here. Note, for instance, that if the generator were not allowed to go to conclusion, generate-and-test would not necessarily produce a solution. Similar issues arise with infinite sets. Justifications will not be presented for the other methods. The purpose of doing it for this (simplest) one is to show that all the components of a method-problem statement, procedure, and justification-exist for these methods of artificial intelligence. However, no separate rationale is needed for generate-andtest, partly because of its simplicity and partly because of the use of a highly descriptive procedural language. If we had used a machine code, for instance, we might have drawn the procedure of Fig. 10.4 as an informal picture of what was going on.

Generate-and-test is used as a complete method, for instance, in opening a combination lock (when in desperation). Its low power is demonstrated by the assertion that a file with a combination lock is a "safe." Still, the method will serve to open the safe eventually. Generateand-test is often used by human beings as a second method for finding lost items, such as a sock or a tiepin. The first method relies on recollections about where the item was left or last seen. After this has failed,

generate-and-test is evoked, generating the physical locations in the room one by one, and looking in each.

The poor record of generate-and-test as a complete method should not blind one to its ubiquitous use when other information is absent. It is used to scan the want ads for neighborhood rentals after the proper column is discovered (to the retort "What else?", the answer is, "Right! That's why the method is so general"). In problem-solving programs it is used to go down lists of theorems or of subproblems. It serves to detect squares of interest on chessboards, words of interest in expressions, and figures of interest in geometrical displays.

3.2. Match

We are given the following expression in symbolic logic:


e: (p ▼ q) Ɔ ((p ▼ q) ▼ (r Ɔ p))

A variety of problems arise from asking whether e is a member of various specified sets of logic expressions. Such problems can usually be thrown into the form of a generate-and-test, at which point the difficulty of finding the solution is directly proportional to the size of the set.

If we know more about the structure of the set, better methods are available. For instance, consider the following two definitions of sets: S1: x (x V y), where x and y are any logic expressions.

Examples: p (p ▼ g), q Ɔ (q ▼ g), (p ▼ p) Ɔ ((p ≤ p) V p), . . . . S2: a, where a may be replaced (independently at each occurrence) according to the following schemes:

[blocks in formation]


Examples: q, p V q, q Ɔ q, p ▼ (p ▼ g), (p ▼ q) Ɔ (p ▼ g),..........

In S1, x and y are variables in the standard fashion, where each occurrence of the variable is to be replaced by its value. In S2 we have defined a replacement system, where each separate occurrence of the symbol a may be replaced by any of the given expressions. These may include α, hence lead to further replacements. A legal logic expression exists only when no a's occur.

It is trivial to determine that e is a member of the set of expressions defined by S1, and not so trivial to determine that it is not a member of the set defined by S2. The difference is that for S1 we could simply match the expressions against the form and determine directly the values of the variables required to do the job. In the case of S we had essentially to generate-and-test. (Actually, the structure of the replacement system

permits the generation to be shaped somewhat to the needs of the task, so it is not pure generate-and-test, which assumes no knowledge of the internal structure of the generator.)

Figure 10.5 shows the structure of the match method, using the same symbolism as in Fig. 10.4 for the generate-and-test. A key assumption, implicit in calling X and F expressions, is that it is possible to generate the subparts of X and F, and that X and F are equal if and only if corresponding subparts are equal. Thus there are two generators, which produce corresponding subparts of the two expressions as elements. These are compared: if equal, the generation continues; if not equal, a test is made if the element from the form is a variable. If it is, a substitution of the corresponding part of X for the variable is possible, thus making the two expressions identical at that point, and permitting generation to continue. The generators must also produce some special end signal, whose co-occurrence is detected by the compare routine to determine that a solution has been found.

The match procedure sketched in Fig. 10.5 is not the most general one possible. Operations other than substitution can be used to modify the form (more generally, the kernel structure) so that it is equal to X. There can be several such operations with the type of difference between the two elements selecting out the appropriate action. This action can

Problem statement

Given: expressions made up of parts from a set S;

a set of variables {v} with values in S;

a form F, which is an expression containing variables;

an expression X.

Find: if X is in the set defined by F; that is,

Find: values for {v} such that X = F (with values substituted). Procedure

[blocks in formation]

result in modification of X as well as F. It is possible to write a single procedure that expresses these more general possibilities, but the detail does not warrant it. The essential point is that generation occurs on the parts of the expressions, and when parts fail to correspond it is possible to make a local decision on what modifying operation is necessary (though perhaps not sufficient) for the two expressions to become equal.

Matching is used so pervasively in mathematical manipulation, from algebraic forms to the conditions of a theorem, that our mathematical sophistication leads us not to notice how powerful it is. Whenever a set of possible solutions can be packaged as a form with variables, the search for a solution is no longer proportional to the size of the set of all possible solutions, but only to the size of the form itself. Notice that the generate process in generate-and-test (Fig. 10.4) operates on quite a different set from the generate of the match (Fig. 10.5).

Beside the obvious uses in proving theorems and doing other mathematics, matching shows up in tasks that seem remote from this discipline. One of them, as shown below, is inducing a pattern from a part. Another use is in answering questions in quasi-natural language. In the latter, information is extracted from the raw text by means of forms, with the variables taking subexpressions in the language as values.

3.3. Hill Climbing

The most elementary procedure for finding an optimum is akin to generate-and-test, with the addition that the candidate element is compared against a stored element-the best so far-and replaces it if higher. The element often involves other information in addition to the position in the space being searched, for example, a function value. With just a little stronger assumptions in the problem statement, the problem can be converted into an analog of climbing a hill. There must be available a set of operators that find new elements on the hill, given an existing element. That is, new candidate elements are generated by taking a step from the present position (one is tempted to say a "nearby" step, but it is the operators themselves that define the concept of nearness). Thus the highest element so far plays a dual role, both as the base for generation of new clements and as the criterion for whether they should be kept.

Figure 10.6 provides the capsule formulation of hill climbing. Generation is over the set of operators, which are then applied to the best x so far, until a better one is found. This method differs from the various forms of steepest ascent in not finding the best step from the current position before making the next step.

« PreviousContinue »