Generate and Test Procedure

Algorithm

This is the simplest search strategy. It consists of the following steps :

   1.   Generating a possible solution for some problems; this means generating a particular point in the problem space. For others it may be generating a path from a start state.

   2.   Test to see if this is actually a solution by comparing the chosen point at the end point of the chosen path to the set of acceptable goal states.

   3.   If a solution has been found, quit otherwise return to step 1.

The generate - and - Test algorithm is a depth first search procedure because complete possible solutions are generated before test. This can be implemented states are likely to appear often in a tree; it can be implemented on a search graph rather than a tree.