Catalogue of Artificial Intelligence Techniques
Keywords: evaluation function, heuristic search
Author(s): Alan Bundy
A complexity measure measures some aspect of the complexity of the current problem state in a search problem. For instance, the depth of a goal is the length of the path from the current goal to the origin of the Search Space. Complexity measures are sometimes associated with the labels of nodes in a search space, especially when these are logical expressions describing the current goal; e.g., the depth of function nesting of an expression is the maximum amount of nesting in the functions in it. The size of an expression is the number of symbols in it. These symbols can also be weighted and the weights totalled. Complexity measures can be used for pruning, in which case they are usually called bounds. In pruning, parts of the search space whose measure exceeds a threshold are not searched. They can also be used as components in the evaluation function of heuristic search.
- Nilsson, N.J., Principles of Artificial Intelligence
, Tioga Pub. Co., Palo Alto, California, 1980.