Maching.

MATCHING

So far, we have seen the process of using search to solve problems as the application of appropriate rules to individual problem states to generate new states to which the rules can then be applied, and so forth, until a solution is found. Clever search involves choosing from among the rules that can be applied at a particular point, the ones that are most likely to lead to a solution. We need to extract from the entire collection of rules, those that can be applied at a given point. To do so requires some kind of matching between the current state and the preconditions of the rules. How should this be done?

One way to select applicable rules is to do a simple search through all the rules comparing one’s preconditions to the current state and extracting all the ones that match . this requires indexing of all the rules. But there are two problems with this simple solutions:

A. It requires the use of a large number of rules. Scanning through all of them would be hopelessly inefficeint.

B. It is not always immediately obvious whether a rule’s preconditions are satisfied by a particular state.

Sometimes , instead of searching through the rules, we can use the current state as an index into the rules and select the matching ones immediately. In spite of limitations, indexing in some form is very important in the efficient operation of rules based systems.

A more complex matching is required when the preconditions of rule specify required properties that are not stated explicitly in the description of the current state. In this case, a separate set of rules must be used to describe how some properties can be inferred from others. An even more complex matching process is required if rules should be applied and if their pre condition approximately match the current situation. This is often the case in situations involving physical descriptions of the world.