1 Requirements of Search

To carry out search by means of a computer program, several elements of the problem and search strategy must be defined. Search requires the following elements [Nilsson, 1971]:

• A defined problem, often requiring intelligent or complex behaviour to solve,
• A model of the problem and the representation of possible solutions,
• A goal state that defines the ideal solution, where heuristic methods often use an evaluation function to rank the non-goal state solutions,
• Transformation operators that are capable of changing an existing solution into an alternative solution, and
• A strategy for searching the space of possible solutions using the representation and transformation operators.

The application of the transformation operator(s) on a solution creates a neighbourhood of solutions. These new solutions can then be compared to the goal state. When knowledge of the problem is available, heuristic algorithms can define an evaluation function that allows the scoring and ranking of solutions. The ranking of solutions determines which, if any, of the solutions in the neighbourhood are better.

While search requires the above items, much of artificial intelligence and search research focuses on the last item, finding good search strategies.