Catalogue of Artificial Intelligence Techniques


Jump to: Top | Entry | References | Comments

View Maths as: Images | MathML

Complexity Measures

Keywords: evaluation function, heuristic search

Categories: 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.



Add Comment

No comments.