S

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
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?
SEARCH TREE
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.
SELECTION
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.
STATE
A state is a particular configuration of an environment. When an agent acts upon its environment a new state is generated.
State
Blocks World – States
SEE ALSO:  Action, Environment
APPLICATIONS:  desktopUSS
STATE SPACE
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.
SEE ALSO:  Action, State, Environment
APPLICATIONS:  desktopUSS
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.

State Space Landscape
One-dimensional State Space Landscape
SEE ALSO:  Local Search
Applications:  desktopGA
It explores the state space systematically, examining the states one by one, until it finds a goal state.
SEE ALSO:  Goal State, Search, State Space
APPLICATIONS:  desktopUSS