SEE THE SOURCES USED FOR THE GLOSSARY DEFINITIONS HERE
There are two kinds of search problems:
- Search for paths to goals: The problem is to find a sequence of actions that reaches a goal state. The search algorithm takes a problem as input and returns a solution in the form of an action sequence. Systematic search strategies are used to solve this kind of problem.
- Search for solutions: The problem is to find a solution (the goal state itself) in a large space of candidate solutions. The path to the goal state is irrelevant. Local search strategies are used to solve this kind of problem.
Search strategies are evaluated according to:
- Completeness – Does it always find a solution if one exists?
- Optimality – Does it always find the least cost solution?
- Time complexity – How long does it take to find a solution?
- Space complexity – How much memory is needed to perform the search?
SEE ALSO: Action, Goal State, Local Search, Problem Formulation, State, Systematic Search
The initial state of the problem is at the root; the branches are actions and the nodes correspond to states in the state space of the problem.
SEE ALSO: Action, Goal State, Initial State, Node (Search Tree), State Space
Operator that selects individuals in a population to generate new individuals. It is used to direct the search process towards better regions of the search space by giving preference to individuals of higher fitness.
SEE ALSO: Evolutionary Algorithm, Individual, Population, Proportional Selection, Tournament Selection
A state is a particular configuration of an environment. When an agent acts upon its environment a new state is generated.
The state space of a problem is the set of all states reachable from the initial state by any sequence of actions. It forms a directed graph in which nodes are states and the links between nodes are actions. If the number of different states is sufficiently small, the graph can be stored explicitly.
STATE SPACE LANDSCAPE
In local search it is useful to consider a state space landscape. It has location, defined by the state, and elevation, defined by the value of the objective function.
It explores the state space systematically, examining the states one by one, until it finds a goal state.